c++ - 改进嵌套循环的优化

Question

我正在编写一个简单的程序来计算数组中可被 3 数组长度整除的对数，值由用户确定。

现在我的代码完全没问题了。但是，我只想检查是否有更快的计算方法可以缩短编译时间？

由于数组的长度为 10^4 或更少，编译器花费的时间少于 100 毫秒。但是，当它达到 10^5 时，它会飙升到 1000 毫秒，这是为什么呢？以及如何提高速度？

#include <iostream>

using namespace std;

int main()
{
    int N, i, b;
    b = 0;
    cin >> N;

    unsigned int j = 0;
    std::vector<unsigned int> a(N);
    for (j = 0; j < N; j++) {
        cin >> a[j];
        if (j == 0) {
        }

        else {
            for (i = j - 1; i >= 0; i = i - 1) {
                if ((a[j] + a[i]) % 3 == 0) {
                    b++;
                }
            }
        }
    }

    cout << b;

    return 0;
}

Answer 1

您的算法具有 O(N^2) 复杂度。有一个更快的方法。

(a[i] + a[j]) % 3 == ((a[i] % 3) + (a[j] % 3)) % 3

因此，您不需要知道确切的数字，您只需要知道它们除以三的余数即可。可以用两个余数为零的数 (0 + 0) 和两个数的余数为 1 和 2 来接收和的零余数 (1 + 2)。

结果将等于 r[1]*r[2] + r[0]*(r[0]-1)/2 其中 r[i] 是余数等于i 的数字的数量。

int r[3] = {};
for (int i : a) {
    r[i % 3]++; 
}
std::cout << r[1]*r[2] + (r[0]*(r[0]-1)) / 2;

这个算法的复杂度是O(N)。