C数据结构（一）：数一数代码的脚步——时间复杂度与空间复杂度

在正式开始摆弄那些数据结构之前，想先学会一件小事：评价一段代码写得好不好。程序跑起来要花时间，也要占内存，于是就有了两个衡量的维度——时间复杂度看它跑得快不快，空间复杂度看它额外占了多少地方。早年的计算机内存小得可怜，大家格外心疼空间；如今内存充裕，我们的目光更多落在时间上啦。

数一数它走了几步

时间复杂度听起来玄，其实很朴素：算法中基本操作的执行次数，就是这个算法的时间复杂度。比如数一数下面这段代码里 ++count 到底执行了多少次：

void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            ++count;              // N * N 次

    for (int k = 0; k < 2 * N; ++k)
        ++count;                  // 2 * N 次

    int M = 10;
    while (M--)
        ++count;                  // 10 次
}

准确次数是 F(N) = N² + 2N + 10。不过实际计算时，我们并不需要这么精确的数字，只要一个大概的量级就够了——这就是大 O 渐进表示法登场的地方。

大O：给次数做个减法

推导大 O 阶的三步小魔法：
① 用常数 1 取代所有的加法常数；
② 只保留最高阶项；
③ 最高阶项系数不是 1 的话，把系数去掉。

于是 N² + 2N + 10 慢慢变成 O(N²)。大 O 关心的是 N 足够大时的趋势——2N 和 10 在 N² 面前，就像零食袋碎屑，可以轻轻拍掉。

常见的几种脚步声

几个小例子走一遍：

void Func2(int N)                 // 2N + 10 次
{
    int count = 0;
    for (int k = 0; k < 2 * N; ++k)
        ++count;
    int M = 10;
    while (M--)
        ++count;
}

void Func3(int N, int M)          // M + N 次
{
    int count = 0;
    for (int k = 0; k < M; ++k)
        ++count;
    for (int k = 0; k < N; ++k)
        ++count;
}

void Func4(int N)                 // 固定 100 次
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
        ++count;
}

O(1)：Func4 里循环固定跑 100 次——常数次也是 O(1)。
O(N)：Func2 循环 2N 次；strchr 查找字符最坏要找完整串。顺便记住：算法看最坏情况。
O(N+M)：Func3 两个未知长度的循环并列着跑。
O(N²)：冒泡排序两层循环。
O(logN)：二分查找，每找一次范围折半，N 折到 1 只要 logN 次。
O(N)：阶乘递归 Fac(N-1)*N，递归了 N 次。
O(2^N)：斐波那契递归，每次裂变成两个——它只有理论意义，真的拿去算斐波那契会等到天荒地老。

把其中四位主角的真身请出来看看——冒泡、二分，还有两位递归选手：

// 冒泡：相邻的悄悄交换，O(N²)
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;
    }
}

// 二分查找：每找一次范围折半，O(logN)
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n - 1;            // 左闭右闭区间，所以有等号
    while (begin <= end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

// 阶乘递归：往下递归 N 层，O(N)
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}

// 斐波那契递归：每次裂变成两个，O(2^N)
long long Fib(size_t N)
{
    if (N < 3)
        return 1;
    return Fib(N - 1) + Fib(N - 2);
}

小提示：logN 在算法分析里默认底数为 2，有的地方会写成 lgN。

空间复杂度也顺路看一眼

空间复杂度度量的是算法额外申请的空间，同样用大 O 表示。如今它不像时间复杂度那么被在意，但递归的深度、临时数组的大小，还是值得顺手数一数的。

两道小甜点面试题

缺失数字（力扣 268 丢失的数字）：数组里装着 0 到 n，但丢了一个，要求 O(n) 找出来。排序再找要 O(nlogn)，太慢啦。求和法很可爱——用 0 到 n 的总和减去数组总和，差的就是丢掉的那个：

int missingNumber(int* nums, int numsSize)
{
    int total = numsSize * (numsSize + 1) / 2;  // 0到n的和
    int sum = 0;
    for (int i = 0; i < numsSize; ++i)
        sum += nums[i];
    return total - sum;
}

还有更巧的异或：让 nums 里每个数和 0 到 n 每个数统统异或一遍，成对出现的都会抵消成 0，最后剩下的就是落单的那个。

int missingNumber2(int* nums, int numsSize)
{
    int xor = 0;
    for (int i = 0; i < numsSize; ++i)
        xor ^= nums[i];      // 先跟数组里每个数异或
    for (int i = 0; i <= numsSize; ++i)
        xor ^= i;            // 再跟 0 到 n 异或
    return xor;              // 成对的全部抵消，剩下落单的
}

轮转数组（力扣 189 轮转数组）：把数组整体向右转 k 个位置。一次挪一格挪 k 次太辛苦，有个优雅的三段逆置——先逆置前 n-k 个，再逆置后 k 个，最后整体逆置：

// 1 2 3 4 5 6 7，k=3
// 前n-k个逆置 → 4 3 2 1 5 6 7
// 后k个逆置   → 4 3 2 1 7 6 5
// 整体逆置    → 5 6 7 1 2 3 4

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

void rotate(int* nums, int numsSize, int k)
{
    k = k % numsSize;                          // 多余的圈数省掉
    reverse(nums, 0, numsSize - k - 1);        // ① 逆置前 n-k 个
    reverse(nums, numsSize - k, numsSize - 1); // ② 逆置后 k 个
    reverse(nums, 0, numsSize - 1);            // ③ 整体逆置
}

别忘了一句 k = k % numsSize，k 比数组还长的时候它负责把多余的圈数省掉。

✿ 摘要

时间复杂度 = 基本操作的执行次数，空间复杂度 = 额外占用的空间。
大 O 三步：常数归 1、只留最高阶、去掉系数。
常见量级：O(1)、O(logN)、O(N)、O(N²)、O(2^N)；二分查找是 O(logN)。
算法分析默认看最坏情况。
缺失数字可以求和或异或找回来；轮转数组用三段逆置最优雅。

愿当下的花如你所见般美丽

可爱喵~