斐波那契搜索的时间复杂度与二分搜索相比

Question

为什么斐波那契搜索的平均时间复杂度与二分搜索的时间复杂度相同，尽管与二分搜索相比斐波那契搜索执行了更多的比较

Answer 1

时间复杂度是关于事物如何随着输入大小的增加而扩展，而不是关于每次迭代的成本。

所以 O(log n) - 它们都是 - 表示如果将输入的长度加倍，所涉及的工作量比原始输入多大约 30%。这样做的成本没有说明——只是给定长度 N 的成本 X，将长度 (2N) 加倍会导致成本增加约 30%。

比较两个搜索的性能 - 时间复杂度有助于理解事情的规模 - 所以 O(log N) 优于 O(N) - 但 N 的大小和操作的成本是在做出决定时同样重要。例如，对于非常小的尺寸和快速比较，O(N) 算法可能比 O(log N) 算法更快，但是随着 N 的增长，性能平衡可能会变为其他方式。

对上一个时间复杂度问题的很好回答 。