第1章 算法设计与优化策略

各位同学好，我是老刘。今天咱们聊聊算法设计与优化这个话题。说实话，我见过太多人一上来就撸代码，结果写到一半发现思路不对，又得重来。这就像盖房子不打地基，迟早要塌。

算法设计，说白了就是解决问题的思路。而优化，就是让这个思路跑得更快、用得更省。我在项目中踩过不少坑，今天把这些经验分享给你。

1.1 算法设计的一般过程

我习惯把算法设计分成五个步骤。你想想看，这跟写作文其实挺像的——先审题，再构思，然后动笔，最后检查。

1. 理解问题：搞清楚输入是什么，输出是什么，约束条件有哪些。
2. 设计思路：想清楚用什么数据结构，用什么算法思想。
3. 伪代码/流程图：把思路写下来，别急着写代码。
4. 编码实现：把伪代码翻译成C语言。
5. 测试验证：跑几个测试用例，看看对不对。

举个例子。假设我们要找数组里最大的数。你会怎么写？

// 最简单的写法
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

嗯，这里要注意：边界条件。如果数组为空怎么办？我当年就吃过这个亏，传了个空数组进去，程序直接崩了。

1.2 常见优化技巧

优化这事儿，说白了就是「用空间换时间」或者「用时间换空间」。具体怎么选，得看你的场景。

1.2.1 空间换时间

这是最常用的技巧。多开点内存，把计算结果存起来，下次直接用。

比如斐波那契数列。递归写法虽然简单，但重复计算太多了。

// 递归写法（慢）
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// 动态规划（快）
int fib_dp(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

你看，多开了一个数组，时间复杂度从 O(2^n) 降到了 O(n)。这就是典型的空间换时间。

1.2.2 预处理

有些计算可以提前做好，用的时候直接查表。我在做图像处理项目时，经常用这个技巧。

// 预处理素数表
#define MAXN 1000000
int is_prime[MAXN+1];

void init_prime() {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= MAXN; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

// 查询 O(1)
int check_prime(int x) {
    return is_prime[x];
}

1.2.3 剪枝

剪枝这个词，最早是从搜索算法里来的。说白了就是「这条路走不通，赶紧回头」。我当年写八皇后问题，没加剪枝跑了半天没出结果，加了剪枝秒出。

// 八皇后问题的剪枝
int board[8][8];
int col[8], diag1[15], diag2[15];  // 剪枝数组

void solve(int row) {
    if (row == 8) {
        // 找到解
        return;
    }
    for (int c = 0; c < 8; c++) {
        // 剪枝：检查列和对角线
        if (col[c] || diag1[row+c] || diag2[row-c+7]) {
            continue;  // 这条路不通
        }
        // 放置皇后
        col[c] = diag1[row+c] = diag2[row-c+7] = 1;
        solve(row+1);
        // 回溯
        col[c] = diag1[row+c] = diag2[row-c+7] = 0;
    }
}

1.2.4 分块

分块思想很有意思。把大问题切成小块，每块单独处理。这就像你打扫房间，一次打扫一间，比一次打扫整个房子要轻松。

// 分块求区间和
#define BLOCK_SIZE 316  // sqrt(100000)
int arr[100005];
int block_sum[320];     // 每块的和

void init(int n) {
    for (int i = 0; i < n; i++) {
        block_sum[i / BLOCK_SIZE] += arr[i];
    }
}

int query(int l, int r) {
    int sum = 0;
    int bl = l / BLOCK_SIZE, br = r / BLOCK_SIZE;
    if (bl == br) {
        // 同一块内，直接遍历
        for (int i = l; i <= r; i++) sum += arr[i];
    } else {
        // 左边不完整块
        for (int i = l; i < (bl+1)*BLOCK_SIZE; i++) sum += arr[i];
        // 中间完整块
        for (int i = bl+1; i < br; i++) sum += block_sum[i];
        // 右边不完整块
        for (int i = br*BLOCK_SIZE; i <= r; i++) sum += arr[i];
    }
    return sum;
}

1.3 算法分析工具与调试技巧

写完了代码，怎么知道它快不快？怎么找到bug？这里分享几个我常用的工具和方法。

1.3.1 时间复杂度分析

大O表示法，这个大家应该都熟悉。我习惯用「数量级」来理解它——输入规模翻倍，运行时间翻几倍？

复杂度	含义	例子
O(1)	常数时间	数组随机访问
O(log n)	对数时间	二分查找
O(n)	线性时间	遍历数组
O(n log n)	线性对数时间	快速排序
O(n²)	平方时间	冒泡排序

1.3.2 调试技巧

调试这事儿，我踩过的坑比走过的路还多。分享几个实用技巧：

• 打印大法：在关键位置加 printf，看变量值对不对。别嫌土，这招最管用。
• 边界测试：空数组、只有一个元素、全是重复值……这些边界情况最容易出bug。
• 小数据测试：先用 n=5 或 n=10 的小数据跑，手动验证结果。
• 断言检查：用 assert 检查前置条件和后置条件。

// 调试示例
int binarySearch(int arr[], int n, int target) {
    assert(arr != NULL);  // 数组不能为空
    assert(n > 0);        // 长度必须大于0
    
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        printf("left=%d, right=%d, mid=%d, arr[mid]=%d\n", 
               left, right, mid, arr[mid]);  // 打印调试
        
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

1.4 知识体系总览

下面这张图，是我整理的本章节知识体系。你可以把它当作一个「地图」，随时回来看看。

1.5 总结

这一章我们聊了算法设计的五个步骤，四种优化技巧，还有分析调试的方法。说实话，这些东西光看是学不会的，得动手练。

我建议你：

• 遇到问题先画流程图，别急着写代码
• 写完代码先跑小数据，再跑大数据
• 优化时先想清楚瓶颈在哪，别瞎优化

记住一句话：好的算法不是写出来的，是改出来的。多练、多思考，你也能写出高效的代码。

---

公众号:蓝海资料掘金营，微信deep3321