algorithm - 函数复杂度 T(N)=T(n/2)+2^n

Question

我是一名在大学学习算法课程的学生。我知道如何应用一些递归技术来查找更简单函数的运行成本，但是2^n这个问题给我带来了麻烦。这是我尝试应用主定理的方法

a=1,b=2 n^log2(1)= n^0.65

这导致n^0=1我知道它必须是多项式乘以，f(N)但2^n我不明白这与 . 有什么可比性2^n。

我也尝试使用递归树，但它太复杂了。

Answer 1

如果没有主定理，这也很容易做到：

T(n) = T(n / 2) + 2^n)
     = T(n / 4) + 2^(n / 2) + 2^n
     = ...
     < 2^0 + 2^1 + ... + 2^n
     = [2^(n + 1) - 1] / (2 - 1) (sum of a geometric progression formula)

=> T(n) = O(2^(n + 1)) = O(2*2^n) = O(2^n)

Answer 2

您可以应用此处描述的主定理的第三种情况，因为 f(n) 等于 Ω(nloga)。

Here, 
f(n) = 2^n , and
Ω(n^log 1) = Ω(1)

2^n = Ω(1)，因为对于一些常数 c>0 且所有足够大的 n，2^n ≥ c*1。

所以 T(n) = f(n)
T(n) = O(2^n)