查找时间复杂度大-Θ此递归公式涉及底函数

Question

我试图找到这个算法的时间复杂度(大-Θ):

Recursion(n):
while n > 1:
n = floor(n/2)
Recursion(n)

通过考虑n是2的幂的最坏情况，我找到了O(n)的上界。

然而，我很难找到一个下界(大-Ω)。我的直觉是，这是Ω(n)，以及，但我不确定如何显示它与底函数的方式。

有什么建议吗?谢谢你！

编辑:我不相信的主要事情是T(n/2)等于T((n/2))。如何证明这个算法呢?

Answer 1

floor函数在常数时间内执行操作，O(1)。因此，你可以忽略它/将其视为常数。下面我们来分析一下算法的时间复杂度:

T(n) = T(n/2) + 1 (floor operation)
T(n/2) = T(n/4) + 1
...
T(2) = T(1) + 1    --> T(1) = constant
T(n) = T(n/4) + 2
T(n) = T(n/8) + 3
...
T(n) = T(n/2^k) + k    2^k = n therefore k=log(n)
T(n) = T(1) + log(n)
T(n) = log(n)

我们可以得出T(n)∈θ(log(n))。