我无法确定以下类型代码的 Big-O 运行时间:
typedef map<string, vector<string> >::iterator MapIter;
while(!myMap.empty()) {
for(MapIter it = myMap.begin(); it != myMap.end(); it++) {
// if it->first is the key for the pairing I want to remove
// then erase it
break;
}
}
这里的代码真的不是特别重要，我的完整代码工作正常，我只是想确定 Big-O 分析。让我特别困惑的是，我在 map 上迭代 n 次，然后是 n-1 次，依此类推，直到 map 为空。这需要 O(n!) 时间吗？
最佳答案
n + (n-1) + (n-2) + ... + 1 + 0 = n(n+1)/2
大概是
O(n^2)
关于c++ - 在同一列表的 while 循环中迭代 for 循环所需的 Big-O 时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20365743/