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

Question

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

标签： algorithmbinary-searchfibonacci

Answer 1

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

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

为了比较两个搜索的性能——时间复杂度有助于理解事物的扩展方式——所以 O(log N) 比 O(N) 好——但是 N 的大小和操作的成本在制作过程中同样重要决定.. 例如，对于非常小的尺寸和快速比较，O(N) 算法可能比 O(log N) 算法更快，但是随着 N 的增长，性能平衡可能会改变为另一种方式。

上一个关于时间复杂度的问题的好答案https://stackoverflow.com/a/2307314。