algorithm - 接近大型项目的空间复杂性

Question

我在创业公司被问到这个问题

如果你被要求设计像 Bing Maps 这样的地图，你会如何估计空间复杂度？

对于地图，我能想到的唯一答案是，空间是恒定的，但我不确定我是否朝着正确的方向前进。

如何处理这样的问题？

Answer 1

如果您查看地图服务的详细信息，您会注意到它们有多个图层。对于每一层，您可以根据源数据的分辨率以及它们所覆盖的区域来估计大小：

size = sum(foreach layer: layer.area * (layer.resolution)^2 * layer.elementsize)

卫星图像是最容易计算的，因为您需要以某种基本分辨率水平覆盖全球。但是您可以期望一些原始材料会集中在感兴趣的区域，例如航空摄影；这些可能是更高的分辨率，但总面积更小。

您需要保存全分辨率数据的缩小版本，以便方便地提供缩小显示。但是，这应该只占用全分辨率数据所需空间的一小部分。图像大小每减少 2 倍，附加数据的大小就会减少 4 倍；2 倍图像金字塔的额外大小将是全分辨率数据的 1/3。

最后，您还需要地理信息，例如道路、地理区域和兴趣点。这些数据的大小自然是非常有弹性的，但是您可以通过评估特定城市的商业地理数据库的大小并按人口进行缩放来获得某种粗略的估计。

Answer 2

假设以 0 倍缩放查看地图（可以看到整个星球）并且地图被分成 X 图像。

然后你缩放到 1，现在你有相同的 X 图像来显示当前区域，但这只是地图的一部分。假设您需要在缩放 1 中查看 Y 部分以“覆盖”整个星球。这意味着您应该查看 X * Y 图像。必应地图有大约 21 个缩放级别，所以你应该有 X * 1 + X * Y + X * Y ^ 2 + ... + X * Y ^ 21 = X * (1 + Y + Y ^ 2 + .. . + Y ^ 21)，这导致估计 O(X * Y ^ 21)。

另外，您应该考虑到描述地址、道路、交通所需的一些数据。这可以通过使用一些统计数据来近似计算。