复杂度O（log（n））是否等于O（sqrt（n））？

Question

我的教授刚刚告诉我们，任何将输入长度减半的操作都具有O（log（n））复杂度作为拇指规则。为什么它不是O（sqrt（n）），它们都不是等价的吗？

Answer 1

他们是不等价的：的sqrt（N）会增加很多超过日志（N）。没有常数C因此，对于所有N大于某个最小值，您将具有sqrt（N）< C.log（N）。

一种简单的方法来抓住这个，是日志（N）将是一个值接近的Ñ（二进制）位的数量，同时SQRT（N）将是一个号码本身的一半数字N有。或者，指出与平等：

        日志（N）= 2log （开方（N））

所以，你需要采取的对数（！ ）的sqrt（N），以使其降至与相同的复杂顺序log （N）。

例如，对于有11个数字，0b10000000000（= 2 10 ）一个二进制数，的平方根是0b100000，但对数仅为10

Answer 2

没有，它不等价的。

@trincot在他的回答中给出了一个很好的解释。我再加一点。你的教授教你的

any operation that halves the length of the input has an O(log(n)) complexity 

这也是事实，

any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity 
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity 
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity 
So on ... 

这是所有还原(B-1)/Bth.输入的长度甚至真的，那么它具有的O(logB(n))

N:B:O(logB(n))复杂表示B基于对数n

Answer 3

假设natural logarithm（否则只是乘以一个常数），我们有

lim {n->inf} log n/sqrt(n) = (inf/inf)

     = lim {n->inf} 1/n/1/(2*sqrt(n)) (by L'Hospital) 
         = lim {n->inf} 2*sqrt(n)/n 
         = lim {n->inf} 2/sqrt(n) 
         = 0 < inf 

参见https://en.wikipedia.org/wiki/Big_O_notation用于O(.)替代认定中并从上方从而我们可以说log n = O(sqrt(n))，

而且比较以下功能的增长，log n始终以sqrt(n)为大n的上限。

Answer 4

不，他们不相当于;你甚至可以证明

O(n**k) > O(log(n, base)) 

的（在sqrt情况下k = 1/2）任何k > 0和base > 1。

当O(f(n))交谈我们要调查的行为大n， 限制是好手段。假设两个大O是等价的：

O(n**k) = O(log(n, base)) 

，这意味着有一个有限的一些常量C这样

O(n**k) <= C * O(log(n, base)) 

不够n一些大的开始;把它放在其他方面（log(n, base)不是0从大n开始，这两个功能是连续可微）：

lim(n**k/log(n, base)) = C 
    n->+inf 

要找出限制的值，我们可以使用L'Hospital's Rule，即求导的分子和分母，将它们划分：

lim(n**k/log(n)) = 

    lim([k*n**(k-1)]/[ln(base)/n]) = 

    ln(base) * k * lim(n**k) = +infinity 

所以我们可以得出结论，有没有不断C这样O(n**k) < C*log(n, base)或者换句话说

O(n**k) > O(log(n, base))