Erhöhung der Effizienz der Laufzeit-Komplexität des Vergleichs von Vektorelementen?

Question

Ich habe zwei Vektoren:

std::vector<int> V1 {1,2,3,4,5,6,7}; 
std::vector<int> V2 {1,2,3}; 

folgende ausführende in quadratischen Laufzeitkomplexität führen würde:

for(auto IT = V1.begin(); IT != V1.end(), IT++) 
{ 
    for(auto IT2 = V2.begin(); IT2 != V2.end(); IT2++) 
    { 
    if(*IT == *IT2){std::cout<<"Found a match!"<<std::endl;} 
    else{std::cout<<"No match!"<<std::endl;} 

    } 
} 

es irgendwelche klare Möglichkeiten, dies zu linearen Zeit zu Fall bringen?

Würde die Verwendung eines STL-Algorithmus dies ermöglichen?

Zum Beispiel:

for(auto IT = V1.begin(); IT != V1.end(); IT++) 
{ 
    std::find(V2.begin(), V2.end(), *IT); 
} 

Answer 1

Sie gehen zu müssen, eine Reihe an linearer Zeit zu halten (Ihr Quell-Array, wie Sie offensichtlich sind von ihm 0th ist es Nth Element ist).

Sie können jedoch den anderen Suchbegriff nach unten bringen, indem Sie sicherstellen, dass der Inhalt des Suchbereichs zuerst sortiert wird. Dies ermöglicht die Verwendung von binären Suchalgorithmen, die log (n) -Komplexität sind.

Viel Glück!

Ein Beispiel hierfür:

std::vector<int> V1 {1,4,5,6,3}; 
std::vector<int> V2 {100, 104,101,3}; 
bool condition {false}; 
std::sort(V2.begin(), V2.end()); 

for(auto IT = V1.begin(); IT != V1.end(); IT++) 
{ 
    auto result {std::binary_search(V2.begin(), V2.end(), *IT)}; 
    if(result > 0){ condition = true}; 
}