如何减少两个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.