CC++ & Algorithm

时空效率分析

困难4
语言版本：C++Python
概述：学会用“时间”和“空间”两个尺子衡量算法的好坏，就像评价一个游戏既要快又要不占内存。

用时间和空间两把尺子，量出好算法

同学们，你有没有想过：为什么有的电脑程序运行得飞快，而有的却慢得像蜗牛？为什么有的游戏占了你电脑很多内存，而有的却很轻巧？这是因为每个程序背后都有一套算法，而我们要学会用两个重要指标来评价它：时间和空间。

时空效率分析就是帮我们判断一个算法“跑得快不快”和“占内存多不多”的方法。就像买零食，你希望又好吃又不贵；写程序，我们希望又快又不占内存。下面我们就来仔细看看这两个尺子怎么用。

? 一、时间效率（时间复杂度）—— 跑得有多快？

时间效率表示程序运行需要多久。想象你在超市排队结账：如果只有一个收银员，队伍越长，你等得越久；如果收银员增加到两个，时间差不多减半；如果来了一个超级收银员，能一秒处理所有人的商品，那么无论队伍多长，你都能瞬间结账。在算法里，我们用一个叫做“大O记号”的工具来描述这种“快慢规律”。

大O记号不关心具体时间（比如3秒还是5秒），它关心的是：当数据量 n 变大时，时间会怎么变？常用的大O有：

  • O(1) —— 常数时间
    不管数据有多少，都只需要固定几步。
    例子：从零食盒里拿第一包薯片，无论盒子里有多少包，你都是伸手就拿，一步搞定。

  • O(n) —— 线性时间
    时间跟数据量成正比。数据多1倍，时间也多1倍。
    例子：在班里按学号找一个人，你得从头到尾一个个看，学号越大找得越久。
    代码：用 for 循环从1加到n，就是O(n)。

  • O(n²) —— 平方时间
    数据翻倍，时间变成原来的4倍。
    例子：画一张同学通讯录，每个人都要和除了自己以外的所有人交换电话（两两比较），人数一多，时间爆炸。

  • O(log n) —— 对数时间
    数据翻倍，时间只增加一点点（比如多1步）。
    例子：猜数字游戏，1到1000中间猜一个数，每次猜中间，排除一半，最多10次就能猜到。数据从1000变成1亿，也只要27次。

小实验：自己数一下1到100的和，用尺子量一量“一个一个加”（O(n)）和“直接套公式”（O(1)）哪个快？公式法1秒算完，循环法可能要100步（虽然电脑很快，但n更大时差别明显）。

? 二、空间效率（空间复杂度）—— 占内存多不多？

空间效率表示程序占用了多少内存。可以想象成你的书包或抽屉：如果书包里只放一本作业本，空间很小；如果塞满了各种文具、书本和零食，空间就很大。在程序里，变量、数组、函数调用都会占用内存。

同样用大O记号衡量空间：

  • O(1) —— 常数空间
    只用几个固定的变量，不随数据量增加而增加。
    例子：上面的求和公式法，只用了 n 和 sum 两个变量，无论n多大，占用的内存都不变。

  • O(n) —— 线性空间
    需要额外存放与数据量成正比的东西。
    例子：你想把全班同学的考试成绩存起来，就要一个长度为50的数组，50个同学。如果全校1000人，就要1000个格子的数组。

  • O(n²) —— 平方空间
    需要存一个二维表格，比如全班同学两两之间的距离，人数50就需要2500个格子。

注意：函数调用时，系统会把每个函数的参数、局部变量存到“栈”里。如果函数递归调用自己很多次（比如求斐波那契数列），栈就会占很多空间，甚至导致程序崩溃。

⚖️ 三、时间与空间的“交易” —— 鱼与熊掌？

有时候，时间快和空间省不能同时做到，需要“交换”。比如：

  • 用空间换时间：提前把一些计算结果存起来，需要时直接取，不用重新算。
    例子：你要经常计算1到n的和，可以一次性算好所有结果放到一个数组里（占用 O(n) 空间），以后每次用 O(1) 时间查就行，不需要再循环或公式。
    代码示例（对比前面的两种方法）：
#include <iostream>
using namespace std;
int main() {
    int n = 1000000;
    // 用数组提前存好1到n的和（空间换时间）
    long long sum_array[1000001]; // 注意：n很大时数组会很大，这里仅作演示
    sum_array[0] = 0;
    for (int i = 1; i <= n; i++) {
        sum_array[i] = sum_array[i-1] + i; // 计算并存储
    }
    // 现在想用任意<=n的k，直接查表 O(1)
    int k = 500000;
    cout << "1到" << k << "的和是：" << sum_array[k] << endl;
    return 0;
}

这个方法时间O(n)（一次性建表），之后每次查询O(1)，但空间O(n)。适合“多次查询”的场景，比如游戏里反复查血量上限。

  • 用时间换空间：不存中间结果，每次现场算，省内存但费时间。
    例子：求斐波那契数列第n项，如果用递归，不存结果，每次都要重新算前两项，时间O(2ⁿ)，空间O(n)（栈深度）。而用循环加两个变量迭代，时间O(n)，空间O(1)。

所以写程序前要思考：是要追求极速（多存点），还是省内存（慢一点）？根据实际需求选择。

