复杂度O(log(n))是否等于O(sqrt(n))？

Question

我的教授刚刚告诉我们,任何将输入长度减半的操作都有一个O(log(n))复杂度作为拇指规则.为什么不是O(sqrt(n)),它们都不是等价的？

Answer 1

它们不等价:sqrt(N)将比log ₂(N)增加更多.没有恒定Ç所以,你将不得不SQRT(N)<C.log(N)为的所有值Ñ比一些最小值大.

一个简单的方法来抓住这个,是日志₂(N)将接近的(二进制)位的数量的值Ñ,而SQRT(N)将是一个数,其具有自身的位数的一半数量的Ñ具有.或者,说明平等:

        log ₂(N)= 2log ₂(sqrt(N))

因此,您需要使用sqrt(N)的对数(!)将其降低到与log ₂(N)相同的复杂度.

例如,对于具有11位数的二进制数,0b10000000000(= 2 ¹⁰),平方根为0b100000,但对数仅为10.

Answer 2

假设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 3

不，这不是等价的。

@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.It 那么它的复杂度为O(logB(n))

N:B: O(logB(n))B基于均值的对数n

Answer 4

只需比较两个函数：

sqrt(n) ---------- log(n)
n^(1/2) ---------- log(n)

Plug in Log
log( n^(1/2) ) --- log( log(n) )
(1/2) log(n) ----- log( log(n) )

很明显：const 。日志（n）>日志（日志（n））

Answer 5

解决该问题的一种方法是比较 O()
和 O(）

1. 

2. 

随着 n 的增加，我们看到 (2) 小于 (1)。当n = 10,000时 ，eq--1等于0.005，而eq--2等于0.0001

因此 n 越大越好。