1 前言

如果我们用C语言或者C++实现了相同问题的不同算法，要比较各种算法的优劣程度，就需要测定依据某一算法编写的程序运行时间。程序的运行时间是衡量算法优劣程度的标准，当计算机依据不同算法使用某一语言编写出一个程序时，该程序运行越快，说明其所用的算法越好。那么，该如何去测定程序的运行时间呢？一般来说，我们常用的是调用特定的头文件，使用其包含的函数来进行时间的测定。

---

2 程序测时

2.1 准备

• 如果使用者使用C语言，只需在源代码头部加上#include <time.h>。
• 如果使用者使用C++，只需在源代码头部加上#include <ctime>。

对于学习过C语言和C++的程序员来说，这两条预编译指令并无差别，无非是头文件的不同。在测时代码中两者使用的相关函数都具有同样的名称与意义，因此并无显著差别，并且现在的C++编译器均兼容了C语言，所以也不必过于拘泥于time.h与ctime这两个头文件，测时的基本框架是相同的。

2.2 测试函数

头文件里提供了clock()函数、CLK_TCK常数以及clock_t数据类型，我们编写测时代码都需要用到它们。现在来详细介绍各自的功能：

• clock()：可以用来测定从程序开始运行到该函数被调用时所耗费的时间，函数的数据类型为clock_t。耗费时间的单位为clock tick，即时钟打点数。
• clock_t：时钟打点数的数据类型，单位为clock tick。
• CLK_TCK：机器时钟每秒所走的时钟打点数，单位为clock tick。对于特定的机器，其CLK_TCK为常数。

---

3 测时框架

我们可以用头文件提供的这些东西编写相应的代码来进行程序测时，不过大多数代码都相差不大，因此我们可以使用以下代码框架进行程序测时。

#include <cstdio>
#include <ctime>

clock_t start,stop; //定义clock_t数据类型的变量start，stop，用以接收clock()返回的数据，单位为clock tick。
double duration;  //被测量程序的运行时间，单位为秒。

int main()
{
    /*
    此区域的代码不在测时的范围之内，各种准备工作可以写在此处。
    */

    start = clock();   
    function();  //被测函数
    stop = clock();
    duration = ((double)(stop - start))/CLK_TCK;  //实际被测函数的运行时间

    /*
    其他处理代码可以写在此处，可以输出duration的值。
    */
    return 0;
}

---

4 测时实例

4.1 问题描述

请求出1+2+3+4+...+100的值。

4.2 代码

#include <cstdio>
#include <ctime>

const int MAXN = 100000;  //循环次数

void TestFunc1();  //实现算法1的函数
void TestFunc2();  //实现算法2的函数
double TestTime(void (*func)());  //测时函数，函数内为测时框架代码，使用函数指针作为参数传递不同函数。

int main()
{
    //主函数输出不同算法运行的时间
    printf("%f\n",TestTime(TestFunc1));
    printf("%f\n",TestTime(TestFunc2));

    return 0;
}

void TestFunc1()
{
    int ans = 0;
    for(int i = 1; i <= 100; ++i)
        ans += i;
    //算法1采用循环求和的方法
}

void TestFunc2()
{
    int ans = 0;
    ans = 100*(1+100)/2;
    //算法2采用等差数列前n项和的公式，这里的n=100。
}

double TestTime(void (*func)())
{
    //测试框架
    clock_t start,stop;
    double duration;

    start = clock();

    for(int i = 0; i < MAXN; ++i)
        func();
    /*
    由于计算机运行速度太快，程序运行时间极短，便使用一层循环来积累时间，
    MAXN为循环次数，这里循环次数设定为100000。
    经检验，MAXN越大，不同算法运行时间的差异越大，本代码中算法1运行的时
    间多于算法2，说明算法2优于算法1。
    */

    stop = clock();
    duration = ((double)(stop - start))/CLK_TCK;

    return duration;
}

4.3 简单分析

由题目的描述很容易就可得出算法1，即循环求和累加的方法，但是如果要成为一个优秀的程序员必须要懂得算法的优化。我们也很容易可以看出题目中的数字之间的关系，是首项为1，公差为1的等差数列，我们要求的是前100项的和。以此我们衍生出了算法2，利用等差数列前n项和公式进行求解。因为计算机的运行速度太快，代码里特别增设一层循环用以累计运行的时间，这样才能被测量到可判断的时间。运行程序的结果如下（结果不是固定的，与机器有关，但是无论什么结果算法1运行时间都要比算法2来得慢）：

算法1和算法2对比
从这个结果里我们知道算法2优于算法1，这是为什么呢？我们可以从两种算法的代码里进行简单的分析。
算法1：TestFunc1()函数里使用了一层循环，可以说其时间复杂度为O(n)，对本题而言n=100。
算法2：TestFunc2()函数里不含循环，利用公式进行求解，其中只进行了一次加法运算，一次乘法运算与一次除法运算，它耗费的时间是线性的，其时间复杂度为O(1)。
对于算法1，若n不是100，而是10000甚至100000时，其运行时间与算法2的差距会越来越大。而对于算法2而言，不论n怎么变，始终进行的就是那几次运算，复杂度始终不变。综上所述，算法2是最优的算法，达到了常数级的运算。

---

5 总结

学习了C/C++的测时方法，我们就可以通过这一测时框架来对我们编写代码里的核心算法进行时间测试，这对于我们进行算法分析和设计具有极大的参考价值。要设计优秀的算法，必须要懂得如何测时~