如果演算法必須進行 n-1 比較才能找到某個元素，那么我們可以假設演算法的最佳運行時間是 O(n) 嗎？我知道排序演算法的下限是 nlogn 但由于我們只回傳找到的一個元素，我認為在運行時間方面可以做得更好嗎？謝謝！
uj5u.com熱心網友回復：
要在未排序的串列中找到某個元素，您需要 O(n)。
但是如果你對陣列進行排序（通常需要 O(n log n)），你可以在 O(log n) 中找到某個元素。
因此，如果您想經常在同一個串列中查找元素，則很可能值得對串列進行排序，以便能夠更有效地查找元素。
uj5u.com熱心網友回復：
如果您的陣列未排序并且您在其中找到一些元素，那么在最壞的情況下，線性搜索演算法進行 n-1 比較，時間復雜度將為 O(n)。
但是，如果您想降低時間復雜度，那么首先對陣列進行排序并使用二進制搜索演算法，在最壞的情況下需要O(logn) 。
所以二分搜索演算法比線性搜索更有效。
uj5u.com熱心網友回復：
對于未排序的元素，最壞的情況是您必須遍歷所有元素，即 O(N)。如果您需要許多查找，那么您有幾個預處理選項可以加速所有未來的訪問。
選項 1：將元素放入標準哈希表中。創建哈希表的平均成本為 O(N)，之后每次查找平均花費 O(1)。這假設可以為這種型別的元素創建一個合理的散列函式。
大多數語言/庫都實作了基于桶的哈希表，在病態的情況下，它可以將所有元素放在一個桶中，每次查找的成本為 O(N)。
選項 2：還有其他不受病態 O(N) 情況影響的哈希表實作。羅賓漢散列（維基百科）（更多在Programming.Guide中）保證在最壞情況下的 O(log N) 查找，平均為 O(1)。
選項3：另一種選擇是將O（N log N）中的元素排序一次，然后使用二進制搜索在O（log N）中查找。通常這比 Robin Hood 散列（選項 2）慢。
選項 4：如果值是范圍有限的簡單整數，最大最小值在 N 左右，則可以將值放入陣列（串列）中，這樣 array[value-min]將包含該值出現在輸入。構建成本為 O(N)，查找成本為 O(1)。更好的是，預處理和查找的常數明顯低于任何其他方法。
注意：我沒有提到 O(N)計數排序作為 O(N log N) 排序（選項 3）的一般情況的替代方案，因為如果max(value)-min(value)對于計數排序足夠小，那么選項 4是相關的并且更簡單、更快。
如果適用，請選擇選項 4，否則如果您想投入時間和代碼，請選擇選項 2。如果 4 不適用，并且 2 在您的情況下不值得努力，那么如果您不介意，請選擇選項 2病態的最壞情況（當對手可能想在 DOS 攻擊中傷害您時，切勿選擇選項 2）。
uj5u.com熱心網友回復：
您的問題與排序無關，更不用說線性搜索了。
如果您聲稱n-1比較是強制性的，那么您的問題肯定很復雜Ω(n)。但是僅憑這些資訊，您不能保證O(n)，因為沒有說這些n-1比較就足夠了，也沒有說演算法不執行額外的操作，例如決定執行哪些比較。結果可能是您的演算法O(n3)沒有機會做得更好，但我們無法判斷。
最佳案例復雜度：Ω(n). 最壞情況復雜性：未知。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424321.html
上一篇：如何在陣列樹模式生成器中支持256個沒有null的值？
下一篇：如何使用C 為快速排序撰寫磁區