c++ - 嵌套映射 cpp 的时间复杂度

Question

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

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

标签： c++maps

Answer 1

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

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

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