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

Question

地图的插入和访问时间是 logN，但由于我的代码必须一次又一次地遍历地图以查找重复项，最坏情况下的复杂度肯定是 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

您仅使用 operator[]，其复杂度为 log(n)，其中 n = number of lines。您的总体 O(n) = nlog(n).

Answer 2

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

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

I made a C++ code using maps that removes duplicate lines from a file. Would the complexity of this code be nlogn or n^2?

c++

dictionary

file-read