پیچیدگی این تابع:
تابع بازگشتی پیچیدگی زمانی این تابع به صورت زیر است :
[tex]T(n)=T(n-1) 1[/tex]
[tex]T(1)=1[/tex]
مرتبه این تابع هم برابر است :
[tex]\theta(n)[/tex]
چطور T(n)=T(n-1)+1 رو به دست آوردید راه حلش چی هست؟ با سپاس
با نگاه کردن به تابع داده شده می بینیم که اگر n==1 بود که m را بر می گرداند در غیر این صورت تابع f را با مقدار n-1 صدا می زند.
در واقع وقتی f(n,m) را اجرا می کنید در ابتدا یک مقایسه انجام می شود و سپس در مورد ادامه مسیر تصمیم می گیرد خب همین مقایسه یک واحد پیچیدگی دارد. اگه n==1 نبود باید رفت f(m, n-1) رو اجرا کرد پس در حالتی که n==1 نباشد پیچیدگی f(m,n) با پیچیدگی f(n, m-1) برابر است.
با توجه به این که در این تابع m هیچ کاره است متوجه می شویم که پیچیدگی تنهابه n بستگی دارد پس پیچیدگی تابعی از n است. اگر فرض کنیم که پیچیدگی f(m,n) را با T(n) نشان دهیم و فرض کنیمکه n==1 نباشد پس باید اول یک مقایسه انجام دهیم و بعد می دانیم که در شرط n==1 صدق نمی کند و باید f(m,n-1) را صدا کنیم. پس t(n) برابر می شود با پیچیدگی چک کردن شر که برابر است با ۱ و پیچیدگی اجرای f(m,n-1) که برابر است با T(n-1) پس می توان نوشت:
T(n)=T(n-1)+1
و اگر هم n==1 باشد پیچیدگی تنها یک مقاسه ی if و برگشتن مقدار m است پس T(1)=1
حالا چطور رابطه ی T(n)=T(n-1)+1 را حل کنیم:
راحت ترین روش جایگذاری است:
T(1)=1
T(2)=T(1)+1=1+1=2
T(3)=T(2)+1=2+1=3
..
.
T(n)=T(n-1)+1=n-1+1=n.