大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

对于第一个关系，你可以做这个：