根据时间复杂度排列函数

Question

将代表 运行 次的下列函数从小到大排序（根据 相对于 n) 的增长率并将具有相同等价性的那些函数分组 class

函数列表

2n^3+12n^2+5, 
8(log n)^2, 
1.5^n, 
n^4-12n^3, 
4n^3(log n), 
4n^3, 
n!, 
7n+6

My solution in ascending order is :
8(log n)^2 - logarithmic complexity
7n+6       - linear complexity
2n^3+12n^2+5, 4n^3(log n), 4n^3 - polynomial complexity
n^4-12n^3 - polynomial complexity
1.5^n - Factorial complexity
n! - Exponential complexity

不确定我所做的是否正确。任何反馈将不胜感激。

Answer 1

复杂度如下：

• 2³+12n²+5 = O(³)
• 8(log)² = O(log²)
• 1.5 = O(1.5)
• ⁴−12³ = O(⁴)
• 4³log = O(³log)
• 4³ = O(³)
• ！ = O(!)
• 7+6 = O()

按复杂性分组并按升序排列时：

• O(log²)
  • 8（对数）²
• O()
  • 7+6
• O(³)
  • 2³+12n²+5
  • 4³
• O(³log)
  • 4³log
• O(⁴)
  • ⁴−12³
• O(1.5)
  • 1.5
• 哦（！）
  • !

所以你的输出本质上有一个区别：O(³log) 不是 O(³)：第一个是更高阶的：

我们可以用反证法证明这一点。如果暂时假设 O(³log) 是 O(³)，那么我们可以找到 ₀ 并且 ³log ≤ ³ 对于所有 > ₀。但这意味着 log ≤ 或 ≤ 2。这对任何 > 2 都不成立，因此该命题不成立。

另一个更正：输出中的标签“指数”和“阶乘”颠倒了。

O(!) 是阶乘，O(1.5) 是指数。