複雜度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))