时间复杂度混淆的下界

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