Bir dosyadan çift satırları kaldıran haritaları kullanarak C++ kodu yaptım. Bu kodun karmaşıklığı nlogn veya n^2 olur mu?

Question

Haritaların ekleme ve erişim zamanları logN'dir, ancak kodlarım tekrar bulmak için tekrar tekrar harita üzerinde yinelenmesi gerektiğinden, en kötü durum karmaşıklığı n^2 doğru olur mu? log(n)n = number of lines karmaşıklığını sahiptir

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

Bulma işlemi bir logN işlemidir. N kere bir döngüde. Yani n * logN tabiki O (nLogN). N veya daha düşük bir değerin bir sonraki döngüsü (çiftler varsa), bu üçüncü döngü için aynıdır. Bu yüzden zaman karmaşıklığı O (nLogN).

Answer 2

Yalnızca operator[] kullanın. Genel olarak O(n) = nlog(n).