زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۳:۲۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

گام محاسباتی

ارسال:
  

فاطمه ارشد ای تی پرسیده:

گام محاسباتی

در صفحه ۲ کتاب طراحی الگوریتم مدرسان شریف نوشته جواد ظهیری امده است:

فراخوانی روال و تابع (call) : دستوری که شامل یک فراخوانی است گامی را لازم ندارد اما در عوض باید تعداد گام های مورد نیاز برای تابع یا روال فراخوانی شده محاسبه گردد.

همچنین در صفحه ۷ این کتاب آمده است :
پیچیدگی تمام توابعی که دارای تعداد ثابتی گام باشند با (۱)O نمایش داده می شود.

می شه لطفا این نوشته ها رو بیشتر یک نفر توضیح بده (حالا اگه با مثال باشه که چه بهتر)
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

gunnersregister پاسخ داده:

RE: گام محاسباتی

در دستور فراخوانی یه تابع یا زیرروال محاسباتی از نظر کامپیوتری انجام نمیگیره. اما در خود زیرروال که انجام یه سری کارها رو در خودش داره باید تعداد گامهاش حساب بشه.

ضمنا تعداد گامهایی که وابسته به n (ورودی مسئله) نباشه یعنی تعداد ثابتی باشه رو همون (۱)O میگیریم(برای راحتی محاسبات).
نقل قول این ارسال در یک پاسخ

ارسال:
  

فاطمه ارشد ای تی پاسخ داده:

RE: گام محاسباتی

(۱۶ اردیبهشت ۱۳۹۴ ۱۲:۲۸ ب.ظ)gunnersregister نوشته شده توسط:  
(16 اردیبهشت ۱۳۹۴ ۱۰:۴۸ ق.ظ)فاطمه ارشد ای تی نوشته شده توسط:  در صفحه ۲ کتاب طراحی الگوریتم مدرسان شریف نوشته جواد ظهیری امده است:

فراخوانی روال و تابع (call) : دستوری که شامل یک فراخوانی است گامی را لازم ندارد اما در عوض باید تعداد گام های مورد نیاز برای تابع یا روال فراخوانی شده محاسبه گردد.

همچنین در صفحه ۷ این کتاب آمده است :
پیچیدگی تمام توابعی که دارای تعداد ثابتی گام باشند با (۱)O نمایش داده می شود.

می شه لطفا این نوشته ها رو بیشتر یک نفر توضیح بده (حالا اگه با مثال باشه که چه بهتر)

در دستور فراخوانی یه تابع یا زیرروال محاسباتی از نظر کامپیوتری انجام نمیگیره. اما در خود زیرروال که انجام یه سری کارها رو در خودش داره باید تعداد گامهاش حساب بشه.

ضمنا تعداد گامهایی که وابسته به n (ورودی مسئله) نباشه یعنی تعداد ثابتی باشه رو همون (۱)O میگیریم(برای راحتی محاسبات).
خیلی ممنون متوجه شدم

(۱۶ اردیبهشت ۱۳۹۴ ۱۲:۳۷ ب.ظ)Farzamm نوشته شده توسط:  
(16 اردیبهشت ۱۳۹۴ ۱۰:۴۸ ق.ظ)فاطمه ارشد ای تی نوشته شده توسط:  در صفحه ۲ کتاب طراحی الگوریتم مدرسان شریف نوشته جواد ظهیری امده است:

فراخوانی روال و تابع (call) : دستوری که شامل یک فراخوانی است گامی را لازم ندارد اما در عوض باید تعداد گام های مورد نیاز برای تابع یا روال فراخوانی شده محاسبه گردد.

همچنین در صفحه ۷ این کتاب آمده است :
پیچیدگی تمام توابعی که دارای تعداد ثابتی گام باشند با (۱)O نمایش داده می شود.

می شه لطفا این نوشته ها رو بیشتر یک نفر توضیح بده (حالا اگه با مثال باشه که چه بهتر)

