以O(N)的时间复杂度遍历二维数组的C语言代码

在C语言中，遍历二维数组（如`int arr[N][M]`）并保持时间复杂度为O(N * M)通常是通过嵌套循环实现的。你可以使用两个for循环，一个用于行，另一个用于列。以下是简单的示例：

#include <stdio.h>

void traverse2DArray(int arr[][M], int rows, int cols) {
    for (int i = 0; i < rows; i++) { // 遍历行
        for (int j = 0; j < cols; j++) { // 遍历列
            printf("%d ", arr[i][j]); // 访问元素并打印
        }
        printf("\n"); // 每行结束换行
    }
}

int main() {
    const int N = 3;
    const int M = 4;
    int arr[N][M] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; // 示例二维数组

    traverse2DArray(arr, N, M);
    return 0;
}

在这个例子中，外部循环控制行数，内部循环控制列数，所以总的时间复杂度是线性的。

相关问题

用除余法二维数组找素数 c语言

这里提供一个用除余法（也称为埃氏筛法）查找素数的C语言代码，其中使用了一个二维数组来存储筛选结果：

#include <stdio.h>

#define N 100

int main()
{
    int i, j;
    int is_prime[N+1][N+1]; // 二维数组，is_prime[i][j] 表示 i * j 是否为素数

    // 初始化数组
    for (i = 2; i <= N; i++) {
        for (j = 2; j <= N; j++) {
            is_prime[i][j] = 1;
        }
    }

    // 使用除余法筛选素数
    for (i = 2; i <= N; i++) {
        for (j = 2; j <= N; j++) {
            if (is_prime[i][j] && i * j <= N) {
                // i * j 是合数，将 is_prime[i*j] 标记为 0
                is_prime[i*j][1] = 0;
            }
        }
    }

    // 输出素数
    printf("2 ");
    for (i = 3; i <= N; i++) {
        if (is_prime[i][1]) {
            printf("%d ", i);
        }
    }

    return 0;
}

在这个代码中，我们使用一个二维数组 `is_prime` 来存储筛选结果。其中，`is_prime[i][j]` 表示 `i * j` 是否为素数。初始时，我们将所有的 `is_prime[i][j]` 都设置为 1。

接着，我们使用除余法对素数进行筛选。具体地，我们从 2 开始遍历每个数 `i` 和 `j`，如果它们的乘积 `i * j` 是合数，就将 `is_prime[i*j][1]` 标记为 0。最后，我们遍历二维数组 `is_prime`，输出所有标记为 1 的素数。

这个算法的时间复杂度为 $O(N^2 \log \log N)$，其中 $N$ 是最大的素数范围。虽然时间复杂度比较高，但是这个算法的优点是可以在有限的空间内处理较大范围的素数。

时间复杂度计算c语言

计算时间复杂度需要考虑算法的执行次数，通常使用大O符号表示。在C语言中，可以通过代码中的循环、递归等结构来分析时间复杂度。以下是一些常见的时间复杂度及其对应的代码结构：

1. O(1)：常数时间复杂度，表示算法的执行时间不随输入规模变化而变化。例如，访问数组中的某个元素。

2. O(n)：线性时间复杂度，表示算法的执行时间随输入规模线性增长。例如，遍历一个数组。

3. O(n^2)：平方时间复杂度，表示算法的执行时间随输入规模平方增长。例如，嵌套循环遍历一个二维数组。

4. O(log n)：对数时间复杂度，表示算法的执行时间随输入规模的对数增长。例如，二分查找。

5. O(n log n)：线性对数时间复杂度，表示算法的执行时间随输入规模的对数与线性成长。例如，快速排序。

6. O(2^n)：指数时间复杂度，表示算法的执行时间随输入规模指数增长。例如，求解汉诺塔问题。