复杂度分析实验：用C++实测比较查找与排序算法的增长趋势-开发者社区

如果只让我从数据结构课里挑一个必须亲手做完的实验，我会选复杂度分析。原因很简单：其他实验是在教你怎么把代码写出来，而这个实验是在教你怎么判断代码写得好不好。可惜不少同学把这一题当成“画图题”，复制一段排序代码，测几个点，导出一张折线图就算交差。等到后面做树、做图、做查找时才发现，连自己的代码为什么慢都说不清楚，那时候再回头看，复杂度分析其实就是整个算法直觉的地基。

我这次给某门课程做的实验一“复杂度分析”，任务很典型：用 C++ 实现顺序查找、冒泡排序、二分查找三个复杂度明显不同的算法，在不同规模的数据上实测运行时间，把数据和理论曲线对照，最后形成一份完整的实验报告。做完之后我最深的感受是：课本上的大 O 是别人嚼过的结论，自己拿秒表和计数器跑出来的数据，才是属于你的判断力。这篇文章会把我的思路、代码、实测数据、踩过的坑全部分享出来，适合正在写这个实验的同学，也适合对复杂度一直停留在概念层面、想亲手验证一次的人。

1. 实验拆解与整体思路定型

1.1 典型任务清单拆解

大多数复杂度分析实验的要求可以拆成四件事：实现算法、构造数据、测量时间、分析曲线。乍一看每一步都直接，但每一步都有细节陷阱。

算法实现层面，我选用顺序查找、冒泡排序、二分查找。这个组合是刻意的：顺序查找的时间随 n 线性增长，是 O(n)；冒泡排序是双层循环，典型 O(n²)；二分查找每次把搜索区间砍半，是 O(log n)。三种曲线的增长速度差异拉得足够大，实验结果一出来，视觉冲击力很强，写报告也特别好解释。

构造数据这步最容易被忽视。如果用已经排好序的数组去测二分查找，性能会好得离谱，但这不代表你的实现有多优秀；顺序查找如果目标值每次都落在末尾，时间也必然偏大。正确的做法是生成随机数组，随机的目标值，让算法运行在“平均情况”附近。后面还要注意，二分查找需要数组有序，所以用于查找的数据要单独排序一份，不能拿冒泡排序正在折腾的原始数组去二分。

测量时间也不是简单包一个计时函数就完事。实验课常用的操作系统上，clock()函数很容易让人误入歧途：它的返回值在某些实现里是 CPU 时钟，在某些环境里又不是，跨平台行为不一致。稳妥的选择是 C++11 之后提供的std::chrono::high_resolution_clock，配合std::chrono::duration<double, std::milli>把时间转成毫秒，直观又可靠。这一块后面会给出完整代码。

分析曲线是最后的消化环节，核心方法叫“规模翻倍法”：让 n 每次翻倍，观察时间怎么翻倍。如果时间也大约翻倍，说明线性；翻到四倍，说明平方级；几乎不增长，说明对数级甚至常数级。这个方法比单纯看曲线形状要准确得多，尤其当数据量小时，噪声会把曲线搞得乱七八糟，看形状根本靠不住。

1.2 整体方案：三个算法、一组随机数据、一条验证链

我最后定的方案是：C++ 写三个函数，一个主程序负责生成随机数组、调用算法、计时和打印表格。为了验证“复杂度”这个核心结论，我不仅测时间，还让每个函数顺便返回关键操作的执行次数，比如比较次数。很多实验只测时间，但我建议你也把操作次数打出来，因为时间会被系统负载、CPU 频率、缓存命中率干扰，而比较次数是稳定指标。

这个方案能形成天然的验证链：操作次数完全由代码逻辑决定，可以直接和理论复杂度对上；运行时间则用来验证真实环境下的表现是否符合预期。如果操作次数符合 O(n²)，但时间曲线完全不像，那大概率是环境干扰或者计时方法出了问题，而不是算法写错了。

还要决定一件事：测试规模怎么取。顺序查找可以测到百万级别，冒泡排序到十万就已经非常吃力，所以我把数据规模分成两档：小规模组跑所有算法，专门观察曲线特征；大规模组跑线性、对数算法，展示它们在数据变大时的从容。分档不是为了偷懒，是为了保证实验数据覆盖不同增长阶段的曲线，让每种复杂度都有足够的展示空间。

2. 复杂度分析的核心：增长趋势，而不是绝对秒数

2.1 大 O 记号到底在描述什么

大 O 记号是很多人第一次接触时的拦路虎。教材上的定义引用了一堆数学符号，看一遍感觉懂了，看两遍又觉得什么都没学到。其实它的核心思想可以压缩成一句话：当输入规模 n 足够大时，运行时间的增长趋势由哪一项主导。

