我創建了一個選擇排序的代碼，但是我的老師問我代碼的時間復雜度是多少，所以我需要幫助才能得到它。我不確定我的代碼是否與其他選擇排序相同，最壞時間情況為 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]
uj5u.com熱心網友回復：
選擇排序沒有最好的情況。它總是 O(n2)，因為每一步都需要在陣列的未排序部分中找到最大（或最小）的元素，這需要掃描整個未排序的段。
您的版本沒有什么不同，只是您不必要地計算最大值兩次，然后進行第三次掃描以找到它的索引。然而，做三倍于必要的作業“只是”一個常數因素，所以漸近復雜度不會改變。但是，您浪費的周期是真實的。
uj5u.com熱心網友回復：
您的代碼與通常的選擇排序具有相同的復雜性 O(n^2)，您只需從末尾而不是從開頭填充排序專案。
有n-1運行長度的回圈n,n-1, n-2..1，所以算術級數的總和給出了n*(n-1)/2比較和n交換。
另請注意，選擇排序的最佳時間情況是二次的，而不是線性的（選擇排序不會檢索資訊以提前停止）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417236.html
標籤：