如何降低 C 中关于嵌套循环的时间复杂度

Question

该代码是关于确定整数数组中的“两个不同的元素”，其中这两个元素的索引不相同，并且在它们之间进行按位运算得到“1”。

“执行以下程序的时间是 500 毫秒。”但是因为我在这里有一个嵌套的 for 循环，所以我得到了 TLE。如何修改此代码以满足要求？

请注意，这是我知道如何检查数组中某些内容的唯一方法，而且我只能用 C 语言编写代码。代码如下：

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, count = 0;
        scanf("%d", &n);
        int num[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if ((num[i] ^ num[j]) == 1)
                    count = 1;
            }
        }
        count == 1 ? printf("Yes\n") : printf("No\n");
    }
    return 0;
}

Answer 1

对于数组中的 2 个条目来匹配表达式 (num[i] ^ num[j]) == 1，它们之间的距离最多为 1。您可以对数组进行排序并使用线性扫描，仅测试连续的元素，将时间复杂度从 O(N²) 降低到 O(N log(N)).

这是修改后的版本：

#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void *aa, const void *bb) {
    const int *a = aa;
    const int *b = bb;
    return (*a > *b) - (*a < *b);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t-- > 0) {
        int n, count = 0;
        scanf("%d", &n);
        int num[n];
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);

        qsort(num, n, sizeof(*num), compare_ints);

        for (int i = 1; i < n; i++) {
            if ((num[i] ^ num[i - 1]) == 1) {
                count = 1;
                break;
            }
        }
        puts(count ? "Yes" : "No");
    }
    return 0;
}

更高效的版本将使用散列 table，在线性扫描中添加每个数字并测试 num[i] ^ 1 是否已存在于散列 table 中。这将具有 O(N) 的时间复杂度，但编写起来更复杂。

如何降低 C 中关于嵌套循环的时间复杂度

How to reduce the time complexity in C regarding nested loop

c

time-complexity