是否有可能证明任何基于比较的搜索算法的排序列表的时间复杂度存在下限?换句话说,是否有任何算法将输入排序列表和元素并输出列表中元素的索引(如果出现)必须采取一定数量的步骤?时间复杂度混淆的下界
0
A
回答
1
执行您提出的特定算法的可接受方式是二进制搜索https://en.wikipedia.org/wiki/Binary_search_algorithm,其平均时间复杂度为O(logN)。正如在上面的评论中指出的那样,这种算法和很多类似的算法可以在完美的情况下在一个步骤中完成。
一般来说,证明一个算法是最优化的是一个难题,它涉及到对算法进行分类,或者将一种诉求归为微不足道。您可以在这里找到更多的信息:
这里:
在这里:
https://www.quora.com/Is-there-any-known-way-to-prove-that-an-algorithm-is-optimal
相关问题
- 1. 空间复杂度混淆
- 2. 混淆下面的Dijkstra算法实现的时间复杂度
- 3. 基本复杂度混淆
- 4. 时间复杂度混乱
- 5. 混淆复杂类?
- 6. MySQL复杂混淆
- 7. SQL PHP的混淆复杂
- 8. 时间复杂度界输入
- 9. 下面代码的时间复杂度?
- 10. 以下算法的时间复杂度?
- 11. 以下算法的时间复杂度
- 12. 时间复杂度
- 13. 时间复杂度
- 14. 时间复杂度
- 15. 时间复杂度
- 16. 时间复杂度和空间复杂度,如何计算空间复杂度
- 17. 以下是什么时间复杂度?
- 18. iPhone下降测试时间复杂度
- 19. 计算函数的空间复杂度和时间复杂度
- 20. map.find()的时间复杂度
- 21. A *的时间复杂度
- 22. Math.Sqrt()的时间复杂度?
- 23. BST的时间复杂度
- 24. gsub的时间复杂度
- 25. Python Suds复杂类型混淆
- 26. 'if'in'时间复杂度
- 27. 时间复杂度(Java,Quicksort)
- 28. 降低时间复杂度
- 29. 算法复杂度时间
- 30. 时间复杂度说明
必须至少需要1步假设第一个元素是什么你正在寻找,虽然这个表现不是平均水平,但它是理论上的最低界限。 –
根据堆栈交换的cs理论部分,这可能会更好。 – Checkmate