安卓
根据算法书籍，二进制搜索的性能为O（log n），而简单搜索的性能为O（n）。
但是，为什么我们还不考虑排序所花费的时间，这是二进制搜索的先决条件呢？
威廉·范昂塞姆
简而言之：因为通常该列表的构建仅进行一次，而搜索（和更新）则进行多次。
构造排序列表确实需要O（n log n）。使用二进制搜索的目的是，对集合进行排序后，我们可以对该列表执行多个查询，每个查询都带有O（log n）。
此外，例如，如果您使用二叉搜索树，则还可以执行插入和删除O（log n）中的元素，因此更新集合也很便宜（前提是您为此使用了有效的数据结构）。
例如，在数据库中，人们经常使用索引来执行快速查找。通常，读取次数比更新次数大。更新单个元素需要O（log n），因此在现有数据上创建索引确实很昂贵，但是与搜索和更新B树数据结构相比，这并不是很常见[wiki]。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
编辑于
我来说两句