c++ - 如果使用 unordered_set，O(NLogN) 显示出比 O(N) 更好的性能

Question

//Time sorting O(nlogn) + binary search for N items logN = 2NLogN = 
//Time: O(NLogN). 
//space - O(1).
bool TwoSum::TwoSumSortAndBinarySearch(int* arr, int size, int sum)
{
    sort(arr, arr + size);
    
    for (int i = 0; i < size; i++)
    {
        if (binary_search(arr + i + 1, arr + size, sum - arr[i]))
            return true;
    }
    return false;
}


//Time: O(N) as time complexity of Add and Search in hashset/unordered_set is O(1).
//Space: O(N)
bool TwoSum::TwoSumHashSet(int* arr, int size, int sum)
{
    unordered_set<int> hash;
    for (int i = 0; i < size; i++)
    {
        if (hash.find(sum - arr[i]) != hash.end())
            return true;
        hash.insert(arr[i]);
    }
    return false;
}

int* TwoSum::Testcase(int size)
{
    int* in = new int[size];
    for (int i = 0; i < size; i++)
    {       
        in[i] = rand() % (size + 1);//random number b/w 0 to N.
    }
    return in;
}

int main()
{
    int size = 5000000;
    int* in = TwoSum::Testcase(size);
    
    auto start = std::chrono::system_clock::now();//clock start 
    bool output = TwoSum::TwoSumHashSet(in, size, INT_MAX);
    auto end = std::chrono::system_clock::now();//clock end

    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "elapsed time: " << elapsed_seconds.count() << "s\n";   
}

我测了上面两种方法的性能，想找出TwoSum问题的地方。 在第一种方法中，我对数组进行排序，然后使用二进制搜索。 时间:O(NLogN)。 空间 - O(1)。

在第二种方法中，unordered_set使用的复杂度平均为常数，最坏情况与容器大小成线性关系。

//时间:O(N) 因为在hashset/unordered_set中Add和Search的时间复杂度是O(1)。 //空间:O(N)

下面是这两种方法所用的三个运行时间

TwoSumSortAndBinarySearch----------------TwoSumHashSet

---

1. 8.05-------------------------------------15.15

---

1. 7.76----------------------------------------14.47

---

1. 7.74----------------------------------------14.28

因此，很明显 TwoSumSortAndBinarySearch 的性能肯定优于 unordered_Set。

哪种方法在实际场景中更可取和推荐，为什么？

Answer 1

这是因为计算复杂性并未考虑每台现代计算机中存在的多级存储系统的行为。正是因为您使用时间 (!!) 通过代理来测量该行为，您的测量并不“像”理论计算复杂性。 计算复杂性仅在控制良好的情况下预测执行时间，此时代码最适合平台。如果你想衡量复杂性，你就无法衡量时间。测量操作计数。届时它将与理论相符。

以我有限的经验，当行为既不是指数也不是立方(或更高项)时，计算复杂性理论很少会预测合理大小的数据集的运行时间。在计算复杂性发挥作用之前，缓存访问模式和架构并行性的利用是性能的主要预测因素。