algorithm - BigOh 符号 O(log n) 何时出现？

Question

您能解释一下是什么让算法成为 O(log n) 吗？

如果您能用简单的代码展示它，我将不胜感激。

谢谢

Answer 1

log(n)/log(i)是递归关系的解

f(n) =  f(n/i) + c

每次你遇到一个可以写成递归调用的函数，其中输入的大小在每次迭代中除以一个常量。类似

function(input, N){
   do some constant work
   return function(input, N/c);
}

然后你有一个 Theta(logn) 复杂度。

例子:

• 当您在平衡搜索树中搜索时:取大小为 n 的树，如果等于根返回(常量)，或者如果较小(大小为 n/2)则在左子树中搜索，在右子树中搜索(尺寸 n/2)如果更大。
• 指数 a^n:如果 n = 1，则返回 a。否则求幂 a^(n/2) = b(大小为 n/2 的问题)，将 b 乘以 b，如果 n 偶数, 乘以一次。