C语言如何降低时间复杂度

Question

#include<stdio.h>
#include<math.h>
int a[1000000];
int b[1000000];
int f[1000000];
int main() {
    int i, j, m, n, k, t = 0;
    int count = 0;
    scanf("%d%d", &m, &n);
    for (i = 0; i < m; i++)
    {
        scanf("%d", &a[i]);
    }
    for (j = 0; j < n; j++)
    {
        scanf("%d", &b[j]);
    }
    for(i=0;i<m;i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i] == b[j])
            {
                f[t] = a[i];
                count++;
                t++;
            }
        }
    }
    printf("%d\n", count);
    for (t=0; t<=count-1; t++)
    {
        printf("%d ", f[t]);
    }

    return 0;
}

这个程序怎么降低时间复杂度啊？

Answer 1

这个程序的目标是找出两个数组中相同的元素，并计算它们的个数，然后打印出这些相同的元素。目前的实现方式是使用两个嵌套的循环，时间复杂度为O(m * n)，其中m和n分别是两个输入数组的大小。为了降低时间复杂度，可以考虑使用更高效的数据结构和算法。

一种可能的优化方式是使用哈希集合（HashSet）来存储其中一个数组的元素，然后遍历另一个数组并检查是否存在于哈希集合中。这将大大减少时间复杂度。以下是详细步骤：

1. 创建一个空的哈希集合（可以使用C中的数据结构，或者手动实现一个简单的哈希表）。

2. 遍历第一个数组（假设是数组a），将其中的元素逐个加入哈希集合中。

3. 遍历第二个数组（数组b），对于每个元素，检查它是否存在于哈希集合中。如果存在，将它添加到结果数组中，并增加计数器。

4. 最后，输出计数器的值和结果数组中的元素。

这种方法的时间复杂度为O(m + n)，其中m和n分别是两个输入数组的大小，因为在构建哈希集合和遍历第二个数组时，每个数组元素只被访问一次，而哈希集合的查找操作通常是常数时间。

下面是修改后的代码示例：

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

#define MAX_SIZE 1000000

int a[MAX_SIZE];
int b[MAX_SIZE];
int f[MAX_SIZE];

int main() {
    int m, n;
    int count = 0;

    scanf("%d%d", &m, &n);

    // 创建一个哈希集合，用于存储数组a中的元素
    bool *hashSet = (bool *)malloc(sizeof(bool) * MAX_SIZE);
    for (int i = 0; i < MAX_SIZE; i++) {
        hashSet[i] = false;
    }

    for (int i = 0; i < m; i++) {
        scanf("%d", &a[i]);
        hashSet[a[i]] = true;
    }

    for (int j = 0; j < n; j++) {
        scanf("%d", &b[j]);
        if (hashSet[b[j]]) {
            f[count] = b[j];
            count++;
        }
    }

    printf("%d\n", count);
    for (int t = 0; t < count; t++) {
        printf("%d ", f[t]);
    }

    free(hashSet); // 释放哈希集合内存

    return 0;
}

这个修改后的代码使用哈希集合来提高查找效率，从而降低了时间复