1樓：猥瑣的民工
快排無論你用什麼方法選基點，在運氣最倒霉的情況下，也就是每次選基點都剛好碰上區間內的最大或最小值的時候，複雜度提高為O(n^2)是必然會發生的。儘管這種情況發生的概率極低，大約是1/(n!)，但在你重複測試了n!
次之後很可能會發生一次。
2樓：TravorLZH
對於某一種情況下（好/壞/平均）的時間複雜度 ，記號僅僅有這些意義：
所以請不要把這些記號和時間複雜度的最壞、最好、平均混淆。
3樓：寨森Lambda-CDM
以下說法都是正確的說法。如果題主真的明白了以下的每一條，你的疑問自動打消。
快排的時間複雜度是
快排的時間複雜度是
快排的時間複雜度不是快排的最好時間複雜度是
快排的最好時間複雜度是
快排的最好時間複雜度是
快排的平均時間複雜度是
快排的平均時間複雜度是
快排的平均時間複雜度是
快排的最壞時間複雜度是
快排的最壞時間複雜度是
快排的最壞時間複雜度是
4樓：衝上雲霄
平均時間複雜度θ(nlogn)，最好和最壞時間都是nlogn，首先你這麼理解就是錯誤的，比如乙個函式f(x)=x，如果x從0開始且是整數到n，平均值是n/2，難道最好最壞是n/2嗎？？你理解就錯了，兄弟，人家裡面說的是函式，到你這程式設計平均了，這都是倆概念了。
關於有限覆蓋定理還是有點不懂，為什麼只能對閉區間適用呢？
William 如果是開區間，假設為 0,1 則H 是它的乙個無限開覆蓋，無論n取多大，總存在乙個區間 0，1 n 不被覆蓋。而如果是閉區間，假設為 0,1 則H 是它的乙個無限開覆蓋，不論n取多少，總存在乙個區間能完全覆蓋 0,1 所以對於開區間，對從區間內逼近的這種無限覆蓋，不能取有限覆蓋。 理...
小白問題，關於演算法複雜度，為什麼要省略n前面的常數？
龍陽桑 可以用修路來理解。所謂的複雜度實際上理解為個人修路的速度。1個人1天修10公尺。10個人1天修了10公尺。現在你說10個人修的速度比1個人修的快，是1個人修的10倍。結論自然是正確的。但是意義何在？所以這裡顯然比較1個人的修路效率才是我們真正要的東西。這裡我們可以看到在10人團隊中，每個人也...
為什麼剛入門的程式設計師沒有感覺到演算法和資料結構的重要性？
hzldds2020 演算法和資料結構屬於內功了，太多的人想的是怎麼把功能做出來就好了，並不會糾結於細節。對於剛入門的程式設計師而言，有太多的東西都半生不熟，而且大多數程式設計師在工作中也很少需要去解決演算法和資料結構的問題。而且有太多的工具庫可以用了，比如List Set Map大多數語言都實現好...