困难C++7 分钟2,511 字

时空效率分析

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

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

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


? 一、时间效率(时间复杂度)—— 跑得有多快?

时间效率​表示程序运行需要多久。想象你在超市排队结账:如果只有一个收银员,队伍越长,你等得越久;如果收银员增加到两个,时间差不多减半;如果来了一个超级收银员,能一秒处理所有人的商品,那么无论队伍多长,你都能瞬间结账。在算法里,我们用一个叫做“大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) 时间查就行,不需要再循环或公式。 代码示例(对比前面的两种方法):
cpp
#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测试,不要太大)。

cpp
#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)访问)——不同结构占用不同的时间和空间。

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

同类知识点