c - 如何减少两个 for 循环的大 O 复杂性

Question

该函数必须返回数组中数字对的计数 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

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

创建一个包含 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。