Какова временная сложность отображения вектора?

Question

У меня есть карта int для вектора,

map<int,vector<int>> m

Предположим, я отображаю N элементов на x.

Теперь, когда я пишу, vector v = m [x]

Какова временная сложность отображения вектора. Это O (1) из-за итераторов или O (N)!

Answer 1

Абстрагирование значения от std::map равно O (log N).

Обратите внимание, что в дополнение к этому вы берете копию значения map, возможно

const vector& v = m[x];

будет лучше?

Answer 2

std::map - это двоичное дерево. Таким образом, поиск по одному элементу - сложность O (log N).

Но в дополнение к этому, в вашем случае будет иметь место vector копирование, что составляет O (N) сложность.

Однако N в первом выражении - это число ключей на карте и не является тем же N из второго выражения, где он представляет размер значения .

Если предположить, что оба N имеют одинаковую величину, общая сложность будет O (N * logN).