增加比較向量元素的運行時複雜度的效率？

我有兩個向量：增加比較向量元素的運行時複雜度的效率？

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

執行以下會導致二次運行時間複雜度：

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;} 

    } 
}

是否有任何明確的方法，把這個下降到線性時間？

會使用STL算法嗎？

例如：

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

來源

2016-12-01 Babra Cunningham

定義什麼是「比較矢量元素」對你意味着什麼。具體解釋當任一向量包含重複值時的預期結果。 –

如果你知道你的向量是有序的，二進制搜索更快。 – lakeweb

也許使用std :: set和compare sets？集合和地圖中的紅黑樹木爲您提供了極佳的性能和適合的用例。或者，如所建議的，首先對載體進行排序。 –

你將需要保持一個陣列的線性時間（源數組作爲你明明搜索它的第0到它的第N個元素）。

但是，您可以可以通過確保搜索空間的內容首先排序來降低其他搜索詞。這將允許使用log（n）複雜度的二進制搜索算法。

祝你好運！

這樣的一個例子：

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}; 
}

來源

2016-12-01 02:01:53 Monza

蒙扎是我的編輯好嗎？你想添加什麼？ –

只是想補充一點，在做2個向量的交集的時候，總是更好地用少量元素來排序向量。 – sameerkn

增加比較向量元素的運行時複雜度的效率？

回答

相關問題