递归方法中的大O复杂度

Question

对于 f(n) = f(n/2) + 1 其中 n 是 2 (n >= 2) 的幂，

与f(1) = 1、

会不会

f(n) = O(logn),
f(n) = O(loglogn),
or
f(n) = O(sqrt(logn))

我相信这是第一个，但我不确定如何验证。

Answer 1

两种方法：

(1) 你可以使用归纳法：

假设 O(logn) 是正确的，那么我们应该显示：

---> 对于 n=1：它是真的 => f(2) = f(1) + 1 = 1（f(1) 为零，因为 n>=2）所以，它是常量o(log2) = o(1)

---> 如果 n 为真，则下一个值（为 2n，因为 n 是 2 的幂）也应为真：

因此，我们假设 O(logn) 对于 f(n) = f(n/2) + 1

为真

现在，我们应该看看它是否仍然适用于：

f(2n): f(2n) = f(n) + 1 => O(log2n) = O(logn) + 1

所以，我们可以再次看到它是正确的。因为，对于大 n，我们有：

Left_side_of_equation: O(log2n)=O(logn + 1) = O(logn)

Right_side_of_equation: O(logn)+1 = O(logn)

============================================= ==

(2)二叉查找树概念：

如果你了解二叉搜索树，那么这个公式显示了一个可以基于二叉搜索树的算法的计算时间。所以，每一层的计算时间取决于它的子层（我的意思是它下面的一层）。并且，在每一层，添加的计算时间为 O(1)。因此，在二叉搜索树中，由于您有 Logn 层，因此您总共将拥有：Logn * o(1) 复杂度，即 O(logn)。

Answer 2

如果n是2的幂，我们可以写成n = 2^m。重复读取

f(2^m) = f(2^(m-1)) + 1

可以看作

g(m) = g(m-1) + 1

与 g(0) = 1.

看到这个没什么大不了的

g(m) = m + 1

这意味着

f(n) = log2(n) + 1.

这是精确解。

递归方法中的大O复杂度

Big O complexity in recursive method

algorithm

recursion

complexity-theory

big-o

logarithm