我正在 JUnit 5 中为 Java 代码库编写单元测试，不过我很乐意使用任何语言来举例。
我有能力计算某些操作发生的确切次数。为了举一个简单的例子，我们假设排序过程中进行的比较次数。
我想编写一个单元测试，断言执行的操作数量属于四个 Big Oh 复杂性类别之一：常量、线性、nlogn 或二次。
因此，例如，我可以构建一个大小为 1 的列表，对其进行排序，并记录操作次数。然后对大小为 2、大小为 3 等的列表执行相同操作。问题是这些比较次数之间的关系可能不完全是恒定的、线性的等，但我想知道它们是四个类别中的哪一个最喜欢。
在允许一些错误和变化的同时，检测这四个类别中哪一个最适合我的数字序列的好方法是什么？理想情况下，这种方法可以考虑摊销。
作为摊销的示例，假设我想展示向数组列表添加元素需要恒定的时间。该列表的策略是数组从大小 5 开始，每次填满时都会加倍。我插入 1 个元素，然后记录操作次数（例如内存写入）。插入另一个元素，记录n个元素的操作次数，依此类推。操作数将如下所示：
1, 1, 1, 1, 1, 6, 1, 1, 1...
6 在分配新数组时发生。这个序列并不完全恒定，但恒定是四个类别的最佳拟合。
首先让我们从无聊的答案开始：一个函数是否属于给定的复杂性类别是一个纯粹的数学概念，无法通过实验进行测试。当然，您可以运行 n = 100、200 和 300 的算法，然后以某种方式比较结果，但不能保证您会从中得到任何有趣的东西。
要认识到的更有趣的事情是，复杂性类通常不是用户关心的事情。他们关心的是他们执行的操作是否需要很长时间。因此，我宁愿建议以下建议，而不是尝试测试复杂性类：在函数的使用方式上限上编写一个测试（如果实际上 n = 1000000 永远不会超过 100，则无需测试 n = 1000000） ）并断言所花费的时间/操作次数低于合理的上限。
因此，如果 n 通常低于 100，您可以使用 n = 200 进行测试，并确保它执行的操作少于 500 次（对于线性算法）。如果有人设法将算法更改为二次算法，那肯定会捕获它。如果没有，那就意味着二次算法实际上并没有差多少，所以这并不重要。
编写这样的测试会更容易，并且测试也会更接近您实际想要测试的内容。