Большой O при штабелировании контейнеров

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

Например map<int, map<int, int>>. Что такое большая буква О для доступа к самой внутренней карте?


c++ big-o stl
person user2600312    schedule 26.10.2016    source источник
comment
складывать эти контейнеры означает?   -  person Saurav Sahu    schedule 26.10.2016
comment
Это то же самое. map<int, map<int, int>> ничем не отличается от map<int, int> в том, что касается доступа к ключу.   -  person NathanOliver    schedule 26.10.2016
comment
Ваш вопрос нужно сформулировать точнее. Что вам нужно для доступа? Какие предположения можно сделать по существующим коэффициентам? Например, все ли карты имеют одинаковый размер? Есть ли на какой-нибудь карте ключи в [0,1,..N], где N — размер?   -  person Emerald Weapon    schedule 26.10.2016
comment
@EmeraldWeapon Правда, я должен упомянуть, что хочу получить доступ к самой внутренней карте. Но я думаю, что когда речь идет о большом О, всегда предполагается, что размер стремится к бесконечности. Я ошибся?   -  person user2600312    schedule 26.10.2016
comment
Предположим, вы хотите найти ключ j на самой внутренней карте, и только у одной из них есть такой ключ, но вы не знаете, какой именно. Это полностью меняет то, как вы должны думать об этом.   -  person Emerald Weapon    schedule 26.10.2016

Ответы (4)


arrow_upward
3
arrow_downward

Вам просто нужно суммировать сложности в этом случае,

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, но они всегда постоянны.

person Jack    schedule 26.10.2016

arrow_upward
3
arrow_downward

То же самое. Если у вас есть map<int, map<int, int>> m и вы хотите найти m[4][2] — это всего два независимых поиска карты. Таким образом, вы просто добавляете их: O(log M + log N) = O(log MN), где M — размер внешней карты, а N — размер внутренней карты.

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

person Barry    schedule 26.10.2016
comment
хорошо, что сложность зависит от обоих размеров - внешней и внутренней коллекции, однако я не уверен, что нотация O позволяет использовать 2D-домен... - person W.F.; 26.10.2016
comment
Есть ли разница, если внутренние карты имеют разные размеры, или вы можете просто взять N = средний размер? Я давно не занимался формальным анализом сложности, и удивительно, как много забываешь всего за пару десятков лет. - person molbdnilo; 26.10.2016
comment
@В.Ф. Конечно, это так. Если у вас есть две независимые переменные, вам нужны обе. например Алгоритм Дейкстры O(E + VlgV). - person Barry; 26.10.2016
comment
@molbdnilo В этом случае, поскольку мы просто добавляем, я бы взял максимальный размер. - person Barry; 26.10.2016
comment
@Barry В общем, почему бы не использовать две переменные в O. Хороший вопрос, спасибо! - person W.F.; 26.10.2016

arrow_upward
2
arrow_downward

Еще O(Log(N))

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

person selbie    schedule 26.10.2016

arrow_upward
2
arrow_downward

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

Это связано с тем, что у вас есть O (log (N)) для получения «внутренней» карты, затем вам снова нужно O (log (N)) для элемента, поэтому в сумме у вас есть O (2 * log (N)), который совпадает с O (log (N)).

person alain    schedule 26.10.2016