algorithm - 根据大 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 .

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

所以:

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

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