数据结构：常见时间复杂度与空间复杂度解析

注意头文件应为 <time.h>，且变量 n 需提前定义。

3. 常见复杂度对比

3.1 常数阶 O(1)

无论输入规模如何，操作次数固定。

int main() {
    int x = 0;
    scanf("%d", &x);
    printf("%d", x);
    return 0;
}

这里只有几条语句，T(N) = 3，根据规则取 O(1)。

3.2 线性阶 O(N)

操作次数与输入规模成正比。

void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
    printf("%d\n", count);
}

计算得 T(N) = 2N + 10，忽略常数和系数后为 O(N)。

若涉及两个变量 M 和 N：

void Func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; ++k) {
        ++count;
    }
    for (int k = 0; k < N; ++k) {
        ++count;
    }
    printf("%d\n", count);
}

此时 T(N) = M + N。如果 M 远小于 N，通常记为 O(N)。

3.3 平方阶 O(N²)

嵌套循环的典型特征。

int main() {
    int n = 100000;
    int x = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            x++;
        }
    }
    return 0;
}

内层循环执行 N 次，外层也是 N 次，总次数 N * N，即 O(N²)。

3.4 对数阶 O(log N)

每次迭代将问题规模减半。

void func5(int n) {
    int cnt = 1;
    while (cnt < n) {
        cnt *= 2;
    }
}

假设执行次数为 x，则 2^x = n，解得 x = log₂n。最坏情况时间复杂度为 O(log n)。

3.5 递归函数

递归的时间复杂度是所有递归调用次数的累加。

单递归：

long long Fac(size_t N) {
    if (N <= 1) return 1;
    return Fac(N - 1) * N;
}

每次调用执行一次乘法，共调用 N 次，复杂度为 O(N)。

如果在递归中加入循环（例如 N 次递归，每次内部循环 N 次），复杂度则会变为 O(N²)。

双递归：

典型的如斐波那契数列的非优化实现，调用树呈指数级增长，复杂度通常为 O(2^N)。

二、空间复杂度

空间复杂度是对算法运行过程中临时占用存储空间大小的量度，同样使用大 O 渐进表示法。在实际编程中，我们更关注时间复杂度，但在嵌入式开发等场景下，空间开销至关重要。

注意：函数栈帧（参数、局部变量）通常在编译期确定，空间复杂度主要看运行时显式申请的额外空间。

冒泡排序 O(1)

void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end) {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i) {
            if (a[i-1] > a[i]) {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0) break;
    }
}

该算法仅使用了 exchange 等有限个局部变量，不随 N 增长而增加，因此空间复杂度为 O(1)。

三个反置 O(N)

void reverse(int* nums, int left, int right) {
    while (left < right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

int main() {
    int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 0;
    scanf("%d", &k);
    k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

这里创建了一个数组 nums，其空间大小与元素个数 N 成正比，因此空间复杂度为 O(N)。通常空间复杂度常见为 O(1)、O(N) 或 O(N²)，其中 O(1) 最优。

总的来说，算法设计时优先保证时间效率，但在资源受限环境下需兼顾空间开销。