我在測驗中有這個問題，我試圖理解它：
假設 Bubblesort() 是 Bubble Sort 演算法的最優化版本，這個函式的時間復雜度（在最壞的情況下）是多少？
def MultSort(a,n):
for i in range(n):
BubbleSort(a)
選項是：
- 線性
- 二次方
- 立方體
我在想第一種（因為這是最壞的情況）O(len(a)^2)，然后n*O(len(a))一旦訂購。但我自己無法真正得到結果
uj5u.com熱心網友回復：
這個練習中令人討厭的事情是，可供選擇的答案并沒有表明變化的維度是什么，復雜性將是線性的、二次的或三次的。有兩個明顯的候選者：len(a)和n。由于在練習中沒有區分，也沒有給出關于兩者之一是否被假定為常數的資訊，你最好的猜測是假設它們是相等的（n = len(a)）。
我們可以猜測它n是作為單獨的引數給出的，因為相同的函式簽名將用于沒有等效len()函式的語言中，例如 C 陣列。
無論如何，假設n = len(a)，這就是我們可以說的：
第一種（因為這是最壞的情況）將是 O(len(a)^2)
是的，或者換句話說：O(??2)
然后 n*O(len(a)) 訂購后。
是的，或者換句話說：??O(??) = O(??2)
但我真的無法得到結果......
最后一步是添加您分析過的這兩個階段，所以這里有一個劇透，以防您看不到如何添加它們：
O(??2) O(??2) = O(??2)
...這意味著分析器是：
二次
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508722.html