google benchmark已经为我们提供了类似的功能，而且使用相当简单。
具体的解释在后面，我们先来看几个例子，我们人为制造几个时间复杂度分别为o(n), o(logn), o(n^n)的测试用例：
// 这里都是为了演示而写成的代码，没有什么实际意义 static void bench_n(benchmark::state& state) { int n = 0; for ([[maybe_unused]] auto _ : state) { for (int i = 0; i < state.range(0); ++i) { benchmark::donotoptimize(n += 2); // 这个函数防止编译器将表达式优化，会略微降低一些性能 } } state.setcomplexityn(state.range(0)); } benchmark(bench_n)->rangemultiplier(10)->range(10, 1000000)->complexity(); static void bench_logn(benchmark::state& state) { int n = 0; for ([[maybe_unused]] auto _ : state) { for (int i = 1; i < state.range(0); i *= 2) { benchmark::donotoptimize(n += 2); } } state.setcomplexityn(state.range(0)); } benchmark(bench_logn)->rangemultiplier(10)->range(10, 1000000)->complexity(); static void bench_square(benchmark::state& state) { int n = 0; auto len = state.range(0); for ([[maybe_unused]] auto _ : state) { for (int64_t i = 1; i < len*len; ++i) { benchmark::donotoptimize(n += 2); } } state.setcomplexityn(len); } benchmark(bench_square)->rangemultiplier(10)->range(10, 100000)->complexity();
如何传递参数和生成批量测试我们在上一篇已经介绍过了，这里不再重复。
需要关注的是新出现的state.setcomplexityn和complexity。
首先是state.setcomplexityn，参数是一个64位整数，用来表示算法总体需要处理的数据总量。benchmark会根据这个数值，再加上运行耗时以及state的迭代次数计算出一个用于后面预估*均时间复杂度的值。
complexity会根据同一组的多个测试用例计算出一个较接*的*均时间复杂度和一个均方根值，需要和state.setcomplexityn配合使用。
complexity还有一个参数，可以接受一个函数或是benchmark::bigo枚举，它的作用是提示benchmark该测试用例的时间复杂度，默认值为benchmark::oauto，测试中会自动帮我们计算出时间复杂度。对于较为复杂的算法，而我们又有预期的时间按复杂度，这时我们就可以将其传给这个方法，比如对于第二个测试用例，我们还可以这样写：
static void bench_logn(benchmark::state& state) { // 中间部分与前面一样，略过 } benchmark(bench_logn)->rangemultiplier(10)->range(10, 1000000)->complexity(benchmark::ologn);
在选择正确的提示后对测试结果几乎没有影响，除了偏差值可以降得更低，使结果更准确。
complexity在计算时间复杂度时会保留复杂度的系数，因此，如果我们发现给出的提示的时间复杂度前的系数过大的话，就意味着我们的预估发生了较大的偏差，同时它还会计算出rms值，同样反应了时间复杂度的偏差情况。
运行我们的测试：
可以看到，自动的时间复杂度计算基本是准确的，可以在我们对算法进行测试时提供一个有效的参考。
以上就是浅谈c++性能测试工具之计算时间复杂度的详细内容，更多关于c++性能测试工具之计算时间复杂度的资料请关注<计算机技术网(www.ctvol.com)!!>其它相关文章！
需要了解更多c/c++开发分享浅谈c++性能测试工具之计算时间复杂度，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/634774.html