时间戳

首页 > 解决方案 > 递归方法中的大 O 复杂度

algorithm - 递归方法中的大 O 复杂度

问题描述

2 的幂在f(n) = f(n/2) + 1哪里，n(n >= 2)

与f(1) = 1,

会不会

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

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

标签： algorithmrecursionbig-ocomplexity-theorylogarithm

解决方案

两种方法：

(1) 可以使用归纳法：

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

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

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

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

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

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

推荐阅读