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

Question

Question: Sort the functions in increasing order of big-O complexity

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（递增顺序） 基于我们可以忽略常量的规则。

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

The correct order of these functions is f1(n), f2(n), f4(n), f3(n).

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

Answer 1

以下事实揭示了顺序：

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

这可能会让人觉得 counter-intuitive，因为 1.0000001^n 开始时真的很慢，但我们在这里谈论的是渐近复杂性。指数增长虽然在实际情况下很慢，但随着我们趋向无穷大，它会主导任何多项式增长。多项式增长大于对数增长也是如此。

所以：

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

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