complexity-theory - 複雑さ - 計算方法

Question

以前にこれを尋ねた人もいるかもしれませんが、試してみます。

バブルソートでソートする配列があるとしましょう

そして（ソートを終えた後）それを（別の比較で）再度ソートして、

私の目的を達成します。

初めて使用したとき: O(n ² ) 。

2回目は O(n ² ) を使用しました。

== > O(n ² ) の複雑さで目的を達成しました。

または何か他のもの (O(n ³ ) または 2*O(n ² ) または私は何を知りません)

Answer 1

O(n ² ) + O(n ² ) = O(n ² ) 理論

初めて：

f ₁ (n) = O(n ² )

2回目：

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 ² )