c++ - 堆放容器时的大O

Question

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

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

Answer 1

在这种情况下，您只需要总结复杂性，

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但它们始终不变。