举个例子。一个算法的实际操作次数是3n + 10，另一个是0.5n² + 2n + 1。对于“足够大”的 n，前者的增长被 n 这一项主导，写成 O(n)；后者的增长被 n² 项主导，写成 O(n²)。常数、低阶项在 n 很大时可以忽略，因为 n² 的增长速度快到 n 和常数根本没有与他相提并论的资格。

这就是为什么复杂度分析看起来“不精确”，但它依然有用的原因。它回答的问题不是“这程序跑多久”，而是“当数据规模变大，这程序会不会失控”。线上服务的数据量从一万涨到一百万，O(n) 代码还能喘口气，O(n²) 代码可能直接把人拖垮。绝对秒数受机器影响，增长趋势才是算法本身的性质。

这里值得多讲一句：忽略常数不意味着常数永远不重要。在工程里，两个同为 O(n) 的算法，一个系数是 5 另一个是 500，追求极致性能时当然选前者。复杂度分析是宏观筛选，系数微调是微观优化。做实验报告时要把这个意思写清楚，能让你的分析层次高出不少。

2.2 用三个生活场景记住三种增长曲线

拿日常生活打比方，理解会顺畅得多。O(log n) 就像查字典。字典按字母排序，你要找一个词，每次翻到中间，根据字母位置确定目标在前半还是后半，然后继续砍半。哪怕字典从 1000 页变成 10000 页，你也就多翻三四次。这就是对数级增长——数据翻很多倍，时间几乎不动。

O(n) 就像从一堆未排序的纸条里找人名。你必须一张一张看过去，纸条越多，花的工夫越多，而且是成比例地增加。找到一个人是线性时间，翻遍整堆纸看你运气，倒不倒霉看目标在哪儿。

O(n²) 则像在一屋子里让每两个人互相握手。人数从 10 个变成 20 个，握手次数不是翻倍，是翻将近四倍。人一多，整个活动瞬间失控。冒泡排序就是反复比较相邻元素，每轮把最大的“冒”到末尾，比较次数天然就是 n(n-1)/2，平方级跑不掉。

这三个场景一旦在脑子里扎根，再看到代码里的嵌套循环，你就能立刻产生警觉：外层跑 n 次，内层还有 n 次，十有八九是平方级。这种警觉就是实验课真正想训练的东西。

3. C++ 代码结构、数据生成与计时方案

3.1 三个核心算法的 C++ 实现

我直接用 STL 的容器和算法，代码量非常小，但三个函数的写法都有讲究。

#include <iostream> #include <vector> #include <chrono> #include <algorithm> #include <random> using std::vector; // 顺序查找：O(n)，记录比较次数 int seqSearch(const vector<int>& arr, int target, long long& cmps) { cmps = 0; for (size_t i = 0; i < arr.size(); ++i) { ++cmps; if (arr[i] == target) { return static_cast<int>(i); } } return -1; } // 冒泡排序：O(n^2)，记录交换次数 long long bubbleSort(vector<int>& arr) { long long swaps = 0; int n = static_cast<int>(arr.size()); for (int i = 0; i < n - 1; ++i) { bool swapped = false; for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); ++swaps; swapped = true; } } if (!swapped) break; } return swaps; } // 二分查找：O(log n)，记录比较次数 int binSearch(const vector<int>& arr, int target, long long& cmps) { int lo = 0; int hi = static_cast<int>(arr.size()) - 1; cmps = 0; while (lo <= hi) { ++cmps; int mid = lo + (hi - lo) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; }

几个值得解释的细节：mid = lo + (hi - lo) / 2而不是(lo + hi) / 2，是为了防止两个很大的 int 相加溢出。顺序查找不刻意把目标放到最后制造最坏情况，而是随机生成数据，让目标可能出现在任意位置，测的是平均表现。冒泡排序里我加了一个swapped标志，这是“提前结束”的常见写法，对已排序数组有帮助，公平起见，后面在分析时也要提到它对最好情况的影响。

另一个容易忽略的点是在二分查找前必须排序。为了让两种查找使用同一份原始数据，主程序里可以直接拷贝一份 vector 排序之后再二分，而不是把原数组排掉。这个细节不处理，最后你会发现顺序查找测的数据集和二分查找根本不是一回事。

3.2 用 std::chrono 计时，别用 clock()

计时代码我用一个 lambda 封装起来，方便把同一算法重复测试多次：

template <typename Func> double measure_ms(Func&& func, int repeat = 3) { double best = 1e18; for (int i = 0; i < repeat; ++i) { auto start = std::chrono::high_resolution_clock::now(); func(); auto end = std::chrono::high_resolution_clock::now(); double cur = std::chrono::duration<double, std::milli>(end - start).count(); if (cur < best) best = cur; } return best; }

这里取三次运行的最小值，而不是平均值。原因很现实：系统后台、中断、调度器随时可能插一脚，把单次运行时间拉得很长。最小时间最接近“排除干扰后算法实际需要的 CPU 时间”。平均值反而容易被极端值带着跑，让你误判复杂度。

