(۱۶ اردیبهشت ۱۳۹۴ ۱۲:۲۸ ب.ظ)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) هستند.