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

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是数组的长度）。所以第二个和第三个。我坚持第 4 步是否会发生 n！时间或其他。

Answer 1

该算法的基本操作是第 5 行的比较，在内循环中。两个循环都执行了≈n次，即基本操作执行了n*n次≈n^2.

选择排序的时间复杂度为O(n^2)。对于最坏的最好的和平均的情况是一样的。

您应该看看下面的 link，它很好地概述了选择排序。 https://www.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort

希望对您有所帮助。

编辑：

在分析非递归算法的时间复杂度时，

• 确定指示输入大小的参数
• 识别基本操作
• 设置一个表示基本操作执行次数的总和
• 确定其增长顺序
• 给出渐近估计

在这种情况下，输入大小将是数组的大小，基本操作是比较，算术和是，

Σ1≤j≤n-1Σj≤i≤n或Σ0≤j≤n-2Σj+1≤i≤n-1

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

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

1. 算法设计与分析导论-Anany Livitin

2. 算法导论 - Coreman