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

注意：运算时间等于结束时刻减去开始时刻。不过要注意，编译器优化可能会改变实际耗时，所以这更多用于粗略参考。

常见复杂度对比

常数阶 O(1)

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

int main() {
    int x = 0;
    scanf("%d", &x); // 假设输入一个整数
    printf("%d", x);
    return 0;
}

这里的基本操作次数与 N 无关，始终为常数，故复杂度为 O(1)。

线性阶 O(N)

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

案例 1：

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);
}

操作次数约为 2N + 10，忽略常数和系数后，复杂度为 O(N)。

案例 2：

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);
}

总次数为 M + N。若 M 和 N 同量级，复杂度仍视为 O(N)。

平方阶 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²)。

对数阶 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)。

递归函数

递归的复杂度取决于递归调用的深度和每次调用的工作量。

单递归：

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

每次调用执行常数时间操作，共递归 N 次，总复杂度为 O(N)。

如果在递归内部增加循环，例如在每次递归中遍历 N 个元素，那么复杂度会变为 O(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]) {
                int tmp = a[i-1];
                a[i-1] = a[i];
                a[i] = tmp;
                exchange = 1;
            }
        }
        if (exchange == 0) break;
    }
}

除了输入数组外，函数仅使用了 exchange、tmp 等有限个局部变量，不随 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;
}

在这个例子中，如果考虑输入数组本身占用的空间，整体空间消耗与数据规模 N 成正比，即 O(N)。但就算法辅助空间而言，依然是常数级的。通常情况下，我们讨论的空间复杂度更侧重于辅助空间，但在某些语境下也会包含输入数据的存储开销。