在未排序列表中查找元素的最有效方法是什麼？

Question

給定數組中未排序的列表，是否至少需要線性時間才能找到比x小的元素數？如果是這樣，爲什麼？

Answer 1

是的，您需要檢查每個數字至少一次，以確定它是否小於指定的閾值。如果這些數字沒有排序，那麼您就無法推斷出這些數字。

Answer 2

是的，你至少需要線性時間。沒有辦法知道一個元素是否小於x而不檢查它，所以你必須檢查每個元素一次。

如果您先將其排序，那麼只要元素大於x就可以停止。

Answer 3

如果您允許使用無限數量的處理器，您可以在接近恆定的時間內解決問題，假設結果串聯速度很快：只需將該陣列拆分爲固定大小的塊，並將每個塊處理在單獨的處理器上。

如果我們談論的是一個單一的處理器我說你需要線性時間：

• 你需要檢查每一個元素，它是否適合謂詞把它的結果。
• 排序或類似將無濟於事，因爲您再次必須檢查每個元素至少一次。