擬似コードを使用して選択ソート選択の一種

Question

時間の複雑さ（最悪の場合）の時間計算量を計算する方法：

'Selection-Sort(A) 

1 For j = 1 to (A.length - 1) 

2 i = j 

3 small = i 

4 While i < A.length 

5  if A[i] < A[small] 

6  small = i 

7  i = i + 1 

8 swap A[small], A[j] 

まずステップは、n-1回発生（nは配列の長さである）されます。だから2番目と3番目。それが起こるかどうか私は4番目のステップで立ち往生しています！何か他の何か。

Answer 1

このアルゴリズムの基本的な操作は、内部ループの5行目での比較です。両方のループは≒n回実行され、すなわち基本動作はn * n回≒n^2回実行される。

選択ソートの時間の複雑さはO（n^2）です。最悪の場合と平均の場合で同じです。

下のリンクをクリックすると、選択のソートについての良い説明が表示されます。 https://www.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort

これが役に立ちます。

編集：

非再帰的アルゴリズムの時間複雑さを分析、

• が
• の数を示す合計値を設定
基本的な動作を識別し、入力サイズを示すパラメータを決定基本操作が実行される回数
• 成長順序を設定する
• この場合には入力サイズは、アレイのサイズになり、基本的な動作は、比較のある漸近推定に

を与え、算術和は次のようになり、

Σ1≤のj個の≤n-1ΣJ 1≦i≦n-1

これは、漸近的にO（n^2）である（n-1）（n/2）と評価される。私ははじめに設計し、アルゴリズム解析する

1. 、これら二冊の本をお勧めします詳細については

   - Anany Livitin

2. アルゴリズム入門 - Coreman