Quan hệ lặp lại là các phương trình xác định một cách đệ quy một mảng nhiều chiều.
Ở đây chúng tôi sẽ giải quyết các câu hỏi dựa trên quan hệ lặp lại.
Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2 It is of the form f(n) = O(n^c), where c = 2
Điều này hình thành nó trong điều kiện định lý chính,
So, logb(a) = log2(12) = 3.58 Using case 1 of the masters theorm, T(n) = θ(n3.58).
Solve the recurrence reation: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, trong trường hợp các giá trị lớn, n, n / 2>> 23, do đó, 23 được bỏ qua.
T(n) = 5T(n/2) + 5n2 + 7n - 5/3. Further, we can take 5n2 + 7n - 5 ≃0(n2). So, T(n) = 5T(n/2) + O(n2)
Điều này thuộc trường hợp 2 của định lý bậc thầy,
So, T(n) = O(n2).
Kiểm tra xem điều sau có thuộc bất kỳ trường hợp nào của định lý tổng hay không.
T(n) = 2T(n/3) + 5n
Không, để áp dụng định lý bậc thầy, hàm phải là một hàm đa thức.
T(n) = 2T(n/5) + tan(n)
Không, hàm lượng giác không tuân theo định lý bậc thầy.
T(n) = 5T(n+1) + log(n)
Không, hàm Logarit không tuân theo định lý bậc thầy.
T(n) = T(n-7) + en
Không, hàm mũ không tuân theo định lý bậc thầy.
T(n) = 9n(n/2+1 ) + 4(n2) - 17 Yes, as solved above.