c++ - O(NlogN) 算法运行速度比 O(n) 快...等等，什么？

Question

老实说，我有点困惑。我正在解决经典算法问题之一。给定一个整数集合，找出是否有 2 个元素的总和等于给定的数字。

所以我实现了 2 个解决方案。

bool find1(std::vector<int>& V, int sum) 
{
    std::unordered_set<int> hashTable;
    for (int i = 0; i < V.size(); ++i) 
    {
        if (hashTable.find(V[i]) != hashTable.end()) 
        {
            return true;
        }
        hashTable.insert(sum - V[i]);
    }
    return false;
}

bool find2(std::vector<int>& V, int sum) 
{
    for (int i = 0; i < V.size() ; ++i) 
    {
        if (std::binary_search(V.begin(), V.end(), sum - V[i])) 
        {
            return true;
        }
    }
    return false;
}

Find1 预计是线性算法(取决于桶的负载和哈希函数的效率)。

Find2 预计为 NlogN，我们循环并为每次迭代进行二分查找。

实现这个函数后，我尝试在一个比较大的集合上测试这些算法的运行时间，结果让我很困惑。

int main() 
{
    std::vector<int> V(10000,0);

    std::chrono::system_clock::time_point now1 = std::chrono::system_clock::now();

    for (int i = 0; i < 100; ++i) 
    {
        bool b = find1(V, 1000);
    }

    std::chrono::system_clock::time_point then1 = std::chrono::system_clock::now();
    std::cout <<"Linear with hashing = "<< std::chrono::duration_cast<std::chrono::microseconds>(then1 - now1).count()<<std::endl;

    std::chrono::system_clock::time_point now2 = std::chrono::system_clock::now();
    std::sort(V.begin(), V.end());
    for (int i = 0; i < 100; ++i)
    {
        bool b = find2(V, 1000);
    }

    std::chrono::system_clock::time_point then2 = std::chrono::system_clock::now();
    std::cout <<"NlogN with binary_search = " <<std::chrono::duration_cast<std::chrono::microseconds>(then2 - now2).count() << std::endl;

    system("pause");
}

在这里，我用 0 初始化了 vector 以确保两个算法都运行最坏的情况。
程序的输出是:

Linear with hashing = 6759245         
NlogN with binary_search = 4508025

这怎么可能？谁能给我解释一下？

Answer 1

仅仅因为一种算法的渐近复杂度的上限小于另一种算法，并不意味着它对于任意输入都更快。这只是意味着存在一定大小的输入 N'，超过该大小，不太复杂的算法会更快。此大小将特定于运行该程序的每个特定系统。

测量渐近更复杂的算法更快仅仅意味着您的测试小于大小 N'。但是，这假设您的复杂性分析首先适用于该程序。例如，如果您的程序使用最佳情况输入测试算法，则分析最坏情况的复杂性是错误的，反之亦然。

就其值(value)而言，在我的系统上的结果是:

Linear with hashing = 9557
NlogN with binary_search = 15828