排序算法的上界和下界

Question

這是一個非常簡單的問題，但我很努力地完全理解這個概念。

我想了解以下語句之間的區別：

1. 存在着這種種在最好的情況下n個數的O（n）的陣列的算法。
2. 在最佳情況下，每種算法都會對O（n）中的n個數字進行排序。
3. 在最佳情況下，存在一種算法，可以在歐米茄（n）中對n個數字進行排序。
4. 在最佳情況下，每種算法都會對歐米茄（n）中的n個數字排序。

我會先解釋一下讓我發瘋的原因。我不確定關於1和3 - 但我知道其中一個答案是正確的，只需指定一個案例，而另一個答案是正確的，通過檢查所有可能的輸入。因此，我知道其中的一個必須是正確的，只需指定數組已被排序，但我無法分辨哪個數組已被排序。 我的老師總是讓我想想，就像我們正在研究誰是班上最高的人，又是由這些選項之一一樣（1,3），這足以說他是，而且沒有理由去檢查所有的班級。

我知道，如果我們要檢查最壞的情況，那麼這些陳述都不是真的，因爲沒有任何假設或額外內存的最佳排序算法是Omega(nlogn)。

重要注意事項：我不是在尋找一種解決方案（一種能夠進行匹配排序的算法） - 只是試圖更好地理解這個概念。

謝謝！

Answer 1

顯然，區別在於「O」和「Omega」。一個人說「上升不及」，第二個說「上升不慢」。

請確保您理解這些術語之間的差異，並且您會看到句子中的差異。

1和3都表示完全不同的東西，就像2和4一樣。

看看那些（這些都是不一樣的！）：

1〜存在一種算法，用於10個項目沒有在最好的情況下需要超過30。
3〜存在一種算法，對於10個項目在最佳情況下不會少於30個。

2〜在最好的情況下，10個項目的每一個算法都不超過30個。
4〜在最好的情況下，對於10個項目的每個算法都需要不少於30個。

你現在感覺不同嗎？與O/Omega的區別是相似的，但調查對象不同。上面的例子說明了某些點/情況下的不同表現，而O/Omega表示法告訴你關於數據大小的性能，但只有在數據「足夠大」的情況下，不管它是三項還是三項，它下降常數因子：

function 1000000*n is O(n) 
function 0.00000*n*n is O(n^2) 

對於少量數據，第二個顯然比第一個非常好。但隨着數據量的增加，很快第一個開始好多了！

重寫上面的例子變成「更合適的」而言，這更類似於原來的句子：

1〜存在一個算法，對於超過N個項目，不佔用超過X * N在最好的情況下。
3〜存在一種算法，對於多於N個項目，在最佳情況下不會少於X * n。

2對於N個以上的項目，在最佳情況下不超過X * N的每種算法。
4〜對於多於N個項目，在最佳情況下不得少於X * N的每個算法。

我希望這可以幫助你「看」/「感覺」的區別！

Answer 2

對於1 + 3問自己 - 你知道的算法，可以在Theta(n)排序在最好的情況下一個數組 - 如果答案是真的，那麼這兩個1 + 3是真實的 - 因爲西塔（n）是O(n) [intersection] Omega(n) ，因此如果你確實有這樣的算法（以Theta（n）最好的情況下運行） - 1 + 3都是正確的。
提示：優化bubble sort。

對於2：問自己 - 每種算法是否對O(n)最佳情況下的一組數字進行排序？你知道一個算法的最壞情況和最好情況下的相同時間複雜度嗎？如果您關閉所有優化，那麼所提到的冒泡排序會發生什麼？

對於4：問問你自己 - 你是否需要讀取所有元素以確保數組被排序？如果你這樣做 - Omega(n)是一個明確的下界，你不能再好了。

祝你好運！