algorithm - 给出了三种算法的时间复杂度。对于大的 N 值，哪个应该执行最慢？

Question

给出的选项:

(a) O(2N)
(b) O(N)
(c) O(logN)
(d) O(n^2)

我在网上考试中遇到过这道题。他们提到的正确选项是 O(logN)。但是在我看来应该是O(2N)，因为他们给出的“n^2”，“n”是小写的，否则应该是O(N^2)。有人帮我找到正确的答案。

Answer 1

要比较复杂度 O(A(n)) 和 O(B(n))，您应该计算极限:

lim A(n)/B(n) = ?
  n->+Inf

您可以有三种可能的结果:

   0      A (infinitely) faster than B
+Inf      A (infinitely) slower than B
   v > 0  A~B; A is v times slower than B 

在你的情况下:

lim(n^2/2n) = lim(n^2/n) = lim(n^2/log(n)) = +Inf
  n->+Inf       n->+Inf      n->+Inf

这就是为什么 (d) O(n^2) 是(a)..(d) 算法中最慢 的算法。

最快 算法是(c) O(log(n))，(使用L'Hospital's rule 计算极限):

lim(log(n)/2n) = lim(log(n)/n) = lim(log(n)/n^2) = 0
  n->+Inf          n->+Inf         n->+Inf

最后，算法从最快到最慢排序:

(c) O(log(n)), (b) O(n), (a) O(2*n), (d) O(n^2)