如何计算选择排序的时间复杂度

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≤j≤n-1Σj≤i≤n orΣ0≤j≤n-2Σj+1≤i≤n-1

这将计算为渐近为O(n^2)的(n-1)(n/2)。

想要了解更多信息，我推荐这两本书，

用于算法设计和分析的

1. Introduction - Anany Livitin
2. Introduction to Algorithms - Coreman