complexity-theory - 复杂性 - 如何计算

Question

我知道有些人之前可能会问过这个问题，但我会尝试的。

假设我有一个数组，我用冒泡排序排序

然后（在我完成排序之后）我再次排序（通过不同的比较）以便

达到我的目的。

我第一次使用： O(n ² ) 。

在我第二次使用： O(n ² ) 。

^{== > 我以 O(n 2} )的复杂度实现了我的目的。

或其他一些东西（O(n ³ ) 或 2*O(n ² ) 或者我不知道是什么）

Answer 1

O(n ² ) + O(n ² ) = O(n ² ) 在理论上

第一次：

f ₁ (n) = O(n ² )

第二次：

g ₁ (n) = O(n ² )

和：

f ₁ (n) + g ₁ (n) ⊆ O(n ² + n ² )
f ₁ (n) + g ₁ (n) ⊆ O(2n ² ) ⊆ O(n ² )

以下属性可能很有用：

另外，使用第一条规则：

O(n ² ) + O(n ² ) ⊆ O(n ² )