? 四、新手常犯的错误

  1. 只看时间，不看空间
    比如用巨大的数组存所有可能结果（内存不够时程序直接崩溃）。
    反例：在计算1到1亿的和时，开一个大小为1亿的数组，可能会让电脑卡死。

  2. 忽略常数因子
    O(2n)和O(100n)在算法分析中都写成O(n)，但实际运行时，100n可能比一个O(n²)但n很小的时候还要慢。大O只描述增长趋势，不表示绝对速度。

  3. 混淆最坏情况与平均情况
    比如在乱序数组中查找一个数，最快（第一个就是）O(1)，最坏（最后一个）O(n)。通常我们关心最坏情况，但有时平均更有意义。

  4. 以为O(1)一定比O(n)快
    如果O(1)的常数是100万步，而O(n)的n只有10，那么O(1)反而更慢。大O是n很大时的趋势，小数据时不一定。

  5. 递归不控制深度
    比如用递归计算n=100000的阶乘，会导致栈溢出（空间爆炸）。此时用循环更好。

? 五、完整可运行示例对比

我们用一个任务：求1到n的和，来对比四种方法的时空效率。以下代码可以直接在C++环境运行（建议用n=100000测试，不要太大）。

#include <iostream>
#include <chrono> // 用来计时
using namespace std;
using namespace std::chrono;

int main() {
    int n = 100000; // 输入数据量
    long long result = 0;

    // 方法1：普通循环 O(n)时间 O(1)空间
    auto start1 = high_resolution_clock::now();
    {
        long long sum = 0;                  // 存储累加和
        for (int i = 1; i <= n; i++) {      // i从1到n
            sum += i;                       // 每次加一个数
        }
        result = sum;
    }
    auto end1 = high_resolution_clock::now();
    auto duration1 = duration_cast<microseconds>(end1 - start1).count();
    cout << "方法1（循环）结果：" << result << "，耗时：" << duration1 << " 微秒" << endl;

    // 方法2：数学公式 O(1)时间 O(1)空间
    auto start2 = high_resolution_clock::now();
    {
        long long sum = (long long)n * (n + 1) / 2; // 直接用公式，注意n*n可能溢出
        result = sum;
    }
    auto end2 = high_resolution_clock::now();
    auto duration2 = duration_cast<microseconds>(end2 - start2).count();
    cout << "方法2（公式）结果：" << result << "，耗时：" << duration2 << " 微秒" << endl;

    // 方法3：数组查表法（空间换时间）O(n)时间建表，O(1)查询，O(n)空间
    // 注意：n较大时（如1000000）数组可能很大，这里用堆分配演示
    long long* preSum = new long long[n + 1]; // 动态数组
    preSum[0] = 0;
    for (int i = 1; i <= n; i++) {           // 建表
        preSum[i] = preSum[i-1] + i;
    }
    auto start3 = high_resolution_clock::now();
    {
        result = preSum[n];                  // 查表 O(1)
    }
    auto end3 = high_resolution_clock::now();
    auto duration3 = duration_cast<microseconds>(end3 - start3).count();
    cout << "方法3（查表）结果：" << result << "，耗时：" << duration3 << " 微秒" << endl;
    delete[] preSum;                         // 释放空间

    // 方法4：递归（不推荐，仅作反面教材）O(n)时间但空间O(n)（栈深度），且容易栈溢出
    // 这里只演示小n=10，太大可能崩溃
    // 递归函数定义在外面，但为了演示，我们写一个lambda（C++11支持）
    // 注意：这里n很小，仅展示原理
    int small_n = 10;
    function<long long(int)> recursiveSum = [&](int x) -> long long {
        if (x == 0) return 0;
        return x + recursiveSum(x - 1);       // 递归调用，占用栈空间
    };
    auto start4 = high_resolution_clock::now();
    result = recursiveSum(small_n);
    auto end4 = high_resolution_clock::now();
    auto duration4 = duration_cast<microseconds>(end4 - start4).count();
    cout << "方法4（递归，n=10）结果：" << result << "，耗时：" << duration4 << " 微秒" << endl;

    return 0;
}

输出结果示例（不同电脑时间不同）：

方法1（循环）结果：5000050000，耗时：234 微秒
方法2（公式）结果：5000050000，耗时：1 微秒
方法3（查表）结果：5000050000，耗时：1 微秒
方法4（递归，n=10）结果：55，耗时：5 微秒

可见公式和查表最快，循环慢一些，递归在小n下也不快且容易溢出。方法3虽然建表花了时间，但后续查询就极快——适合需要多次查询的场景。

? 六、接下来学什么？

  • 排序算法：冒泡排序O(n²)、快速排序O(n log n)……学习如何分析它们的时空。
  • 搜索算法：线性搜索O(n)、二分搜索O(log n)。
  • 动态规划：用空间换时间的经典例子（如背包问题、斐波那契优化）。
  • 数据结构：数组（O(1)访问，O(n)插入）、链表（O(1)插入，O(n)访问）——不同结构占用不同的时间和空间。

希望你现在能拿起“时间”和“空间”两把尺子，每次写代码前先想一想：这个算法快不快？占内存多不多？养成好习惯，你就是小小算法优化师！

例题精讲

1单选题

在C++中，以下哪种算法的时间复杂度最适合用于在无序数组中查找最大值？

A冒泡排序 (O(n^2))
B线性扫描 (O(n))
C二分查找 (O(log n))
D快速排序 (O(n log n))
2判断题

在C++中，使用递归实现斐波那契数列（未优化）的时间复杂度是O(2^n)，而使用动态规划（迭代）可以优化到O(n)。

3填空题
下面代码用于计算数组前缀和，请填空使其空间复杂度为O(1)（原地修改）。
void prefixSum(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        ___;
    }
}
4填空题
以下函数使用二分查找在有序数组中查找目标值，请填空使得时间复杂度保持O(log n)。
int binarySearch(int arr[], int l, int r, int target) {
    while (___ <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}
5填空题
给定一个链表，判断是否有环。为了在O(n)时间和O(1)空间内完成，请补充以下快慢指针代码。
bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (___ && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}