什么时候出现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.否则exponentiate a^(n/2)= B(大小为n/2的问题),乘b通过b,并且如果n为偶数,通过一次相乘.