如何計算時間使用僞代碼選擇排序

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是陣列的長度）。所以第二和第三。我堅持第四步是否會發生n！時間或其他東西。

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≤Ĵ≤N-1Σj （n-1）（n/2），其漸近地爲O（n^2）。

欲瞭解更多信息，我會推薦這兩本書，

1. 介紹到設計和算法分析 - Anany Livitin

2. 算法導論 - Coreman