Big O при укладке контейнеров

Question

Я использую std :: map, которая реализована как красно-черное дерево со сложностью времени O (log (N)) для доступа (согласно этому сайту: http://bigocheatsheet.com/). Как вычислить большой O, если я складываю эти контейнеры.

Например, map<int, map<int, int>>. Что такое большой 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).

Это было бы O (LOGN) также в случае map<int, map<int, map<int, map<int, .. и так далее, потому что количество вложенных уровней не зависит от N но они всегда постоянные.

Answer 2

Еще O(Log(N))

Предполагая, что вы имели в виду доступа ко второй карте в выездном карте, это по существу две O (журнал (N)) операций спина к спине. Следовательно, O(2*log(N)), который уменьшен до O(log(N)).

Answer 3

Это то же самое, O (log (N)).

Это потому, что у вас есть O (log (N)), чтобы получить «внутреннюю» карту, тогда вам понадобится 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 - размер внутренней карты.

Обратите внимание, что размеры внешних и внутренних карт независимы.