时间戳

首页 > 解决方案 > 我们可以使用地图搜索而不是二分搜索吗？

python - 我们可以使用地图搜索而不是二分搜索吗？

问题描述

地图提供 O(1) 查找。难道我们不能遍历数组一次并构建一个与其索引相对应的映射（与数组相反），当我们想要搜索我们可以调用map[VALUE]的东西时，它会返回索引。

它可能不适用于数组中的大值，但假设a[i]<10^5我们不能这样做而不是二进制搜索吗？然后，每个查询将是 O(1)。

PS：我的意思是无序地图..

标签： pythonc++algorithmdata-structures

解决方案

以下是您可能要考虑的问题 -

  • 您不能在地图中存储相同值的多个元素

  • 查找时间是O(log(n))而不是O(1)

  • 地图中发生的事情并不是魔法，它允许我们在更短的时间内访问它。在后台有一个散列过程正在进行，unordered_map这O(1)也需要时间。所以，大 O 隐藏了一个很大的常数时间因子。标准map为您提供O(logn)查找，与数组中的二进制搜索相同的时间复杂度。

您获得的搜索平均时间复杂度大致相同。在 C++ 中使用标准映射将遇到的主要问题是它无法容纳具有相同值的多个元素。使用 map 可能获得的一个优点是删除和插入时间将是O(logn).

因此，如果您知道您将要处理的数据集没有重复元素和/或将频繁添加/删除元素，那么在这种情况下，您当然可以考虑将 map 作为更好的选择

推荐阅读