递归方程的时间复杂度

Question

运行 递归方程的时间 Cn = C(n/2) + 1 , C1 = 1.

它的时间复杂度是多少？

我正在考虑 O(logn)，因为它与 (+1) 无关，因为在大 O 表示法中 n > 1。如果 n = 0，它将只是 O(1)。我很困惑。感谢您的帮助。

Answer 1

是 C_n = C_n/2 + 1[=74= 的时间复杂度] 是 O(logn) 使用 Master Theorem. Btw its the equation of Binary Search.

来自大师方法：

T_n = aT_n/b + F_n

有以下三种情况：

1. 如果 f(n) = O(n^c) 其中 c < ^Log_ba 然后 T(n) = O(n^Log_ba)

2. 如果 f(n) = O(n^c) 其中 c = ^Log_ba 然后 T(n) = O(n^Log_ba*Logn)

3. 如果 f(n) = O(n^c) 其中 c > ^Log_ba 然后 T(n) = O(f(n))

你的情况： a = 1、b = 2

所以 n^Log_ba = n^Log₂1 = n⁰ = 1

还有 f(n) = O(1)。所以 n^Log_ba = c (案例 2)

因此，T(n) = O(n^Log_ba*Logn) = Θ(n ⁰*Logn) = O(Logn)