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/

相关文章:

c# - 一维柏林噪声?

algorithm - 确定最长的连续子序列

data-structures - 基于像素的模式识别的数据结构

java - 我的方法的效率有问题。有什么建议吗?

algorithm - 如何判断一个图是否单连通?

algorithm - Radix Sort 是复杂算法 P 还是 NP 的一个例子?

java - 通过打印所有可能的方式递归硬币找零

c - 是否可以创建一个在编译时大小未知的结构?

algorithm - 这个函数的大Θ分析是什么?

algorithm - 二分查找运行时间上限 : Recurrence Relation