algorithm - 二分搜索与简单搜索

Question

根据算法书籍，二分搜索的性能为 O(log n)，而简单搜索为 O(n)。

但为什么我们不考虑排序所花费的时间，这是二分查找的先决条件？

Answer 1

简而言之:因为通常构建该列表只进行一次，而搜索(和更新)则进行多次。

构造一个排序列表确实需要 O(n log n)。使用二分查找的要点在于，一旦集合被排序，我们就可以对该列表执行多个查询，每个查询的复杂度为O(log n)。

此外，如果您使用二叉搜索树，您也可以在 O(log n) 中执行插入和删除元素，因此更新集合也可以很便宜(假设您为此使用了有效的数据结构)。

例如，在数据库中，人们经常使用索引来执行快速查找。通常读取的数量比更新的数量大。更新单个元素需要 O(log n)，因此在现有数据上创建索引确实很昂贵，但与搜索和更新 B-tree datastructure [wiki] 相比这并不常见。 .