⚡ 算法优化

同一个问题，笨办法要跑 1 小时，聪明办法 1 秒就算完！算法优化就是：少做重复的事、用数学公式代替傻循环、把 O(n) 变 O(log n)。学会「先找慢在哪，再换好方法」，你写的程序也能嗖嗖快。

考纲知识点：不同算法求解问题的差异分析
算法优化的一般方法
根据数学知识优化算法的一般方法（包括但不局限于等差、等比数列的求和公式等）

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 八级

(8)算法优化。理解不同方法求解一个问题在时间复杂度和空间复杂度上的差异，理解使用数学知识辅助求解问题的技巧（如可以用循环求出等差数列的和，也可以用数学公式求出等差数列的和），掌握一般的算法优化技巧。

📚

先学一学

花 6 分钟读完下面 5 课，再去闯关就不慌啦

🐢 慢在哪？笨办法 vs 好办法

同一个问题可以有多种算法，时间可能差出「天文数字」。比如在 n 个数里找目标：一个个看是 O(n)；先排好序再二分是 O(log n)。算 1+2+…+n：傻循环是 O(n)，用公式是 O(1)。

🏆 数学公式的威力

高斯小时候算 1+2+…+100，没有傻傻加 100 次，而是发现「首尾配对」：(1+100)×100÷2 = 5050，一次搞定！

💡 口诀：先想有没有公式，再决定要不要循环；公式一出手，O(n) 变 O(1)。

➕ 等差 / 等比求和公式

等差数列求和 = (首项 + 末项) × 项数 ÷ 2；等比数列求和也有专门公式。看到「连续加一串数」，先想能不能套公式。

🪄 空间换时间：把算过的存起来

📦 前缀和：快速求区间和

想反复问「第 l 个数到第 r 个数的和」，每次都加一遍太慢。提前算好前缀和 s[i] = 前 i 个的和，则区间和 = s[r] − s[l−1]，一次 O(1) 查出来。这就是用一点空间换大量时间。

💡 口诀：算过的存下来，别反复算；前缀和让区间和变 O(1)。

🗂️ 记忆化 / 缓存

递归里同一个子问题被算很多次，就把结果记在表里，下次直接用——这叫记忆化。网站也把热门数据存在「缓存」里，不用每次重新算。

🎯 二分答案：把「试答案」变快

有些问题不好直接算，只能「猜答案再检查」。答案在 1~M 之间，如果检查函数有单调性（答案越大越可行，或越小越可行），就能用二分快速找最小可行值。

🧮 复杂度怎么算

每次判定 check(x) 花 O(n)，二分会试 O(log M) 次 → 总时间 O(n log M)。如果 check 没有单调性，二分就不能用。

💡 口诀：二分答案省时间，前提是要有单调性；判定 O(n)、范围 M，总时间 n log M。

📖 其它常用优化

找到答案就 break 提前退出；能用快速幂把 O(e) 变成 O(log e)；循环里去掉没用的重复计算；用位运算加速。优化没有唯一答案，关键是分析慢在哪一步。

💻 读代码：一个 break 让筛法变「线性」

⚙️ 欧拉筛（线性筛）

看得懂就好，不用背。普通埃氏筛可能把一个合数标记好几次；线性筛在「i % p == 0」时立刻 break，保证每个合数只被它的最小质因子筛一次，于是总时间是 O(n)：

for (int i = 2; i <= n; ++i) {
  if (!is_composite[i]) primes.push_back(i);
  for (int p : primes) {
    if (i * p > n) break;
    is_composite[i * p] = true;
    if (i % p == 0) break; // 保证只被最小质因子筛一次
  }
}

优化前后，筛合数从「可能重复做很多次」变成「每个合数只做一次」。

💡 口诀：见最小质因子就 break，合数只筛一遍，时间变 O(n)。

🌟 优化四步曲 + 行业实际

🗺️ 拿到题目先这样想

① 先写一个一定能对的暴力方法；② 找哪里重复计算最多；③ 看有没有数学公式或规律；④ 换更快的数据结构/算法（前缀和、二分、记忆化、快速幂…）。

💡 口诀：先暴力跑对，再找重复，套公式换算法，最后测大样例。

🌟 行业实际

搜索引擎把热点结果放在缓存；数据库用索引把查找从 O(n) 变 O(log n)；视频网站提前算好「已看进度」避免重复计算；大数据平台把慢查询改写快好几万倍——优化无处不在，是工程师的日常功夫。

🎯

闯关小锦囊 · 考点提醒

同一问题不同算法复杂度不同：循环求 1+2+…+n 是 O(n)，用等差公式是 O(1)。
等差数列求和 =（首项 + 末项）× 项数 ÷ 2；等比数列也有求和公式。
少做重复计算：前缀和求区间和 O(1)；记忆化/缓存把算过的存下来。
二分答案：答案范围 M、每次判定 O(n) → 总时间 O(n log M)；前提是 check 有单调性。
快速幂把幂运算从 O(e) 优化到 O(log e)；合适的 break 能提前退出省时间。
线性筛的 break 保证每个合数只被最小质因子筛一次 → 总时间 O(n)。
优化步骤：先暴力 → 找重复 → 套数学 → 换更快算法/结构。

🎮

学完了？来闯关！

下面 15 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。