搜索未排序數組

Question

未排序數組中可能有重複元素的最小和最大比較次數是多少？

據我所知，在未排序數組中找到任何東西都是O（n）問題。但是，如果數組也包含重複元素，這是真的嗎？

重複元素我的意思是，在給定數組中出現多次的元素。

Answer 1

作爲一般的經驗法則，當我們談論忽略像O（n）這樣的常數的漸近複雜性時，無論你有兩倍的工作量還是三倍的工作量都不重要。因此，問題是O（n）在這種情況下保持O（n）。

在這個特定的問題中，在未排序的數組中存在重複項不會加速搜索元素的過程。當然，如果元素是數組中的10倍，那麼您可能會發現它的平均速度快了10倍，但只要這不依賴於n，它並不會改變複雜性。

Answer 2

所以這裏的想法是，你必須從前到後走陣列，因爲它是未排序的。這意味着你正在看O（n） - 元素的線性遍歷。無論您正在搜索的位置是位置0，位置8還是位置n-1，您都必須走陣列才能找到它。

現在，如果數組中可能有重複，唯一的區別是您可能會發現該值的多個實例。如果你正在尋找所有這些或只是第一個，它仍然是一個O（n）的情況。重複項不會改變複雜性。

最好的情況 - 你找到它（假設你只需要找到一個）在第一次比較。

最壞的情況 - 沒有重複的給定值，它是你檢查的最後一個 - 第n比較。

如果您必須查找所有重複項，它總是會進行n次比較，因爲您必須訪問未排序數組中的每個元素。

Answer 3

即使存在重複元素，O(n)時間也是如此。你應該熟悉big-oh notation。

在最壞的情況下，考慮這個數組：1, 1, 1, 1, ..., 1, 1, 2。如果從第一個元素開始搜索2，那麼將會完全進行n比較，因此重複項目根本沒有任何幫助。如果你要搜索1，你會發現它在一個單一的比較，但有不同元素的輸入，如果你幸運的話，你也可以在單個比較中找到一個元素，所以重複確實不會意味着很多，除了你更有可能幸運並且以更少的步驟找到你的目標元素。但它仍然是O(n)。

幾乎總有最好的情況和最壞的情況。大多數算法的實際性能總是取決於給定的輸入，大哦表示法只會讓您對算法如何執行有一個模糊的概念。這並不是說漸近表示法是無用的，只是它並不總是完全準確，因爲涉及的基礎常量在實踐中會產生差異。

如果對性能有疑問，請運行您自己的基準測試。

Answer 4

什麼會在排序的數組 ，可能有重複的元素，以及最小和最大 數量比較？

如果您正在搜索一個指定的值，那麼最小和最大比較數將分別爲1和n。如果已知該值在數組中，並且您只查找它的位置，則可以通過n-1比較逃脫。

據我所知，發現任何在 未排序的數組是O（n）問題。但是，如果數組中還包含重複的 元素，那麼是否爲 ？

是的，它仍然是O（n）。

假設重複出現意味着平均搜索時間減半。那麼，這是一個很大的減少，但它不會影響O（n）的時間。大O不是一般的情況，這是最壞的情況，最壞的情況不會改變。無論如何，由一個常數因子劃分不會影響大O時間。

Answer 5

依我之見，應該是2N比較

for (int i=0; i<n; i++) 
    if (a[i]==ele) 
     break 
    else 
     continue; 

因此，有兩個比較(i<n)和(a[i]==ele)做過N次在最壞的情況下。因此2n比較。如果有什麼方法可以減少i<n，我不知道如何。

Answer 6

像其他人一樣，我同意一個包含沒有重複的未分類數組，窮舉線性搜索將是O（n）。

如果允許重複，則該算法僅在任何元素重複的概率均勻分佈的假設下保持爲O（n）。

如果存在描述重複元素分佈的不同概率密度函數，則根據概率密度函數，搜索算法可能會小於O（n）。