根据 Big-O 复杂度对函数进行排序

Question

问题：按照 big-O 复杂度的升序对函数进行排序

1. f1(n) = (n^0.999999) log n
2. f2(n) = 10000000n
3. f3(n) = 1.0000001^n
4. f4(n) = n^2

我对这个问题的回答是：3、2、1、4（按递增顺序）基于我们可以忽略常量的规则。

但我在解决方案手册中找到的答案是：

这些函数的正确顺序是 f1(n)、f2(n)、f4(n)、f3(n)。

我无法理解这一点，谁能解释一下？如果有帮助，这里是解决方案的解释。

提前致谢！

Answer 1

以下事实揭示了排序：

1. O(n^k) > O(log(n))对于任何k > 0.
2. O(k^n) > O(n^b)对于任何k > 1.

这可能感觉违反直觉，因为1.0000001^n开始时非常缓慢，但我们在这里谈论的是渐近复杂性。指数增长虽然在实际场景中很慢，但在我们走向无穷大时主导着任何多项式增长。多项式增长大于对数增长也是如此。

所以：

• f3(n)，指数增长的复杂度最高。
• f4(n) 大于 f2(n) 和 f1(n) 是很明显的。
• f1(n) vs f2(n) - 考虑它们n^0.999999 * lognvs n^0.999999 * n^0.000001。所以决定这里比较的是lognvs n^0.000001。正如我们在事实 (1) 中所说的，多项式增长 > 对数增长。所以 f2(n) > f1(n)。

结合结果，我们有O(f1(n)) < O(f2(n)) < O(f4(n)) < O(f3(n)).