获取选择排序的时间复杂度

Question

我创建了一个选择排序代码，但是我的老师问我代码的时间复杂度是多少，所以我需要帮助才能得到它。我不确定我的代码是否与其他选择排序相同，最坏时间为 O(n^2)，最佳时间为 O(n)。

代码：

def selection(collection):
for endnum in range(len(collection)-1, 0, -1):
    print(collection)
    max_idx = endnum
    if max(collection[0:endnum]) > collection[endnum]:
        max_idx = collection.index(max(collection[0:endnum]))
    collection[endnum], collection[max_idx] = collection[max_idx], collection[endnum]

Answer 1

您的代码与通常的选择排序具有相同的复杂度 O(n^2)，您只需从末尾而不是从头开始填充已排序的项目。

有 n-1 个循环，长度运行 n,n-1, n-2..1，因此等差级数的总和给出了大约 n*(n-1)/2 比较和 n 交换。

另请注意，选择排序的最佳时间情况是二次的，而不是线性的（选择排序不会检索信息以提前停止）

Answer 2

选择排序没有最佳情况。它总是O(n²)，因为每一步都需要在数组的未排序部分中找到最大（或最小）的元素，这需要扫描整个未排序的段。

您的版本没有什么不同，只是您不必要地计算最大值两次然后进行 第三次 扫描以找到它的索引。然而，做必要工作的三倍“只是”一个常数，所以渐近复杂度不会改变。不过，您浪费的周期是真实的。

获取选择排序的时间复杂度

Getting the time complexity of a selection sort

algorithm

selection-sort