خود دستور فراخوانی تابع در واقع عملیاتی انجام نمی دهد و صرفاً تابع موردنظرمان که قرار است محاسبات موردنظرمان را انجام دهد صدا می زند، مثلاً تو برنامه ی زیر:
main }
...
fib(a)
...
{
خود دستور فراخوانی fib(a) کار انجام نمی ده و تابع فراخوانی شده عملیات مورد نظر را انجام می دهد، پس وقتی ما stepهای اجرای یک برنامه رو می شماریم لزومی ندارد خود دستور فراخوانی رو به عنوان یه گام در نظر بگیریم و مقدار عملیات صورت گرفته درون تابع فقط برای ما مهم است.

وقتی ما پیچیدگی محاسباتی یه برنامه رو حساب می کنیم، تعداد گام های اجرایی برامون مهمه که با تغییر سایز ورودی (n) مقدارش تغییر کنه / ولی مثلاً حلقه for کد زیر:
for (i=0; i>100; i++)
x=y+i
همواره ۱۰۰ بار اجرا میشه و سایز ورودی روی آن تأثیر نداره (حتی اگه یک میلیون هم باشه) / بنابراین چون تعداد گام های این حلقه همواره ثابت است در پیچیدگی تأثیری ندارد و O(1) محسوب می شود / به طور کلی مقادیر ثابت دارای پیچیدگی O(1) هستند.

خیلی ممنون متوجه شدم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Farzamm پاسخ داده:

RE: گام محاسباتی

(۱۶ اردیبهشت ۱۳۹۴ ۱۰:۴۸ ق.ظ)فاطمه ارشد ای تی نوشته شده توسط:  در صفحه ۲ کتاب طراحی الگوریتم مدرسان شریف نوشته جواد ظهیری امده است:

فراخوانی روال و تابع (call) : دستوری که شامل یک فراخوانی است گامی را لازم ندارد اما در عوض باید تعداد گام های مورد نیاز برای تابع یا روال فراخوانی شده محاسبه گردد.

همچنین در صفحه ۷ این کتاب آمده است :
پیچیدگی تمام توابعی که دارای تعداد ثابتی گام باشند با (۱)O نمایش داده می شود.

می شه لطفا این نوشته ها رو بیشتر یک نفر توضیح بده (حالا اگه با مثال باشه که چه بهتر)

خود دستور فراخوانی تابع در واقع عملیاتی انجام نمی دهد و صرفاً تابع موردنظرمان که قرار است محاسبات موردنظرمان را انجام دهد صدا می زند، مثلاً تو برنامه ی زیر:
main }
...
fib(a)
...
{
خود دستور فراخوانی fib(a) کار انجام نمی ده و تابع فراخوانی شده عملیات مورد نظر را انجام می دهد، پس وقتی ما stepهای اجرای یک برنامه رو می شماریم لزومی ندارد خود دستور فراخوانی رو به عنوان یه گام در نظر بگیریم و مقدار عملیات صورت گرفته درون تابع فقط برای ما مهم است.

وقتی ما پیچیدگی محاسباتی یه برنامه رو حساب می کنیم، تعداد گام های اجرایی برامون مهمه که با تغییر سایز ورودی (n) مقدارش تغییر کنه / ولی مثلاً حلقه for کد زیر:
for (i=0; i>100; i++)
x=y+i
همواره ۱۰۰ بار اجرا میشه و سایز ورودی روی آن تأثیر نداره (حتی اگه یک میلیون هم باشه) / بنابراین چون تعداد گام های این حلقه همواره ثابت است در پیچیدگی تأثیری ندارد و O(1) محسوب می شود / به طور کلی مقادیر ثابت دارای پیچیدگی O(1) هستند.
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Lightbulb گام به گام تا ارشد ۹۹ marvelous ۴۹۲ ۱۷۳,۳۱۵ ۱۵ شهریور ۱۳۹۹ ۰۷:۴۸ ب.ظ
آخرین ارسال: شانی
Question برنامه ریزی به سبک ۳ گام sara417 ۴ ۶,۴۵۸ ۲۰ آذر ۱۳۹۸ ۰۲:۰۴ ق.ظ
آخرین ارسال: marvelous
Question موسسه سه گام برای مشاوره ارشد marvelous ۱ ۳,۲۵۶ ۰۸ آذر ۱۳۹۸ ۱۱:۵۱ ب.ظ
آخرین ارسال: marvelous
  کتاب آموزش گام به گام c# sisili ۰ ۲,۰۴۳ ۱۵ آبان ۱۳۹۶ ۰۱:۰۴ ب.ظ
آخرین ارسال: sisili
Question سوال، مرتبه اجرایی و گام برنامه Mr.R3ZA ۶ ۵,۵۵۱ ۰۲ مرداد ۱۳۹۶ ۰۲:۴۲ ب.ظ
آخرین ارسال: mino0z
  پنج گام برای ارزیابی یک فرصت شغلی good-wishes ۴ ۵,۳۱۶ ۱۸ خرداد ۱۳۹۶ ۰۲:۱۴ ب.ظ
آخرین ارسال: terme86
  پردازنده های محاسباتی akramasadi ۰ ۱,۷۰۳ ۱۶ بهمن ۱۳۹۵ ۰۱:۳۱ ق.ظ
آخرین ارسال: akramasadi
Question هندسه محاسباتی- binary space partitioning royayebahar ۳ ۳,۱۱۹ ۲۴ اردیبهشت ۱۳۹۵ ۰۲:۰۴ ق.ظ
آخرین ارسال: royayebahar
  کاربرد هندسه محاسباتی در کامپیوتر irpersian20 ۲ ۲,۶۵۵ ۰۹ بهمن ۱۳۹۴ ۰۴:۰۴ ب.ظ
آخرین ارسال: matt2007
  هوش محاسباتی mm123456789 ۰ ۱,۱۲۷ ۰۲ دى ۱۳۹۴ ۰۹:۳۷ ب.ظ
آخرین ارسال: mm123456789

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close