本地图说明如何 计算 算法的代价：它根据数据规模执行多少次操作， n，以及当 n 增大时它如何增长。
代价是一种 n 的函数。秒数取决于计算机；操作次数不取决于。
点击每个方框查看其说明。箭头 ← → （或底部的按钮）进入下一个，并且 Esc 关闭它。看过之后会出现 ✓；点击它可以取消。带有「?」的方框属于其他级别。
本地图说明如何 计算 算法的代价：程序执行多少次操作。每个方框都有简短的说明，有些还附有练习。
一个算法更 快 当它做 更少的操作.
点击每个方框查看其说明。箭头 ← → 进入下一个，并且 Esc 关闭它。看过之后会出现 ✓。
初中四年级 ESO（面向有能力的学生）。 简化版本：计算规则、关于 n 的阶数和二分查找。不含正式的 O(·) 记号、算法图表和操作方框。
对应于： 数字化（初中四年级）（计算思维：标准 3.1 和 3.2，逻辑清晰且高效的算法）。
建议活动： 数一数一个循环的操作次数，然后用二分查找检验它要走多少步。
PTD-I · 高中预科一年级。 新增了计算规则（顺序、条件和循环）、O(·) 记号、增长图与时间图、线性查找和选择排序。时间实验（毫秒）不再是重点：测量的是操作次数。
对应于： 程序设计与数据处理 I：CEsp1（算法的分析与设计，关于计算代价的标准 1.3）和 CEsp3（数据结构上操作的效率与复杂度）。
建议活动： 假设每秒 10⁹ 次操作、n = 10⁶，计算线性查找（n）和冒泡排序（n(n−1)/2）各需要多久，并与时间图比较。
PTD-II · 高中预科二年级。 与 PTD-I 内容相同：计算规则、O(·) 记号、增长图表，以及查找与排序算法。
对应于： 程序设计与数据处理 II：CEsp1（算法与计算思维）。
建议活动： 手工比较 n = 1 000 000 时的线性查找和二分查找，并说明差异的原因。
带有 «?» 在此级别中是隐藏的：点击一次即可展开并显示其关系，再点击一次打开窗口，看过之后再点击一次又会隐藏。按钮 🔗 复制一个包含级别和已展开方框的链接。
选择器 级别 会改变地图和所有窗口。地址中保存级别（?edad=4eso, ptd1 或 ptd2）以及已展开的方框（&ver=casos,fonts).
说一个算法快，就要说明快在哪方面。秒数取决于计算机、系统以及正在运行的内容。因此我们计算 操作.
比较两个算法时，问问自己： 什么在增长，增长多少?
计算代价衡量程序根据数据规模（n）。请注意两点： 时间 （操作次数）和 内存 （占用多少空间）。
一个算法的计算代价是基本操作 它做的操作，根据数据规模而定， n。秒数取决于计算机；操作次数不取决于。
一次基本操作（赋值、加法、比较或访问某个位置）的代价是 1。计算的是 最坏情况，这正是对任意数据都能保证结果的原因。
| 函数 T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
秒数不适合用来比较算法。请数 操作 并看看 增长 当 n 增大时。
规模 n。 所有公式都依赖于一个规模， n：算法接收的数据数量。计数之前先定义 n（根据问题，可以是元素个数、位数或行数）。
程序依次执行指令。计算代价时，把指令相加。如果有循环，就乘以重复的次数。
一条简单指令的代价是 1。循环把循环体的代价乘以重复次数。
一个程序由四种结构组合而成。总代价通过对每种结构应用一条规则来计算。
| 结构 | 代价规则 | 示例 |
|---|---|---|
| 简单指令 | 1 | x ← x + 1 → 1 |
| 顺序 | 代价之和 | A；然后 B → T(A) + T(B) |
| 条件 | 测试 + 最贵的分支 | 若…则…否则… → 1 + 最大(T₁, T₂) |
| 循环 | 迭代次数 × 循环体代价 | 对 i 从 1 到 n：x ← x + 1 → n |
当你不知道条件语句会执行哪条分支时，就按最贵的那条计算：也就是 最坏情况.
循环的代价是其循环体的代价乘以重复次数。一次操作不显眼；一百万次操作就很明显了。
| 结构 | n = 1 000 时的操作次数 | n = 1 000 000 时的操作次数 |
|---|---|---|
| 一个循环 | 1 000 | 1 000 000 |
| 两个嵌套循环 | 1 000 000 | 1 000 000 000 000 |
数一数最内层循环体执行了多少次。一个 n 步的循环做 n 次操作；两个 n 步的嵌套循环做 n · n 次。
两个嵌套循环是 O(n²)；一个循环， O(n).
看起来简单的结构（“只是一个循环”）内部可能隐藏着一次查找。请始终检查循环体内部有什么。
循环会重复执行其循环体。总代价是循环体的代价乘以重复次数。
| 结构 | n = 1 000 时的操作次数 | n = 1 000 000 时的操作次数 |
|---|---|---|
| 一个循环 | 1 000 | 1 000 000 |
| 两个嵌套循环（n · n） | 1 000 000 | 1 000 000 000 000 |
| 两个循环，第二个到 i 为止 | 500 500 | 500 000 500 000 |
一个循环是 O(n)。两个嵌套循环是 O(n²)。直到 i 的嵌套循环进行 n(n+1)/2 步：同样 O(n²)，因为我们忽略常数 ½。
看起来简单的结构（“只是一个循环”）内部可能隐藏着一次查找。请始终检查循环体内部有什么。
冒泡排序比较相邻元素，若顺序错误就交换。它重复进行多趟，直到不再需要交换。它是理解代价的典型算法，因为一切都可以计数。
| n（数据） | 比较次数（最坏情况） | 交换次数（平均） |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
每一趟把最大值放到末尾。对于 n 个数据，第一趟进行 n−1 次比较，下一趟 n−2 次，依此类推直到 1。最坏情况下总计： n(n−1)/2.
注意：如果 你把数据乘以 10，工作量乘以 100.
这是 O(n²)。比较次数按 n 的平方增长。
冒泡排序比较每一对相邻元素，并交换顺序错误的两个。每一趟之后，最大值都会留在末尾。
| n（数据） | 比较次数（最坏情况） | 交换次数（平均） |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
第一趟进行 n−1 次比较，第二趟 n−2 次，依此类推直到 1。最坏情况下合计：(n−1) + (n−2) + … + 1 = n(n−1)/2，即 O(n²).
时间图表：时间与操作次数成正比。每秒 10⁹ 次操作时，10⁶ 次操作耗时 1 毫秒。
如果列表有序，就不必全部查看。查看中间元素，并排除不可能包含目标的一半。每一步把规模减半。
列表是 1、2、3…n：无需把它全部保存在内存中，因此可以用 10 亿来测试。
| n（数据） | 二分步数（最坏情况） | 线性比较次数（最坏情况） |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
每一步做一次比较并排除一半。步数约为 log₂ n。因此 10 亿个数据只需 30 步。
这是 O(log n).
二分查找只有在列表已经 有序。对它排序也有代价。
二分查找查看有序列表的中间元素，并排除不可能包含目标的一半。每一步除以 2。
列表是 1、2、3…n。只计算步数：无需把它保存在内存中。
| n（数据） | 步数（最坏情况） | 线性查找（最坏情况） |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
每一步把规模减半：k 步后剩下 n / 2ᵏ 个元素。由于 n / 2ᵏ = 1 时 k = log₂ n，代价为 O(log n).
二分查找只有在列表已经 有序。对它排序也有代价。
时间图表：时间与操作次数成正比。每秒 10⁹ 次操作时，10⁶ 次操作耗时 1 毫秒。
当数据增长时，代价以特定的速度增长。记号 O(·) 只保留这种节奏，忽略常数。
O(log n) 增长非常缓慢：当 n 从 1 增加到 20 时，它只达到 ≈ 4.3，而 O(n) 达到 20。
n 较小时，所有曲线看起来都很接近；从 n ≈ 10 起，二次曲线与其他曲线分开。
| 函数 | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1)：代价与 n 无关。O(log n)：每一步除以 2（二分）。O(n)：与 n 成正比（线性查找）。O(n log n)：优秀排序算法的典型代价。O(n²)：两个嵌套循环（冒泡、选择）。
当 n 乘以 10 时：O(n) 的代价乘以 10；O(n²) 乘以 100；O(log n) 几乎不变。
忽略常数和小项：3n² + 5n 的复杂度是 O(n²).
关于 n 的阶数说明了数据增多时代价如何增长。这是本地图最重要的思想。
当 n 乘以 10 时，O(n) 的代价也乘以 10，而 O(n²) 的代价乘以 100。
如果代价是 O(n)，工作量与数据同步增长。如果是 O(n²)，数据加倍时工作量变为 4 倍。
重要的是 如何增长，而不是确切的操作次数。
同一个算法根据数据的不同，耗时可能多也可能少。因此分析会区分三种情况： 最好, 平均 和 最坏.
| 情况 | 冒泡排序 | 二分 |
|---|---|---|
| 最好 | n−1 次比较（列表已有序） | 1 步（中间值就是要找的值） |
| 平均 | ≈ n²/2 次比较 | ≈ log₂ n 步 |
| 最坏 | n(n−1)/2 次比较 | ⌊log₂ n⌋ + 1 步 |
如果比值接近 2，增长大致是线性的；如果接近 4，则是二次的。浏览器的噪声使结果不够精确，因此取 3 次重复的中位数。
要评价一个算法，需要查看以下数据的 最坏情况 （最能让它工作的那些），但也包括最常见的平均情况。
对某个具体情况的一次测量，并不能说明哪个是最坏的。先分析情况，再测量。
线性查找逐个查看元素，直到找到目标。它是最简单的方法，也是与二分查找比较的参照。
将每个元素与要查找的值比较，直到找到它或到达末尾。
| 情况 | 比较次数 | 当 n = 1 000 000 时 |
|---|---|---|
| 最好（是第一个） | 1 | 1 |
| 平均（在中间） | n / 2 | 500 000 |
| 最坏（是最后一个或不存在） | n | 1 000 000 |
代价是 O(n)：每个元素最多检查一次。
给出代价时，请说 哪种情况 是：最好、平均还是最坏。
时间图表：时间与操作次数成正比。每秒 10⁹ 次操作时，10⁶ 次操作耗时 1 毫秒。
选择排序在未排序部分中找最小值，并把它放到前面。重复这一过程，直到整个列表有序。
第一趟在 n 个元素中找最小值（n−1 次比较），并把它放到第一个位置。下一趟在 n−1 个元素中查找，依此类推直到最后一个。
| n（数据） | 比较次数（总是） |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
合计：(n−1) + (n−2) + … + 1 = n(n−1)/2，即 O(n²) 在所有情况下。最多进行 n−1 次交换。
选择排序总是进行相同的比较；冒泡排序如果列表已经有序，可以提前停止。
时间图表：时间与操作次数成正比。每秒 10⁹ 次操作时，10⁶ 次操作耗时 1 毫秒。
插入排序取出每个元素，并把它放到已排序部分中正确的位置。
在 最坏情况 （逆序列表）进行 n(n−1)/2 次比较： O(n²)。在 最好情况 （已排序列表）只进行 n−1 次： O(n).
当列表几乎已经有序时，插入排序很快。
归并排序把列表对半分，分别排序每一半，然后再合并。
每一层划分进行 n 步，共有 log₂ n 层。代价为 O(n log n) 在所有情况下。
对于大型列表，它比冒泡排序快得多。
测量很容易出错。以下是最常见的错误及如何避免。
在说某个算法更快之前，先问问自己： 使用什么数据、在什么机器上、测量了几次。
阅读每个情境并选择 哪个概念 解释该情况。如果你选的是也相关但不是主要的那个，我们会告诉你。
一个程序在循环中把 100 万个数相加。哪个概念解释了为什么代价很高？
一个程序在循环中把 100 万个数相加。哪个概念解释了为什么代价很高？
你在一个有一百万个数的有序列表中查找 42。你看中间，排除一半，大约 20 步就找到了。这是什么算法？
一个算法遍历列表，比较相邻元素并交换它们。对于逆序列表，它做 n(n−1)/2 次比较。这是什么算法？
当数据加倍时，一个算法的耗时变为 4 倍。哪个概念描述了它的代价如何增长？
你在一个有 n 个元素的无序列表中查找一个数，逐个与每个元素比较，直到找到它。这是什么算法？
一个算法在未排序部分中查找最小值，并把它放到前面。即使列表已经有序，它也要做 n(n−1)/2 次比较。这是什么算法？
本地图汇集了算法分析的经典概念以及巴利阿里群岛课程的目标。你可以在这里核对并深入学习。