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

在这里,我vector用0来初始化,以确保两个algos运行最坏的情况.
该计划的输出是:

Linear with hashing = 6759245         
NlogN with binary_search = 4508025

这怎么可能？有人可以向我解释一下吗？

Answer 1

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

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

对于它的价值,我的系统的结果是:

Linear with hashing = 9557
NlogN with binary_search = 15828

Answer 2

您创建没有预期大小的哈希表.然后逐个插入元素.这会导致哈希表反复调整大小,从而导致系统调用分配更多内存.

虽然这对于O(1)每个插入都是分摊的,但系统调用的隐藏常量足以使二进制搜索更快.

尝试将哈希表的预期大小设置为sizeof(V) * 1.2左右,以避免重新散列.如果这还不够,那么将时间与100000, 1000000, 10000000, ...值进行比较.您应该看到哈希表赢得N更大.

注意:二进制搜索V.end() == 0将在第一次比较时终止,并且不是最坏情况.这是最好的情况.可能更加理由为什么它更快.