您能解释一下是什么让算法成为 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/