O(N ^ 2)是否将O循环嵌套为O(N),而循环可能？

Question

我说这个代码会在O(N)时间执行吗？这是迭代map <int,vector <int >>.

  int counter = 0;
  unsigned int u = 0;
  unsigned int v = 0;
  bool notDone = true;
  while (notDone) {
    if (u < map.size()) {
      if (v < map.at(u).size()) {
        if (map.at(u)[v] == -1) {
          ++v;
        }
        else {
          ++counter;
          ++v;
        }
      }
      else {
        v = 0;
        ++u;
      }
    } else {
      notDone = false;
    }
  }

Answer 1

如果N是映射条目的数量,并且TV是所有向量的大小的总和,那么您的程序O(N + TV)无论是写入"while"还是嵌套"for".

如果N是映射条目的数量,并且MV是所有向量的大小的平均值,那么O(N * MV)无论是作为"while"还是嵌套"for" ,您的程序都是如此.

更新:评论添指出,map.at是O(lg N)在地图的大小,它被称为O(N)倍,这样就使得实际的复杂性O(N * lg N + TV)和O(N * lg N * MV)分别.谢谢!

我不太清楚C++标准库是否有更有效的方法; 我怀疑在地图上存在一个O(1)迭代器.如果确实如此,那么您可以使用它而不是索引来迭代地图,并且该lg N术语将再次消失.