用程序步分析程序执行时间

   算法在计算机编程中举足轻重，一个程序的好坏很大部分取决于算法的时间复杂度与空间复杂度。举个最简单的例子，假若你要选择最短的路去市场买菜，那么花的时间也少很多。不论游戏开发亦或是软件设计，算法都是最奇妙的那一部分。算法的空间复杂度本篇并没有涉及，因为这与程序运行过程中使用到的堆栈有密切联系。设想一下，你玩游戏进入游戏的时间由于算法设计的不够好而需要等待上几分钟，几十分钟，那该是多么差的一种游戏体验。因此学习算法的分析与设计是非常重要的。

    一个程序P所需要的时间T（P）包括编译时间以及运行时间，我们主要关注运行时间。通过计算程序的步数，我们可以对比分析下程序的运行时间。每个程序语句到底对应多少程序步由语句的类型决定。

    例如：

    注释以及声明语句（int，struct，#include，class等）记为0步；一个不涉及其他调用的赋值语句记为1步；

    一个循环语句如for，while等我们只对语句的控制部分进行计数；

    我们来看一个简单的程序：

    我们可以采用某种方法来确定一个程序求解一个特定问题实例是所需要的程序步数。我们可以在程序中加入一个新的变量count，初始值为0，我们需要在原始语句中每执行一条语句时对count增加该语句对应的步数。

    我们利用count来计算上面Sum函数的程序步：

    可以计算得到最后count=2n+3步数。

    接下来我们来看一个递归程序，分析下其程序步数

    该程序计算的是a[0]+.......+a[n]的值。我们进行以下分析：

    由于存在递归部分，通过程序我们无法迅速计算count的值，我们将本程序步数记为T（n）【n为数组长度】，那么可以得到下列表示：

    如果n=0，T（n）=2；

    如果n>0，T（n）=2+T（n-1）；

    我们可以发现，上述存在递归式，我们可以不断进行替换：

    T（n）=2+T（n-1）

    =2+2+T（n-2）

    =2+2+2+T（n-3）

    .....

    =2n+T（0）

    =2n+2

    接下里我们来分析一下矩阵相加这个程序

    分析可得程序步数为2mn+2m+1；

    注意，这个程序我们计算的是a[m][n]，b[m][n]相加，如果m<n，我们上面的程序还算可以，但如果m>n，那我们应当交换下两个for循环的位置，程序步变为2mn+2n+1，执行更快。

    但不是每个算法都能直接计算运行次数,例如下面的例子：

   我们很难计算算法中的程序到底执行了多少次，因为运行次数依赖于x在数组中的位置，如果第一个元素就是x，则执行1次(最好情况);如果最后一个元素是x，则执行n次(最坏情况)；如果分布概率均等，则平均执行次数为(n+1)/2。

    因此对于某些算法来说，可以分为最好、最坏和平均情况。但我们考查一个算法通常考查最坏的情况，而不是考查最好的情况，最坏情况对衡量算法的好坏具有实际的意义。