Quan hệ hồi quy là các phương trình định nghĩa đệ quy một mảng đa chiều.
Chúng ta sẽ giải một số bài toán dựa trên quan hệ hồi quy.
Giải quan hệ hồi quy: T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. Ở đây, a = 12, b = 2 và f(n) = 9n2 + 2. Đây là dạng f(n) = O(n^c), với c = 2.
Đây rơi vào điều kiện của định lý Master:
logb(a) = log2(12) ≈ 3.585. Áp dụng trường hợp 1 của định lý Master: T(n) = Θ(n3.585).
Giải quan hệ hồi quy: T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3. T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3.
Khi đơn giản hóa, với n lớn, n, n/2 >> 23, nên 23 có thể bỏ qua.
T(n) = 5T(n/2) + 5n2 + 7n - 5/3. Tiếp tục, 5n2 + 7n - 5 ≃ O(n2). Vậy T(n) = 5T(n/2) + O(n2).
Đây rơi vào trường hợp 2 của định lý Master:
Vậy T(n) = O(n2).
Kiểm tra xem các quan hệ sau có rơi vào trường hợp nào của định lý Master không.
T(n) = 2T(n/3) + 5n
Không, vì định lý Master yêu cầu hàm phải là hàm đa thức.
T(n) = 2T(n/5) + tan(n)
Không, hàm lượng giác không thuộc định lý Master.
T(n) = 5T(n+1) + log(n)
Không, hàm logarit không thuộc định lý Master.
T(n) = T(n-7) + en
Không, hàm mũ không thuộc định lý Master.
T(n) = 9n(n/2+1) + 4(n2) - 17 Có, như đã giải ở trên.