堆放集装箱时的大O

Question

我使用 std::map 实现为红黑树，时间复杂度为 O(log(N)) 进行访问（根据此站点：http://bigocheatsheet.com/）。如果我堆叠这些容器，我如何计算大 O。

例如map<int, map<int, int>>。访问最里面地图的大O是什么？

Answer 1

还是O(Log(N))

假设您的意思是访问 out 映射中的第二个映射，它实际上是两个 O(log(N)) 背靠背操作。因此O(2*log(N))，再减少就是O(log(N))。

Answer 2

你只需要总结一下这种情况下的复杂性，

map<int, map<int, int>> data;
const auto& lookup = data[5]; // here you spend O(logn)
int value lookup2 = lookup[3]; // here you spend O(logn)

所以是 O(logn) + O(logn) = O(klogn) = O(logn).

在 map<int, map<int, map<int, map<int, .. 的情况下也是 O(logn) 等等，因为嵌套级别的数量不依赖于 N但它们总是不变的。

Answer 3

一样，O(log(N))。

这是因为你有 O(log(N)) 来获得 'inner' 地图，然后你需要 O(log(N)) 再次用于元素，所以你总共有 O(2 *log(N)) 与 O(log(N)).

相同

Answer 4

同样的事情。如果有 map<int, map<int, int>> m 而您想查找 m[4][2] - 那只是两个独立的地图查找。所以你只需添加它们：O(log M + log N) = O(log MN) 其中 M 是外部地图的大小，N 是内部地图的大小。

请注意，外部和内部地图大小是独立的。

Big O when stacking containers