大O符號中下列代碼的時間複雜度是多少？

Question

1. T(n) = 8*T(n/2) + n*n

2. T(n) = 3*T(n/4) + n

我想計算大O符號的時間複雜度。什麼是答案（不使用主定理）

Answer 1

主定理適用於形式T(n) = a*T(n/b) + n^c的任何重現。它着眼於和復發的兩個部分進行比較：在此級別（C） 2）的遞歸調用（的數量和尺寸

1）的恆定工作的大小和b）

從這裏，我們比較log_b（a）和c。有三種可能性

1. log_b (a) > c - >T(n)是O(n^log_b (a))
2. log_b (a) < c - >T(n)是O(n^c)
3. log_b (a) = c - >T(n)是O(n^c log(n))

因此，對於你的兩個例子...

1. T(n) = 8*T(n/2) + n*n，因此a = 8, b = 2, c = 2，log_2 (8) > 2，因此T(n)是O(n^(log_2 (8)) = O(n^3)
2. T(n) = 3 * T(n/4) + n，因此a = 3, b = 4, c = 1，log_4 (3) < 1，因此T(n)是O(n^c) = O(n)

A fuller explanation on Wikipedia

Answer 2

對於第一個關係，你可以做這個：