⏱️ 算法复杂度估算方法

同样是「做作业」，题目从 10 道变成 100 道，有的做法时间也翻 10 倍，有的却暴涨到 100 倍。算法复杂度就是给程序发一张「完成时间等级卡」：数据变大时，它是慢慢变慢，还是一下子跑不动？这一页学会用大 O 给它估个级。

考纲知识点：含多项式的算法复杂度
含对数的算法复杂度

📖

考纲 · 知识点详述

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

(5)掌握算法复杂度估算方法（含多项式、对数）。

📚

先学一学

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

📊 复杂度：给算法发一张「变慢等级卡」

算法复杂度不关心程序到底跑几秒（不同电脑速度差很多），而关心数据量 n 变大时，操作次数大概按什么等级增长。我们把「大概多少次」记成大 O 记法，例如 O(n) 表示大约 n 次、O(n²) 表示大约 n×n 次。

🚪 O(1)：永远只做固定几下

不管 n 是 10 还是 1000 万，都只做固定几下（比如直接报出数组第一个数），就写 O(1)——常数时间，最省事的一档。

💡 口诀：复杂度是「等级卡」不是秒表；O(1) = 做几下都行，跟 n 没关系。

🎯 看等级别看常数

n=100 时，n²=10000，比 100×n=10000 一样？不对——n² 是 n×n，100n 是 100×n。n=100 时 100n=10000、n²=10000 碰巧相等；但 n 变成 1000 时，100n=10万、n²=100万。所以等级 n² 比 100n「后劲更猛」。

💡 口诀：大 O 看趋势不看常数；数据一大，等级高的迟早跑赢（慢的）那头。

📈 含多项式的复杂度：数循环层数最方便

多项式就是像 n、n²、n³ 这样「n 自己乘自己几次」的式子。最简单估算就是数循环嵌套了几层：

🔢 数循环估多项式

· 1 层 for 循环 n 次 → 大约 n 次 → O(n)（线性）
· 2 层 for 套起来，每层 n 次 → 大约 n×n 次 → O(n²)
· 3 层 for 套起来 → 大约 n³ → O(n³)
· 有时每层不是整 n，比如外层 n、内层 n/2，仍约 n×n/2，等级还是 O(n²)。

💡 口诀：几层整循环 ≈ 几次方：一层 O(n)、两层 O(n²)、三层 O(n³)。

✂️ 取最大的那一项

算法真的要 n² + 3n + 10 步，写大 O 时只留涨得最快的 n²，写 O(n²)。n 很大时，3n 和 10 都只是小尾巴。

💡 口诀：大 O 只留「带头大哥」；n²+3n+10 约等于 O(n²)。

🔪 含对数的复杂度：每次砍一半，快到飞起

玩「1~16 猜一个数，每次告诉你大了小了」的游戏：每次都把范围砍掉一半，16 → 8 → 4 → 2 → 1，最多 4 次就猜中。这个「砍几刀才剩 1」的次数就是对数，写成 log₂n。猜 1~100 大约只要 7 次（2⁷=128），因为 100 连砍 7 刀就砍到 1 了。

⚡ O(log n)：数据翻倍只多砍一刀

范围从 1000 变到 2000，二分查找只是多砍一刀，次数几乎没涨。相比之下 O(n) 要从 1000 次变 2000 次。所以对数复杂度特别省，是很多高效算法的秘密武器（二分算法那一页的主角）。

💡 口诀：对数是「砍半几刀」；数据翻倍，只是多砍一刀。

📚 O(n log n)：每个都要处理一下，但总能砍半

很多聪明的排序（归并排序、快速排序）是 O(n log n)：大概 n 个数，每个享受「砍半」级别的便利。它比 O(n²) 快得多——给 100 万个数排序，n² 要一万亿步，n log n 只要约两千万步。

💡 口诀：n log n 是「每人砍半」的待遇；比 n² 快几个数量级。

🏁 复杂度排排坐：从快到慢认个全

🚀 常见等级从快到慢

O(1) 常数 → O(log n) 对数 → O(n) 线性 → O(n log n) → O(n²) 平方 → O(n³) 立方 → O(2ⁿ) 指数（四级认识过，翻倍再翻倍，涨得最快）。
画成折线图，指数是陡峭上天，多项式是爬坡，对数是几乎躺平的省电模式。

💡 口诀：常数最省、对数躺平、线性爬坡、平方吃力、指数上天；n 一大，等级说话。

🆚 多项式 vs 对数 vs 指数

· 多项式（n、n²、n³…）：n 自己乘自己若干次，常见于多层循环。
· 对数（log n）：每次砍一半，来自二分思想。
· 指数（2ⁿ）：每加 1 就翻倍，来自「一分为二再一分为二」的爆炸，n=30 就超过 10 亿。
· 五级考纲点名要会估算多项式和对数这两类。

💡 口诀：多项式 = 自己乘自己几次；对数 = 砍半砍几刀；指数 = 翻倍又翻倍。

🧭 怎么估：看循环、看递归、看数据范围

🔍 三步估复杂度

① 找到重复最多的那段操作（通常是最内层循环或递归调用）；② 数它大概执行多少次（n？n²？log n？）；③ 用大 O 写等级、只留最大项。

💡 口诀：找最内层、数次数、写大 O；递归别忘算调用了几层。

🗄️ 顺带一提：空间复杂度

复杂度不只看时间，也看空间（占了多少内存格子）。递归一层叠一层会占格子，深度 n 就大约占 O(n) 格——这会在递归那一页再见面。

💡 口诀：时间看快慢，空间看占地；递归多深，栈就占多高。

🌟 行业实际：为什么工程师总说「数据量大就要换算法」

给 100 个人排队，O(n²) 也无所谓；给一亿个用户算推荐，O(n²) 直接卡死。搜索引擎、地图导航背后都藏着「砍半」「每人砍半」的对数级与 n log n 级算法。先会估复杂度，才知道什么时候必须换更聪明的招。

💡 口诀：小题随便写，大数必须省；复杂度一估，换不换算法一目了然。

🎯

闯关小锦囊 · 考点提醒

复杂度是「操作次数按什么等级增长」；大 O 只留涨得最快的项，不管常数。
多项式（含多项式）：数循环层数——一层 O(n)、两层 O(n²)、三层 O(n³)。
对数（含对数）：每次砍一半——O(log n)；数据翻倍只多砍一刀。
等级从快到慢：O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → O(2ⁿ)。
估复杂度三步：找最内层（或递归）、数次数、写大 O；递归还要想空间占多深。
递归里「每次调用自己两次」会让工作量翻倍再翻倍 → 约 O(2ⁿ)；只调用一次并把范围砍半才是 O(log n)。
判断单个质数试除到根号 n（i * i <= n）就够；要筛一整张质数表，用埃氏筛或线性筛更快。

🎮

学完了？来闯关！

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

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