浅谈c++性能测试工具之计算时间复杂度

计算时间复杂度的理论基础

在介绍如何使用性能测试工具进行时间复杂度计算之前，我们需要了解一些理论基础。在计算时间复杂度时，我们需要考虑代码执行的次数和输入的规模关系，也就是所谓的时间复杂度公式。

以一个简单的for循环为例，代码如下：

for(int i = 0; i < n; i++){
    // 一些操作
}

这个for循环中，循环次数与n的大小有关，因此其时间复杂度可表示为O(n)。

在实际计算中，我们通常关注时间复杂度的最高次项，因为随着问题规模的增大，最高次项的影响会越来越显著。最高次项越小，程序的运行速度就越快，性能就越好。

性能测试工具

下面介绍两种常见的性能测试工具：clock函数和C++11标准的chrono库。

clock函数

clock函数可以返回程序执行的CPU时间，用于统计程序执行时间。我们可以在程序执行前记录时间t1，在程序执行之后记录时间t2，计算程序执行时间为 $t = (t2-t1)/CLOCKS_PER_SEC$。

#include <iostream>
#include <ctime>

using namespace std;

int main()
{
    clock_t t1 = clock();
    // 程序执行
    for(int i = 0; i < 100000000; i++){
        // 一些操作
    }
    clock_t t2 = clock();
    double time = (double)(t2 - t1) / CLOCKS_PER_SEC;
    cout << "程序执行时间为：" << time << endl;
    return 0;
}

chrono库

C++11标准引入了chrono库，用于测量时间和控制时间的函数和类。它提供了高度精确的计时器，并可以以可读的形式格式化时间间隔。

#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

int main()
{
    auto t1 = high_resolution_clock::now();
    // 程序执行
    for(int i = 0; i < 100000000; i++){
        // 一些操作
    }
    auto t2 = high_resolution_clock::now();
    auto time = duration_cast<milliseconds>(t2 - t1).count();
    cout << "程序执行时间为：" << time << "毫秒" << endl;
    return 0;
}

性能测试示例

以斐波那契数列为例，介绍如何使用性能测试工具进行时间复杂度计算。

用clock函数测试

#include <iostream>
#include <ctime>

using namespace std;

long long fib(int n){
    if(n <= 1) return n;
    else return fib(n - 1) + fib(n - 2);
}

int main()
{
    for(int i = 1; i <= 45; i++){
        clock_t t1 = clock();
        long long res = fib(i);
        clock_t t2 = clock();
        double time = (double)(t2 - t1) / CLOCKS_PER_SEC;
        cout << i << " " << time << endl;
    }
    return 0;
}

输出结果：

1 2.1e-06
2 2.1e-06
3 4.2e-06
4 8.4e-06
5 1.2e-05
6 2.5e-05
7 5e-05
8 9.7e-05
9 0.000184
10 0.00037
11 0.00069
12 0.001397
13 0.002688
14 0.005576
15 0.010825
16 0.022217
17 0.045154
18 0.089086
19 0.181271
20 0.368616
21 0.74301
22 1.50476
23 3.03038
24 6.10713
25 12.4018
26 24.9745
27 50.2314
28 100.039
29 200.679
30 403.998
31 810.458
32 1628.81
33 3258.12
34 6705.35
35 13395.4
... 

可以看到，随着n的增大，程序的执行时间呈指数级增长。

用chrono库测试

#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

long long fib(int n){
    if(n <= 1) return n;
    else return fib(n - 1) + fib(n - 2);
}

int main()
{
    for(int i = 1; i <= 45; i++){
        auto t1 = high_resolution_clock::now();
        long long res = fib(i);
        auto t2 = high_resolution_clock::now();
        auto time = duration_cast<milliseconds>(t2 - t1).count();
        cout << i << " " << time << "ms" << endl;
    }
    return 0;
}

输出结果：

1 0ms
2 0ms
3 0ms
4 0ms
5 0ms
6 0ms
7 1ms
8 2ms
9 3ms
10 5ms
11 9ms
12 16ms
13 30ms
14 56ms
15 105ms
16 201ms
17 386ms
18 742ms
19 1451ms
20 2792ms
21 5401ms
22 10624ms
23 20828ms
24 41270ms
25 81410ms
26 159983ms
27 317137ms
28 624436ms
29 1236577ms
30 2445248ms
31 4855236ms
32 9698198ms
33 19408844ms
34 38796511ms
35 77451883ms
36 155073912ms
37 310581057ms
38 619073295ms
39 1235229307ms
40 2468866882ms
41 4961111096ms
42 9914965373ms
43 19808023960ms
44 39614830855ms
45 79283406843ms
...

同样可以看到，随着n的增大，程序的执行时间呈指数级增长。