映射向量的时间复杂性是多少

Question

我有一个int映射到向量，

map<int,vector<int>> m

假设我将n元素映射到x。

现在，当我写作时， vector v = m [x]

映射向量的时间复杂性是多少。是因为迭代器还是o(n(！

Answer 1

o(logn(要找到键，然后o(n(复制向量，但是实际的时间复杂性本质上是渐近的，并且应该比O(nlogn(更好性能。

因此，时间复杂性是big-oh(nlogn(。

Answer 2

从 std::map中抽象一个值为o(log n(。

请注意，除此之外，您还取出map值的值副本，也许

const vector& v = m[x];

会更好？

Answer 3

std::map是二进制树。因此，单个元素查找是o(log n(复杂性。

但是，除此之外，在您的情况下，vector复制将是O(n(复杂性。

但是，第一个表达式中的 n 是地图中键的数量表达式，代表 value 。

的大小

假设两个 n 的幅度相同，整体复杂性将为O(n*logn(。