今天，我的演算法老師給了我一個小練習，介紹了計算成本。代碼如下：
A = [8,7,6,5,4,3,2,1]
for y in range (0, len(A)):
el = A[y]
i = y-1
while i >= 0 and A[i] > el:
A[i 1] = A[i]
i = i-1
A[i 1] = el
無需浪費您的時間：它是一種采用陣列并對其進行重新排序的演算法。我必須找出 O 的順序。考慮到所有賦值操作都使用 1 作為成本，“最重”的行是 for 和 while。如果 for 回圈的數量級為 O (n) 且 n = len (A) 我不知道如何計算 while。最壞的情況它運行 28 次，但我找不到與陣列長度的相關性。有人能幫我嗎？提前謝謝了。
uj5u.com熱心網友回復：
對于給定的輸入，條件A[i] > el在被評估時將始終為真，因為每個下一個值el都小于所有前面的值A[i]。所以輸入確實觸發了最壞情況的執行。
然后，每次外部回圈進行迭代時，內部回圈的 if 執行次數都會增加 1：
0
1
2
3
...
n-1
所有這些的總和是一個三角形數：n(n-1)/2，即 O(n2)
uj5u.com熱心網友回復：
while 回圈在它之前的子陣列中插入A[y]（對于 some y）A[0..y-1]。正如您可以驗證的，當在增加時執行時y，這會A[0..y]排序。ywhile 回圈的成本與插入點之間的距離成正比。充其量，這個距離總是1（A[y]已經到位）；在最壞的情況下，它是y（A[y]應該先出現，就像給定的輸入一樣）；平均而言，y/2均勻分布。
因此，在全球范圍內，排序是最好的Θ(n)，但最壞的也是平均的Θ(n2)。（不超過 . 的整數之和n。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/517805.html
標籤：Python算法排序