递归方法的复杂性很大

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=2) 因此，它是常数，o(log2)=o(1)

--->如果n为真，那么下一个值(由于n是2的幂，因此为2n)应该为真：

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

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

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

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

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

右侧_边_方程：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

用CCD_ 8。

看到没什么大不了的

g(m) = m + 1

这意味着

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

这就是确切的解决方案。