嵌套映射 cpp 的时间复杂度

Question

假设我们有map<int,map<int,int>>m那么这个的时间复杂度应该是m[x][y]多少？

我认为应该是logn*logmnumber of xisn和 number of yis m。

Answer 1

如果 x 的数量为 n 且 y 的数量为 m，我认为它应该是 logn*logm。

不可以。您在两个单独的地图上执行两次地图查找。你没有任何重复。一张地图在另一张地图内不会影响复杂性。

当您按顺序执行两个操作时，复杂度是各个操作的复杂度之和。因此，在这种情况下，复杂度为 O(log N + log M)，其中 N 是一张地图的大小，M 是另一张地图的大小 - 可以简化为 O(log N)，其中 N 是大小更大的地图。