浅谈c++性能测试工具之计算时间复杂度
作者:apocelipes 时间:2023-07-09 12:40:05
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值,同样反应了时间复杂度的偏差情况。
运行我们的测试:
可以看到,自动的时间复杂度计算基本是准确的,可以在我们对算法进行测试时提供一个有效的参考。
来源:https://www.cnblogs.com/apocelipes/p/11108483.html
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
android虚拟键盘弹出遮挡登陆按钮问题的解决方法
![](https://img.aspxhome.com/file/2023/8/126708_0s.gif)
Spring Security权限管理实现接口动态权限控制
![](https://img.aspxhome.com/file/2023/5/83445_0s.png)
android 版本检测 Android程序的版本检测与更新实现介绍
![](https://img.aspxhome.com/file/2023/7/109157_0s.png)
Java制作智能拼图游戏原理及代码
c# 通过wbemtest和WMI Code Cretor更加高效的访问WMI
![](https://img.aspxhome.com/file/2023/3/79073_0s.jpg)
C#基于Socket的TCP通信实现聊天室案例
![](https://img.aspxhome.com/file/2023/8/122618_0s.jpg)
下载软件后使用c#获取文件的md5码示例
SpringBoot集成Redis—使用RedisRepositories详解
![](https://img.aspxhome.com/file/2023/7/67017_0s.png)
SpringBoot+easypoi实现数据的Excel导出
Java中的内存泄露问题和解决办法
![](https://img.aspxhome.com/file/2023/4/84194_0s.png)
C#实现winform自动关闭MessageBox对话框的方法
Unity实现俄罗斯方块
![](https://img.aspxhome.com/file/2023/8/69198_0s.jpg)
SpringBootTest单元测试报错的解决方案
![](https://img.aspxhome.com/file/2023/4/128854_0s.png)
Java8新特性之lambda(动力节点Java学院整理)
Android简单使用PopupWindow的方法
![](https://img.aspxhome.com/file/2023/2/94252_0s.jpg)
SpringBoot构建RESTful API的实现示例
C#实现添加多行文本水印到Word文档
![](https://img.aspxhome.com/file/2023/8/92888_0s.png)
关于Spring MVC在Controller层中注入request的坑详解
![](https://img.aspxhome.com/file/2023/4/58414_0s.png)
C#中ManualResetEvent实现线程的暂停与恢复
![](https://img.aspxhome.com/file/2023/4/116454_0s.png)