时间戳

首页 > 解决方案 > 根据时间复杂度排列函数

algorithm - 根据时间复杂度排列函数

问题描述

将以下代表运行时间的函数从最小到最大排序（根据相对于 n 的增长率），并将那些在同一等价类中的函数分组

函数列表

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

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

标签： algorithmfunctiontime-complexitydiscrete-mathematics

解决方案

复杂性如下：

  • 2 3 +12n 2 +5 = O( 3 )
  • 8(log) 2 = O(log 2 )
  • 1.5= O(1.5)
  • 4 −12 3 = O( 4 )
  • 4 3对数 = O( 3对数)
  • 4 3 = O( 3 )
  • ！= O（！）
  • 7+6 = O()

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

  • O(log 2 )
    • 8（日志）2
  • O()
    • 7+6
  • O( 3 )
    • 2 3 +12n 2 +5
    • 4 3
  • O( 3对数)
    • 4 3日志
  • O( 4 )
    • 4 −12 3
  • O(1.5)
    • 1.5
  • 哦（！）
    • ！

因此，您的输出本质上存在一个区别： O( 3 log) 不是 O( 3 )：第一个是更大的顺序：

我们可以用反证法来证明这一点。如果我们暂时假设 O( 3 log) 是 O( 3 )，那么我们可以找到一个0和一个满足3 log ≤ 3的所有 > 0的 a 。但这意味着 log ≤ 或 ≤ 2. 这对于任何 > 2 都不成立，所以命题不成立。

另一个更正：标签“指数”和“因子”在您的输出中被反转。

O(!) 是阶乘且 O(1.5) 是指数的。

推荐阅读