c++ - 我使用从文件中删除重复行的映射制作了 C++ 代码。这段代码的复杂度是 nlogn 还是 n^2？

Question

map 的插入和访问时间是 logN，但由于我的代码必须一次又一次地遍历 map 以查找重复项，最坏情况下的复杂度肯定是 n^2 对吧？

ifstream infile; infile.open("test.txt");
string line;
int linecount=0;
map<string, int> TextLines;
if (infile.is_open())
{

    while (getline(infile, line))
    {
        if (TextLines.find(line) != TextLines.end())
            continue;
        TextLines[line] = ++linecount;
    }
}
infile.close();
//print in new file;
map<int, string> output;
map<string, int> ::iterator ite = TextLines.begin();
while (ite != TextLines.end())
{
    output[ite->second] = ite->first;
    ite++;
}
ofstream outfile;
outfile.open("test.txt");
map<int, string> ::iterator ite2 = output.begin();
while (ite2 != output.end())
{
    outfile << ite2->second <<endl;
    ite2++;
}

Answer 1

查找操作是一个 logN 操作。就这样循环了N次。所以 n*logN 当然是 O(nLogN)。某个值 N 或更低的下一个循环(如果有重复)，这与第三个循环相同。所以时间复杂度是 O(nLogN)。