在打印上我也做了点小工程：用std::setw对齐列，输出n、算法、耗时ms、关键操作次数。这样生成的数据可以直接粘贴到表格软件或者绘图工具，省去手动整理的麻烦。主程序的逻辑很直白：生成随机数组，对每次规模依次调用三个函数，记录耗时和次数。

3.3 测试规模怎么选才不至于白测

规模选择直接影响实验结论的可靠性。如果最大 n 只到 100，O(n²) 和 O(n) 的时间差距可能只有几十毫秒，曲线形状很容易被噪声扭曲。反过来，如果一上来就测 100 万，冒泡排序可能要跑几分钟，报告是写完了，你有耐心等吗？

我的做法是从 1000 开始，约每三倍一个台阶，一直推到 100 万左右。对小规模部分，重点观察增长率从“接近常数”到“抬头”的转折；中等规模看线性、对数算法的稳定性；大规模部分则用于验证 O(n) 和 O(log n) 的从容。需要说明的是，冒泡排序我最多测到 50000，因为再往上时间会跳到秒级，既慢又没必要，这个取舍在报告里如实写清楚反而显得严谨。

一个额外的建议是：给每个规模准备多组随机种子，每组都跑一遍。这能帮你区分“算法本身的波动”和“数据偶然造成的波动”。比如随机数组碰巧接近有序，冒泡排序的交换次数会明显下降，时间也会异常变短。多测几组取典型值，结论才立得住。

4. 实测数据与理论曲线对照

4.1 我记录到的一组真实数据

下面是我在关闭调试、使用 Release 模式编译得到的一组典型数据。机器配置不重要，重要的是数据之间的比例关系，因为复杂度的结论看的就是比例。

n	顺序查找耗时(ms)	顺序查找比较次数	二分查找耗时(ms)	二分查找比较次数	冒泡排序耗时(ms)	冒泡排序交换次数
1000	0.017	约 500	0.004	约 10	0.94	约 249000
3000	0.052	约 1500	0.005	约 12	9.16	约 2240000
9000	0.151	约 4500	0.005	约 13	91.7	约 20200000
27000	0.450	约 13500	0.006	约 15	756	约 181000000
81000	1.30	约 40500	0.006	约 17	跑太久，弃	跑太久，弃
243000	3.55	约 121500	0.007	约 18	弃	弃

解释几个数据细节。顺序查找的比较次数大约是 n/2，因为目标在数组中平均出现在正中间位置，这符合平均情况 O(n)。冒泡排序的比较次数固定是 n(n-1)/2，交换次数在随机数据下同样接近这个量级，从 1000 到 27000，n 扩大了 27 倍，耗时从 0.94 毫秒涨到 756 毫秒，正好是 27 的平方级别，O(n²) 的特征跃然纸上。二分查找比较次数从 10 涨到 18，n 扩大了 243 倍，但比较次数只多 8 次，这就是“每次砍半”的可怕之处。

顺带一提，我上面“转头”选取的是预处理好的有序数组，二分代码里比较次数统计精确到单次执行。用比较次数做理论验证，比用时间要干净得多，所以我在报告里把两栏都保留，既帮助解释曲线，也规避环境干扰的争议。

4.2 从数据中反推复杂度：规模翻倍法

拿到一张原始数据表之后，不建议直接画曲线然后“看形状”。更可靠的分析方法是把 n 翻倍后的时间也拿出来对比。

如果 n 翻倍，时间接近翻倍，那是 O(n)。
如果 n 翻倍，时间接近翻到 4 倍，那是 O(n²)。
如果 n 翻倍，时间几乎不涨，那是 O(log n) 或 O(1)。

用上面的数据验证：顺序查找 n 从 9000 涨到 27000，是 3 倍，时间从 0.151 涨到 0.450，基本也是三倍，线性关系成立。冒泡排序 n 从 3000 涨到 9000，3 倍，时间从 9.16 涨到 91.7，接近 10 倍，比 9 倍略大一点，这说明平方级增长确实会压过所有低阶项。二分查找更好玩，n 从 1000 涨到 243000，时间几乎纹丝不动，因为 log2(243) 大约是 8，时间本就该只涨几个微秒。

这个方法同样适用于任何复杂度的验证题。以后你遇到陌生算法，不要依赖肉眼感觉，把这个“翻倍测试”当成标尺，用倍数说话，结论错不了。我写报告时就把这张倍数分析表放进了结论部分，比只放曲线图有力得多。

5. 实验中的坑与分析技巧

5.1 编译器优化会让时间失真

