time-complexity - 排序增长函数

Question

按从最有效到最复杂的顺序列出以下增长函数：

1. nlog ² (n)+n ²
2. n ² -nlog(n)
3. nlog(n)
4. n ²对数（n）
5. 2 ⁿ +100 n ⁴
6. n ³ -100 n ²

我知道该功能被 n 的压倒性功能认为是最有效或最复杂的。但是，当有多个日志引用时，我不确定如何进行。

我知道 (5) 是最复杂的，因为它具有指数 n 并且会以指数方式增加。(6) 复杂度落后，因为它是多项式。

现在我的困惑来了。我认为 (1) 会出现在 6 之前，因为它的 n ²值被添加到 log 函数中。然后（2）作为对数函数被减去。然后 (4) 相乘。这使得 3 成为最有效的双对数。

我的猜测，从最复杂到最有效：
3
4
2
1
6
5

这是接近正确的地方还是我在左场？

Answer 1

记住 log(n) ^a ∈ O(n) for all a。您可以使用它将所有给定函数放入多项式/指数类别：

1. n ² + n•log ² (n) ∈ O(n ² )
2. n ² − n•log(n) ∈ O(n ² )
3. n•log(n) ∈ O(n•log(n)) ∈ O(n ² )
4. n ² •log(n) ∈ O(n ² •log(n)) ∈ O(n ³ )
5. 100n ⁴ + 2 ⁿ ∈ O(2 ⁿ )
6. n ³ − 100n ² ∈ O(n ³ )

现在您知道 {1,2,3} < {4,6} < 5。

在{1,2,3}内，n•log(n)是最小的，因为它是< n^2。显然n^2 - x< n^2 + y，所以 2 小于 1。

在{4,6}内n^2•log(n) = n•n•log(n) < n•n•(n-100) = n^3-100n^2，因为log(n) < n-100对于大 n。

所以正确的顺序是 3 < 2 < 1 < 4 < 6 < 5。

Answer 2

只是总是试图找到增长最快的函数：顺序是 n^n >> n！>> a^n >> n^a >> n*log(n) >> n >> log(n) >> log(log(n))。如果将这些函数相乘，同样 n*log(n)*log(n) 比 nn*log(n) 增长得快，因此顺序为：nlog(n) < n^2-nlog(n) < nlog^2(n) + n^2 < n^2log(n) < n^-100n^2。虽然我会说 n^2-nlog(n) 类似于 nlog^2(n) + n^2) 因为增长最快的是 n^2 所以实际上日志并不有趣。