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

Question

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

algorithmtime-complexity

82

我的教授刚刚教了我们这样一个规则：任何将输入长度减半的操作，复杂度都可以用 O(log(n)) 来近似表示。为什么不是O(sqrt(n))呢？这两个复杂度不是等价的吗？

- white_tree

11

绘制 log(n) 和 sqrt(n) 的图形，最高到 n==1000，看看它们是否等价，无论您对此的意思是什么。 - High Performance Mark

2

log(1) = 0，sqrt(1) = 1 - Sung

10

抱歉，我不知道当时在想什么，虽然所有答案都非常有用。谢谢。 - white_tree

1

“log(n)”和“sqrt(n)”是否等价，仅相差一个常数因子？ - user207421

检查两个函数的相对增长的一般方法是取两个函数的比值的极限。如果极限值为无穷大，则分子增长得更快，如果极限值为零，则相反成立。如果极限值为某个常数，则函数的增长是可比较的。你可以考虑查看下面'Sandipan Dey'的回答。 - undefined

8个回答

38

假设采用自然对数（否则只需乘以一个常数），我们有：

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))。同时比较下面这些函数的增长情况，对于所有n>0，log n始终被sqrt(n)上界限制。

- Sandipan Dey

8

只需比较这两个函数：

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 . log(n) > log(log(n))

- Yousef

为了更好地理解可视化内容，请在WolframAlpha上绘图。 - shripal mehta

7

不，它们并不等价。

@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的对数。

- jbsu32

5

处理此问题的一种方法是比较O（）的增长率，和O（）的增长率。

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

因此，对于增大的n，是更好的选择。

- Gaurav Chawla

3

不，不是这样的。当我们处理时间复杂度时，将输入视为非常大的数字。因此，让n = 2^18。现在对于sqrt(n)个操作，操作次数将为2^9，而对于log(n)，它将等于18（我们在这里考虑以2为底的对数）。显然，2^9比18要大得多。因此，我们可以说O(log n)小于O(sqrt n)。

- androidGeek

3

不，它们不是等价的；你甚至可以证明这一点。

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

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

当谈论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) 在大的 n 时不是 0，两个函数都是连续可微的):

  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))

- Dmitry Bychenko

那么您是否认为如果矩阵乘法可以在O(n^2 log n)的时间内完成，那么ω w=2？我认为这在某种情况下是一种矛盾。您可以说w=2.00000000000001，但它不是2。当一个问题用n^k的形式表达时，它的解决方法可能是n^(k-1)log n，这很有趣。 - Gregory Morse

0

为了证明 sqrt(n) 比 lgn(base2) 快增长，您可以取第二个函数除以第一个函数的极限，并证明它在 n 趋近于无穷大时趋近于0。

lim(n—>inf) of (lgn/sqrt(n))

应用洛必达法则：

= lim(n—>inf) of (2/(sqrt(n)*ln2))

由于随着 n 的增加，sqrt(n) 和 ln2 会无限增加，而2是一个常数，这证明了

lim(n—>inf) of (2/(sqrt(n)*ln2)) = 0

- joshua.vw

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

它们并不相等：sqrt(N) 的增长速度比 log₂(N) 快得多。不存在常数C，使得对于所有大于某个最小值的N值，你都有sqrt(N) < C.log(N)。

一个简单的理解方法是，log₂(N)将会是接近于N的（二进制）位数，而sqrt(N)将会是一个数字，其本身的位数只有N的一半。或者，用一个等式来说明：

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

所以，你需要取sqrt(N)的对数(!)来将其降到与log₂(N)的同一复杂度级别。

例如，对于一个有11个二进制数位的二进制数，0b10000000000 (=2¹⁰)，平方根是0b100000，但对数仅为10。