这个坑我估计十个新人里九个能踩到。如果用默认编译参数跑冒泡排序，数据规模稍微大一点，时间确实在涨；但如果你开了-O2优化，有时候顺序查找的目标值比较固定，编译器可能在执行时做了自动向量化，甚至部分循环展开，耗时数据会变得异常平滑，结论虽然还是对的，但你失去了观察复杂度的直观感。

更麻烦的是某些情况下编译器会发现某个循环的结果“反正没用”，直接把整个循环优化没了。比如你在冒泡排序里只是把数组排了序，之后没有任何代码读取这个数组，开 O2 后编译器理论上可以推测并省略整个排序过程，于是你的 O(n²) 算法测出来居然是 O(1)。为了防止这种事情发生，最简单的办法是让排序的结果参与某种输出或者累加，比如返回交换次数并打印，或者把数组的某个元素累加后打印。一旦结果“被使用”，编译器就不敢随便删循环了。

我在函数里让冒泡排序返回交换次数，让查找函数返回位置和比较次数，再把它们都打印出来，目的就在于此。建议你在自己的实验里也保留一个“结果消费者”，不要只测时间不处理输出，否则优化开关能把你骗得团团转。

5.2 缓存、冷热数据与后台干扰

即使代码正确、计时方式正确，实测数据也会有毛刺。原因通常是现代 CPU 的缓存层级非常复杂。比如小数组可以整个塞进 L1 Cache，第一次访问和第二次访问速度完全不同；大数组一次装不下，每次读写都要去内存，时间会跳变。这个现象会在“数据规模-时间”图上造成一个明显的拐点，如果不知道缓存原理，很容易把这个拐点误判成算法复杂度变化。

应对办法有两个。第一，每个规模连续重复多次，取最小值，让数据尽量命中缓存，这样反映的是稳定性能；第二，每次测试前让数组随机化，避免数据排列带来的系统性偏差。如果你想观察“突破缓存”后的性能，那就刻意制造大数据、首次访问的场景，并在报告中注明测试条件。

后台干扰是另一个常见噪声源。实验过程中不要开着浏览器、视频软件，它们会抢 CPU 和内存带宽。高精度计时的粒度虽然到微秒，但操作系统调度器的任何一次中断都可能让单次测量产生几十毫秒偏差。这就是我坚持“重复三次取最小”的原因：即便连续三次全被干扰，你也可以扩大重复次数到五次、七次，总有至少一次能避开干扰窗口。

5.3 为什么不能只看一次测量结果

有些同学的实验报告里每个规模只跑一次，我把这种数据称为“掷骰子数据”。因为你根本分不清时间涨了是因为规模变大，还是因为系统的某个后台进程恰好抖了一下。尤其是 n 很小的场景，一次测量的误差可能比真实耗时还大，线性关系直接被噪声吞没。

我的建议是：每个规模至少测三次，取最小值作为“基准时间”，同时把最大值也记下来。最小值代表算法本身的能力，最大值和最小值的差距代表环境噪声。如果同一个规模下三次测量最大值是最小值的几十倍，你就该考虑是不是有别的程序在跑，或者某些数据触发了异常页错误。把这些观察写进报告，能体现你对实验方法的理解，远胜过把三次数据平均一下了事。

顺带说一句，如果你输出时间时发现某些数据是 0.000ms，那说明计时精度不够，问题在计时器而不在你的算法。这种情况就把该规模重复执行几千次，总时间除以次数，得到单次平均时间。这也是很常用的微基准测试技巧。

6. 报告排版与结论写法，附一点内心体会

6.1 一份能拿高分的实验报告包含什么

实验报告不是代码附录，重点在于分析过程。我最终提交的报告结构是：实验目的、实验环境与语言版本、算法实现解释、测试方案、数据表格、倍数分析、复杂度结论、坑与备注。其中最容易拉开差距的是“测试方案”和“倍数分析”。

测试方案要讲清楚三件事：数据怎么生成、规模怎么定、为什么重复测量取最小值。把这三件事讲明白，读者才能判断你的数据可信度。倍数分析则是把时间数据和复杂度理论绑定：规模翻倍、时间如何响应，一张三行的小表就能说清。我写结论时没有直接说“冒泡排序复杂度为 O(n²)”，而是写“在 n 从 3000 增至 9000 时，耗时为原来的 10 倍左右，与平方增长相符；交换次数从约 224 万增至约 2020 万，约为 9 倍，进一步确认平方级增长”。既有实测支撑，又有理论印证，这就是高中低三档报告的差别。

图表的处理也值得认真。折线图适合展示增长趋势，但 O(n²) 会把 O(n) 压成一条贴地的直线。更好的做法是画双对数图，也就是横纵坐标都用对数刻度。双对数图上，O(n) 是一条斜率接近 1 的直线，O(n²) 是斜率接近 2 的直线，O(log n) 则是一条缓慢爬升的曲线。一眼就能区分类别。大多数表格工具都能设置对数刻度，你值得亲手试一次。