求这个涉及floor函数的递归公式的时间复杂度Big-Θ

Question

我正在尝试找出该算法的时间复杂度 (Big-Θ)：

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

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

但是，我无法为此找到下限 (Big-Ω)。我的直觉是这也是 Ω(n)，但我不确定如何用 floor 函数来显示它。

有什么建议吗？谢谢！

编辑：我不相信的主要事情是 T(n/2) 等价于 T(floor(n/2))。如何用这个算法证明这一点？

Answer 1

floor 函数在恒定时间内执行其操作，O(1)。因此，您可以忽略 it/see 它作为常量。下面分析一下算法的时间复杂度：

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)).

求这个涉及floor函数的递归公式的时间复杂度Big-Θ

Finding time complexity Big-Θ of this recursive formula involving floor function

algorithm

recursion

big-o

time-complexity

floor