复杂度 O (log (n))等价于 O (sqrt (n))吗？

我的教授刚刚告诉我们，任何将输入长度减半的操作都有一个 O (log (n))复杂度作为经验法则。为什么不是 O (sqrt (n)) ，它们不是等价的吗？

111660 次浏览
小开
最佳答案

它们不是等价的: Sqrt (N)的增长速度比 Log < sub > 2 (N)快得多。没有常量 C，所以对于大于某个最小值的所有 N值，都应该有 Sqrt (N) < C.log (N)。

掌握这一点的一个简单方法是，Log < sub > 2 (N)将是一个接近于 N的(二进制)数字数的值，而 Sqrt (N)将是一个数字，其本身的数字数量只有 N的一半。或者，以平等的方式陈述:

Log < sub > 2 (N) = 2log < sub > 2 (sqrt (N))

所以你需要取对数(!)将 Sqrt (N)的复杂度降低到与 Log < sub > 2 (N)相同的复杂度。

例如，对于具有11位数字的二进制数0b1000000000(= 210) ，平方根是0b100000，但对数只有10。

小开

不，这不是等价的。

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

小开

假设自然对数(否则只乘以常数) ，我们有

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

enter image description here

小开

不，它们是 没有的等价物; 你甚至可以证明这一点

   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

为了求极限的值，我们可以使用 医院守则，也就是对分子和分母求导，然后除以:

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

不，不是的。 当我们处理时间复杂性时，我们认为输入是一个非常大的数字。我们取 n = 2 ^ 18。现在对于 sqrt (n) ，操作数是2 ^ 9，对于 log (n) ，操作数等于18(我们在这里考虑以2为基数的 log)。显然2 ^ 9比18大得多。 所以，我们可以说 O (logn)小于 O (sqrtn)。

小开

比较一下这两个函数:

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

很明显: < em > const. log (n) > log (log (n))

小开

解决这个问题的一种方法是比较 O (< img src = “ https://i.stack.imgur.com/KfHDK.png”alt = “ sqrt (n)”/>)的生长速率
O (< img src = “ https://i.stack.imgur.com/vb49G.png”alt = “ log (n)”/> < img src = “ https://i.stack.imgur.com/vb49G.png”alt = “ log (n)”/> )

  1. derivative of sqrt n

  2. enter image description here

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

因此，随着 n 的增加，< img src = “ https://i.stack.imgur.com/Txnre.png”alt = “ log (n)”/> < img src = “ https://i.stack.imgur.com/Txnre.png”alt = “ log (n)”/> 更好。

小开

为了证明 sqrt(n)比 lgn(base2)增长得更快，你可以取2的极限大于1，并证明它接近0，因为 n 接近无穷大。

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

应用 L’霍普特斯规则:

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


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

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

提交答案