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

标签 algorithm data-structures big-o

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

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

谢谢

最佳答案

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 偶数, 乘以一次。

关于algorithm - BigOh 符号 O(log n) 何时出现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9940819/

相关文章:

javascript - 位操作设计

algorithm - 在一组 100 万个数字中找到一个唯一数字的有效算法是什么?

Python 类次调度优化

c++ - 以 O(log(n)) 复杂度改变二叉堆元素的优先级

python - 此 2 的幂函数的 "Big O"

数据库同步算法建议

c++ - 插入排序错误

c++ - 我不知道如何存储表示为字符串的大量大数字

algorithm - 用对数证明算法

javascript - 当用作哈希时,JavaScript 数组的大 O 是什么?