测试自定义数据结构big-o复杂度

作为一项任务，我实现了自定义数据结构和一些测试用例，以确保它能正常工作。代码本身并不是真的需要这个问题，但你可以认为它是某种SortedList。我的问题是，我还被要求测试大O的复杂性，例如确保put（）是o（n）等。测试自定义数据结构big-o复杂度

我很难理解如何编写这样的测试。

想到的一种方法是用一个简单的计数器计算put（）方法内部的迭代次数，然后检查它是否与列表大小相等，但这需要我更改代码的名单本身来计算确切的数字，而我更愿意以适当的方式在课堂外进行，只保留一个实例。

任何想法的人？我真的很感激帮助！

2016-03-05 Mikim

由于很多原因，它被称为“时间复杂度”... –

“测试时间复杂度”意味着*性能分析*，即对采样输入的方法进行计时，绘制结果并确保它们符合您导出的理论复杂性。 – Bakuriu

@AlexeiLevenkov你是对的。固定 – Mikim

使用单元测试测试类的接口，但迭代次数不是接口的一部分。您可以使用计时器来检查不同大小的运行时行为。如果它是O（n），那么在时间和n之间应该存在线性依赖关系。

2016-03-05 21:15:40

获取测试开始时的当前时间，调用您正在测试大量次数的方法，获取当前时间，然后检查差异以获取执行时间。重复一次不同的大小输入，并检查执行时间是否符合预期的关系。

对于o（n）算法，适当的检查是将输入大小加倍大约使执行时间加倍。

2016-03-05 21:17:19 Douglas

回答