c++ - 由于它们的大 O 复杂性，两个函数没有花费我预期的时间，谁能解释为什么？

Question

所以我要解决的问题是找到一组整数中的多数元素，集合的大小 0 < n < 10^5，并且每个元素 0 < a < 10^9。所以我只需要找出哪个元素出现严格超过 n/2 次。

我有两个解决方案，我认为它们都是正确的，但它们的表现并不像我对它们的复杂性的理解所期望的那样。有人可以向我解释我做错了什么/误解了什么吗？

int getMajElement(vector<int> a)
{
std::unordered_map<int, int> countMap;
std::unordered_map<int, int>::iterator it;

for (int i : a)
{
    it = countMap.find(i);

    if (it == countMap.end())
    {
        countMap.insert(std::pair<int, int>(i, 1));
    }
    else
    {
        it->second++;
    }
}

int mostOfNum = 0;
int mostOfNumCount = 0;

for (std::pair<int, int>  pair : countMap)
{
    if (pair.second > mostOfNumCount)
    {
        mostOfNumCount = pair.second;
        mostOfNum = pair.first;
    }
}

if (mostOfNumCount > floor(a.size() / 2))
{
    return mostOfNum;
}
else
{
    return -1;
}
}

根据我的理解，第一个“for(int i : a)”应该在 O(n) 时间内运行，而查找/增加值应该在 hashmap 的 O(1) 时间内运行。第二个“for (std::pair pair : countMap)”循环也应该在 O(n) 时间内运行，因为我只是迭代最多 n 对。这总共需要 O(n) 时间。

此函数需要 2.4 秒才能运行 n = 10^5，并且每个 a = rand() % 10^9。我确保只为函数计时，而不是设置初始值。

然后下一个在相同条件下需要 0.70 秒，但我本以为第一个会更快。

第二个函数采用递归的分治法求解，需要O(n log(n))的时间。它基本上将列表分成 n 个单独的部分，然后检查左半部分的多数元素是否与右半部分的多数元素相同。如果不是，它将扫描列表以查看哪个值是该部分的总体多数 (value > floor((right - left)/2)) 并将其传回，否则 -1。

有人可以向我解释是什么导致了时差吗，这只是我犯的一个实现错误吗？

int get_majority_element(vector<int> &a, int left, int right) {

    if (left == right) return -1;
    if (left + 1 == right) return a[left];

    int mid = left + floor((right - left) / 2);

    int leftMajority = get_majority_element(a, left, mid);
    int rightMajority = get_majority_element(a, mid, right);

    if(leftMajority == rightMajority)
    {
        return leftMajority;
    }
    else if (rightMajority == -1)
    {
        return leftMajority;
    }
    else if (leftMajority == -1)
    {
        return rightMajority;
    }
    else
    {
        int leftCount = 0, rightCount = 0;
        for (int i = left; i < right; i++)
        {
            if (a[i] == leftMajority)
            {
                leftCount++;
            }
            else if (a[i] == rightMajority)
            {
                rightCount++;
            }
        }

        if (leftCount > floor((right - left) / 2))
        {
            return leftMajority;
        }
        else if (rightCount > floor((right - left) / 2))
        {
            return rightMajority;
        }
        else
        {
            return -1;
        }           
    }

    return -1;
}

Answer 1

评论太长了。

复杂性理论是关于随着数据量的增长单个算法会发生什么。它是 n --> 无穷大的极限。

在对相同大小的数据比较两种不同的算法时，它的用处要小得多。为什么？因为开销可以支配计算。例如，冒泡排序是 O(n^2)。但是在(非常)小的数据集上，它的性能可以胜过“更快”算法的合理实现。

正确的比较应该是每个算法在 10^5 个元素上的速度，然后是 10^6，然后是 10^7。也就是说，给定算法的速度如何增长。