如何降低两个 for 循环的大 O 复杂度

Question

该函数必须 return 数组 songs（由歌曲长度组成的整数数组，以秒为单位）中数字对的计数，这样形成的数字对加起来就是整分钟。

long playlist(int songs_count, int *songs) {
    int i, j, k = 0;
    for (i = 0; i < songs_count; i++) {
        for (j = i + 1; j < songs_count; j++)
            if ((songs[i] + songs[j]) % 60 == 0)
                k++;
    }
    return k;
}

Answer 1

如果seconds的值比较小，可以用hash map（c++中的unordered_map）来解决~O(n)复杂度。

假设你知道这对的最大值是 600 秒，那么你可以用另一个数组存储这些值。

for(int i = 1; i <= 10; i++)
{
    a[i-1] = i * 60;
}

//a[] = {60, 120, 180, 240, 300, 360, 420, 480, 540, 600};
unordered_map <int, int> mymap;

for(int i = 0; i < songs_count; i++)
{
    mymap[i] = songs[i];
}

现在您可以将代码修改为（解决方案适用于 C++）：

long playlist(int songs_count, int *songs) 
{
    int i, j, k = 0;
    for(int i = 1; i <= 10; i++)
    {
        a[i-1] = i * 60;
    }

    //a[] = {60, 120, 180, 240, 300, 360, 420, 480, 540, 600};
    unordered_map <int, int> mymap;

    for(int i = 0; i < songs_count; i++)
    {
        mymap[i] = songs[i];
    }

    for (i = 0; i < songs_count; i++) 
    {
        for (j = 0; j < n /*size of a*/; j++)
        {
            if (a[j] > songs[i] && mymap.find(a[j] - songs[i]) != mymap.end())
            {
                k++;
            }
        }
    }
    return k;
}

Answer 2

第一个直接的方法是这样的：

创建一个包含 60 个条目的数组，seconds%60 的其余部分初始化为全零。
计算每首歌曲的余数并递增数组中的相关条目。
迭代所有可能的余数 (1..29)
对于每个剩余部分，您有 a = array[i] 首歌曲和 b = array[60-i] 首需要合并的匹配歌曲：num = a*b; k += num;
对于 i==0 和 i==30 您需要特殊处理，因为匹配歌曲位于同一数组元素中：num = a*(a-1);

这会将时间复杂度降低到 O(N):

你需要

循环 n 来填充数组（可以在构建歌曲列表时完成一次）和
循环 0..30 进行计算。

这导致 O(N)+O(1)

编辑：根据您的规则（歌曲的顺序是否重要）您可能需要乘以 2。

Answer 3

您可以将复杂度从 O(N²) 降低到 O(N) 一个简单的方法：

使用数组 int a[60]，对于 0..59 中的每个 i，计算持续时间为 i 秒的歌曲数量，并且整数分钟。一次通过就足够了。
对于数组中的每个 i，计算感兴趣的歌曲对的数量。再次需要一次通过。
要计算对数，需要额外说明：
- 成对订购了吗？
- 一对可以有两次相同的歌曲吗？

假设一对必须有不同的歌曲并且顺序无关紧要，这里是一个实现：

long playlist(int songs_count, int *songs) {
    long a[60] = { 0 };
    int i;
    long total;
    for (i = 0; i < songs_count; i++)
        a[songs[i] % 60]++;
    total = (a[0] * (a[0] - 1) + a[30] * (a[30] - 1)) / 2;
    for (i = 1; i <= 29; i++)
        total += a[i] * a[60 - i];
    return total;
}

如果顺序很重要并且一对可以有两次相同的歌曲，则计算不同：

long playlist(int songs_count, int *songs) {
    long a[60] = { 0 };
    int i;
    long total;
    for (i = 0; i < songs_count; i++)
        a[songs[i] % 60]++;
    total = 0;
    for (i = 0; i < 60; i++)
        total += a[i] * a[(60 - i) % 60];
    return total;
}

如何降低两个 for 循环的大 O 复杂度

How can I reduce big O complexity of two for loops

c

big-o

asymptotic-complexity