تحلیل الگوریتمها: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
بدون خلاصۀ ویرایش برچسبها: ویرایشگر دیداری ویرایش همراه ویرایش از وبگاه همراه |
بدون خلاصۀ ویرایش برچسبها: متن دارای ویکیمتن نامتناظر ویرایشگر دیداری ویرایش همراه ویرایش از وبگاه همراه |
||
خط ۱۶۵:
|-
! width=10|Case
! حالت بندی روی <math>f(n)</math> درمقایسه با <math>c_{\operatorname{crit}}</math>,
! توضیحات
▲! حالت بندی روی <math>f(n)</math> درمقایسه با <math>c_{\operatorname{crit}}</math>, i.e. <math>\log_b a</math>
! توصیف با تابع رشد
! width=400|مثال
|-
! 1
|آهنگ رشد <math>f(n)</math> بر برگ ها غلبه میکند▼
| اگر <math>f(n) = \mathcal {O(n^{c})}</math> در شرایطی که <math>c<c_{\operatorname{crit}}</math>
▲|آهنگ رشد <math>f(n)</math> بر برگ ها غلبه میکند.
|
<math>T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)</math>
|
سطر ۱۸۷ ⟵ ۱۸۳:
! 2
| وقتی <math>f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)</math> برای هر <math>k \ge 0</math>
| آهنگ رشد توابع بازگشتی با <math>f(n)</math> تقریبا یکسان است.
|جواب به صورت زیر است :
| اگر <math>b=a^2</math> و <math>f(n) = \Theta(n^{1/2})</math>, آنگاه <math>T(n) = \Theta(n^{1/2} \log n)</math>.
سطر ۲۰۰ ⟵ ۱۹۵:
! 3
| آهنگ رشد توابع بازگشتی ایجاد شده زیاد بوده و تعداد برگها به <math>f(n)</math> غلبه میکند▼
| وقتی <math>f(n) = \Omega(n^{c})</math> در حالی که <math>c>c_{\operatorname{crit}}</math>
▲| آهنگ رشد توابع بازگشتی ایجاد شده زیاد بوده و تعداد برگها به <math>f(n)</math> غلبه میکند.
| جواب به صورت زیر است:
|