Rekursiv alqoritmin vaxtı özünü çağırdığı üçün rekurrent münasibətlə yazılır: T(n) vaxtı daha kiçik girişlərdə T-nin qiyməti və hər çağırışın öz işi ilə ifadə olunur. Bu dərsdə rekurrentləri həll etməyin üç yolunu görəcəksiniz: açma/əvəzetmə, rekursiya ağacı və master teoremi.
Dörd tanış rekurrent
| Rekurrent | Nümunə | Həll |
|---|---|---|
T(n) = T(n-1) + c | faktorial, siyahının cəmi | O(n) |
T(n) = T(n-1) + n | rekursiv seçmə sıralama | O(n^2) |
T(n) = T(n/2) + c | ikili axtarış | O(log n) |
T(n) = 2T(n/2) + n | merge sort | O(n log n) |
T(n) = 2T(n-1) + c | hər addımda iki çağırış | O(2^n) |
Açma üsulu: T(n) = T(n-1) + n üçün T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 alınır. Aşağıdakı kod dörd rekurrentin real işini sayır və nəticələr nəzəriyyə ilə üst-üstə düşür.
def work_linear(n): # T(n) = T(n-1) + 1
return 0 if n == 0 else 1 + work_linear(n - 1)
def work_quad(n): # T(n) = T(n-1) + n
return 0 if n == 0 else n + work_quad(n - 1)
def work_log(n): # T(n) = T(n/2) + 1
return 0 if n <= 1 else 1 + work_log(n // 2)
def work_nlogn(n): # T(n) = 2T(n/2) + n
return 0 if n <= 1 else n + 2 * work_nlogn(n // 2)
for n in (16, 64, 256):
print(n, work_linear(n), work_quad(n), work_log(n), work_nlogn(n))