Böl və hökm sür

Böl və hökm sür metodu məsələni eyni tipli müstəqil kiçik məsələlərə bölür, hər birini rekursiv həll edir və cavabları birləşdirir.

Üç addım

1. Böl: məsələni hissələrə ayır (adətən iki yarıya).
2. Həll et: hər hissəni rekursiv həll et; ən kiçik hissə (baza halı) birbaşa həll olunur.
3. Birləşdir: hissələrin cavablarından ümumi cavabı qur.

Hissələr kəsişmir; bu, alt məsələlərin təkrarlandığı dinamik proqramlaşdırmadan əsas fərqdir.

Nümunə: rekursiv maksimum

def max_rec(a, lo, hi):
    if lo == hi:                          # base case: one item
        return a[lo]
    mid = (lo + hi) // 2
    left = max_rec(a, lo, mid)            # solve the left half
    right = max_rec(a, mid + 1, hi)       # solve the right half
    return max(left, right)               # combine

data = [3, 9, 2, 7, 5, 8]
print(max_rec(data, 0, len(data) - 1))

T(n) = 2T(n/2) + O(1) rekurrensi O(n) verir, adi dövr kimi. Nümunə yalnız sxemi göstərir.

Sürətli üstləmə

x^n = (x^(n/2))^2, tək n üçün isə bir x vuruğu da əlavə olunur. Yarı bir dəfə hesablanır: T(n) = T(n/2) + O(1) = O(log n).