4. 算法复杂度分析：时间复杂度和空间复杂度、大O表示法、实时系统中的最坏情况执行时间（WCET）分析

各位同学，咱们今天聊点实在的。算法复杂度，说白了就是衡量你写的代码到底有多“能吃”资源——吃时间，吃内存。在嵌入式实时系统里，这可不是闹着玩的。我见过太多项目，功能都调通了，一上硬件就崩，为什么？就是没算清楚这笔账。

4.1 大O表示法：别被名字吓到

大O表示法，其实就是一个“趋势”的描述。它不关心你具体跑了多少微秒，只关心当输入规模 n 变大时，你的算法时间会怎么涨。

举个例子，你写个循环遍历数组：

for (int i = 0; i < n; i++) {
    // 做点事
}

这个就是 O(n)。n 翻倍，时间也翻倍。简单吧？

再看这个：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 做点事
    }
}

这是 O(n²)。n 翻倍，时间翻四倍。嗯，这里要注意，在嵌入式里，O(n²) 的算法能不用就别用，除非你的 n 永远是个小常数。

常见复杂度速查表：

大O名称典型场景
O(1)常数时间访问数组元素、位操作
O(log n)对数时间二分查找、平衡树查找
O(n)线性时间单循环遍历
O(n log n)线性对数快速排序、归并排序
O(n²)平方时间冒泡排序、双重循环
O(2ⁿ)指数时间递归穷举（慎用！）

我个人习惯，在写实时控制代码前，先拿笔算算复杂度。别急着敲键盘，想清楚再动手。

4.2 时间复杂度：你的代码到底跑多快？

时间复杂度，就是算法执行时间随输入规模增长的增长率。在嵌入式里，我们更关心的是“最坏情况”。

为什么？因为实时系统要求的是“确定性”。你不能说“平均情况下 1ms 搞定”，你得保证“最坏情况下也不超过 2ms”。否则，系统就可能丢帧、失控。

我举个例子，查找一个无序数组里的最大值：

int find_max(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

这个算法，不管数组怎么排列，循环次数永远是 n-1 次。所以最好、最坏、平均都是 O(n)。这种叫“确定性算法”，我喜欢。

但有些算法就不一样了。比如快速排序，平均 O(n log n)，最坏 O(n²)。你想想看，如果某个控制任务正好碰上最坏情况，系统会不会崩？

避坑指南：我曾经在一个电机控制项目里用了快速排序来排序传感器数据。平时跑得好好的，结果有一次数据恰好是逆序的，排序时间暴涨，导致控制周期超时，电机直接抖了起来。从那以后，我在实时任务里只用归并排序或堆排序——它们的最坏情况也是 O(n log n)。

4.3 空间复杂度：内存不是无限的

嵌入式系统的内存，金贵得很。你写个递归函数，每层递归压一次栈，深度一上来，栈溢出就来了。

空间复杂度，就是算法运行时占用的额外内存大小。注意，是“额外”的，输入数据本身占的空间不算。

看这个递归求阶乘：

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

空间复杂度 O(n)。因为递归深度是 n，每层都要保存返回地址和局部变量。n=1000 时，栈空间可能就爆了。

改成迭代：

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

空间复杂度 O(1)。只用了几个变量，稳得很。

我的建议：在嵌入式里，能用迭代就别用递归。除非递归深度是确定的且很小（比如树遍历深度不超过 10）。否则，你省下的那几行代码，可能换来一次栈溢出崩溃。

4.4 实时系统中的 WCET 分析

WCET，全称 Worst-Case Execution Time，最坏情况执行时间。这是实时系统的命根子。

你想想看，一个控制任务，比如每 1ms 执行一次 PID 计算。如果 WCET 是 0.5ms，那没问题。但如果 WCET 是 1.2ms，那就超时了，系统就不可靠了。

WCET 分析，就是要找出代码在“最倒霉”的情况下，到底要跑多久。这个“最倒霉”包括：

  • 数据路径最长：比如条件判断走最长的分支
  • 缓存全部失效：每次访问内存都要从主存读
  • 中断最频繁：但注意，WCET 分析通常不考虑中断抢占，那是调度的事
  • 流水线停顿最多：分支预测全错

怎么分析？两种方法：

  1. 静态分析：通过分析代码结构，计算每条指令的执行时间，累加出最坏路径。工具如 aiT、Bound-T。
  2. 测量法：在硬件上跑，用示波器或逻辑分析仪抓引脚电平，测出实际执行时间。但测量法有个坑——你很难触发到真正的“最坏情况”。

我个人习惯，两种方法结合。先用静态分析算出理论上限，再用测量法验证。如果测量结果远小于静态分析，那就看看是不是静态分析太保守了，还是测试用例没覆盖到最坏路径。

WCET 分析的关键点：

  • 循环次数要确定。不确定的循环，要分析出最大迭代次数
  • 函数调用链要完整。递归调用要小心
  • 条件分支要覆盖所有路径。特别是 else 分支
  • 硬件特性要考虑：缓存、流水线、分支预测、内存等待

4.5 实战：一个 PID 控制器的复杂度与 WCET 分析

咱们拿一个典型的 PID 控制器来练练手。代码大概长这样：

float pid_update(float setpoint, float measurement) {
    float error = setpoint - measurement;
    float p_term = Kp * error;
    
    integral += error * dt;
    float i_term = Ki * integral;
    
    float derivative = (error - prev_error) / dt;
    float d_term = Kd * derivative;
    
    prev_error = error;
    
    return p_term + i_term + d_term;
}

时间复杂度：O(1)。不管输入是什么，执行路径都一样，几条乘加指令，固定时间。

空间复杂度：O(1)。只用了几个局部变量和一个全局的 integral。

WCET 分析：这个函数没有循环，没有条件分支（假设没有抗积分饱和等逻辑），所以 WCET 就是所有指令执行时间的总和。在 100MHz 的 Cortex-M4 上，大概 1-2 微秒。稳得很。

但如果你加了抗积分饱和：

if (integral > INTEGRAL_MAX) {
    integral = INTEGRAL_MAX;
} else if (integral < INTEGRAL_MIN) {
    integral = INTEGRAL_MIN;
}

这时候就有分支了。WCET 分析就要考虑两种情况：走 if 分支、走 else if 分支、都不走。取执行时间最长的那个。虽然差别不大，但严谨的分析还是要做。

一个小技巧：我在做 WCET 分析时，会把所有条件分支都加上 __builtin_expect 或者类似的编译器提示，告诉编译器哪个分支更可能走。虽然不影响 WCET，但能优化平均性能。不过记住，WCET 只看最坏情况，编译器优化不能改变最坏路径的执行时间。

4.6 总结一下

算法复杂度分析，说白了就是两件事：算清楚时间，算清楚空间。在实时系统里，再加一件事：算清楚最坏情况。

大O表示法帮你快速评估趋势，WCET 分析帮你精确把控底线。两者结合，才能写出既高效又可靠的嵌入式代码。

嗯，今天就到这里。下次咱们聊聊实时调度，那又是另一片天地了。

← 上一章 📖 返回目录 下一章 →