algorithm - 处理大型项目的空间复杂性

Question

我在一家初创公司被问到这个问题

If you are asked to design Maps like Bing Maps how would you estimate the space complexity ?

对于 map ，我能想到的唯一答案是，空间是恒定的，但我不确定我的方向是否正确。

如何处理这样的问题？

Answer 1

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

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

卫星图像是最容易计算的，因为您需要以某种基本分辨率级别覆盖全局。但是你可以期待一些源 Material 集中在感兴趣的区域，比如航空摄影；这些可能会具有更高的分辨率，但总面积更小。

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

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