如何最优计算两个std::vector的差值？优化O(mn)复杂度方案

你的实现之所以在大容量vector下运行缓慢，核心原因是每次调用std::count都会完整遍历v0，导致最坏时间复杂度达到O(mn)。我们可以通过两种主流方案优化时间复杂度：

方案一：排序+二分查找（稳定最坏时间复杂度） #

通过先对v0排序，再用二分查找判断元素是否存在，将查找操作的时间复杂度从O(n)降到O(log n)，整体最坏时间复杂度优化为O(n log n + m log n)。

优化后代码 #

#include <vector>
#include <algorithm>

template<typename T>
std::vector<T> diff_vectors(const std::vector<T>& v, const std::vector<T>& v0) {
    std::vector<T> result;
    std::vector<T> sorted_v0(v0); // 拷贝v0避免修改原容器
    
    // 排序v0，时间复杂度O(n log n)
    std::sort(sorted_v0.begin(), sorted_v0.end());
    // 去重（可选，不影响正确性，但能减少二分查找的范围）
    auto unique_end = std::unique(sorted_v0.begin(), sorted_v0.end());
    sorted_v0.erase(unique_end, sorted_v0.end());
    
    for (const T& elem : v) {
        // 二分查找判断元素是否存在，O(log n)
        if (!std::binary_search(sorted_v0.begin(), sorted_v0.end(), elem)) {
            result.push_back(elem);
        }
    }
    return result;
}

关键说明 #

• 排序仅需执行一次，后续所有查找都基于排序后的容器；
• 增加了参数的const引用修饰，避免原代码中传值导致的大容量vector拷贝损耗；
• 去重操作可进一步缩小二分查找的范围，提升查找效率。

方案二：哈希集合（平均最优时间复杂度） #

利用std::unordered_set的平均O(1)查找特性，将整体平均时间复杂度降到O(m + n)，适合对性能要求极高且元素类型支持哈希的场景。

优化后代码 #

#include <vector>
#include <unordered_set>

template<typename T>
std::vector<T> diff_vectors(const std::vector<T>& v, const std::vector<T>& v0) {
    std::vector<T> result;
    std::unordered_set<T> v0_set(v0.begin(), v0.end());
    
    for (const T& elem : v) {
        // 平均O(1)时间的查找操作
        if (v0_set.find(elem) == v0_set.end()) {
            result.push_back(elem);
        }
    }
    return result;
}

关键说明 #

• 哈希集合的构建时间为O(n)平均，遍历v的时间为O(m)，整体平均性能优于排序方案；
• 若元素为自定义类型，需为其提供对应的哈希函数和相等性判断逻辑；
• 哈希集合存在最坏O(n)的查找情况（极端哈希冲突），但实际工程中几乎不会出现。

方案选择建议 #

• 若元素类型不支持哈希（或难以实现哈希函数），或需要稳定的最坏时间复杂度，选择排序+二分查找方案；
• 若元素类型支持哈希，且追求极致的平均性能，选择哈希集合方案。

内容的提问来源于stack exchange，提问作者sbh