時間複雜度混淆的下界

Question

是否有可能證明任何基於比較的搜索算法的排序列表的時間複雜度存在下限？換句話說，是否有任何算法將輸入排序列表和元素並輸出列表中元素的索引（如果出現）必須採取一定數量的步驟？

Answer 1

執行您提出的特定算法的可接受方式是二進制搜索https://en.wikipedia.org/wiki/Binary_search_algorithm，其平均時間複雜度爲O（logN）。正如在上面的評論中指出的那樣，這種算法和很多類似的算法可以在完美的情況下在一個步驟中完成。

一般來說，證明一個算法是最優化的是一個難題，它涉及到對算法進行分類，或者將一種訴求歸爲微不足道。您可以在這裏找到更多的信息：

https://cstheory.stackexchange.com/questions/1284/problems-that-can-be-used-to-show-polynomial-time-hardness-results

這裏：

https://cstheory.stackexchange.com/questions/2038/what-techniques-are-used-for-proving-algorithms-optimal

在這裏：

https://www.quora.com/Is-there-any-known-way-to-prove-that-an-algorithm-is-optimal