1、算法效率的度量方法
“刚才我们提到设计算法要提高效率。这里效率大都指算法的执行时间。那么我们如何度量一个算法的执行时间呢？
正所谓“是骡子是马，拉出来遛遛”。比较容易想到的方法就是，我们通过对算法的数据测试，利用计算机的计时功能，来计算不同算法的效率是高还是低。”
摘录来自: 程杰. “大话数据结构。”
1.1、事后统计法
事后统计法：这种方主要是通过事先设计好一个测量算法执行时间的程序，用这个程序来测量算法的执行时间，比较依赖于计算机本身的计时器。
1.2、事前分析估算方法
一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
- 算法采用的策略、方法。 这是决定算法好坏的根本。
- 编译产生的代码质量。这条是由编译软件来支持。
- 问题的输入规模。
- 机器执行指令的速度。这个取决于计算机的硬件支持。
抛开计算机软件和硬件的影响，一个算法的执行时间，依赖于问题的输入规模，那什么又是问题的输入规模呢？
所谓的输入规模也就是问题的输入量。
接下来我们来看个例子：
int i, sum = 0,n = 100; /* 执行1次 */
for (i = 1; i <= n; i++) /* 执行了n+1次 */
{
sum = sum + i; /* 执行n次 */
}
printf("%d", sum); /* 执行1次 */
这段程序一种执行了1+n+1+n+1=2n+3次，这就是算法的输入量。
测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。
2、算法时间复杂度
2.1、推到大O阶方法
推到大O阶：
- 用常数1取代运行时间中的所有加法常数。
- 只保留最高阶的一项。
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的结果就是大O阶。
2.2、常数阶
下面这个算法，为什么时间复杂度不是，而是
。
int sum = 0,n = 100; /* 执行一次 */
sum = (1 + n) * n / 2; /* 执行一次 */
printf("%d", sum); /* 执行一次 */
根据我们推导大O阶的方法，第一步就是把常数项3改为1。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)。
2.3、线性阶
下面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码须要执行n次。
int i;
for (i = 0; i < n; i++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
2.4、对数阶
int count = 1;
while (count < n)
{
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于，则会退出循环。由
得到
所以这个循环的时间复杂度为。
2.5、平方阶
下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为
如果外循环的循环次数改为了m，时间复杂度就变为。
int i, j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
那么下面这个循环嵌套，它的时间复杂度是多少呢？
int i, j;
for (i = 0; i < n; i++)
{
/* 注意j = i 而不是0 */
for (j = i; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，……当i=n-1时，执行了1次。所以总的执行次数为：
用我们推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留；第三条，去除这个项相乘的常数，也就是去除
，最终这段代码的时间复杂度为
。
2.6、常见的时间复杂度
| 执行次数 | 函数阶 | 非正式术语 |
|---|---|---|
| 12 | 常数阶 | |
| 2n+3 | 线性阶 | |
| 3n2+2n+1 | 对数阶 | |
| 2n+3nlog2n+19 | nlogn阶 | |
| 6n3+2n2+3n+4 | 立方阶 | |
| 2n | 指数阶 |
常用的时间复杂度所耗费的时间从小到大依次是：
2.7、最坏情况与平均情况
2.7.1、最坏情况
“你早晨上班出门后突然想起来，手机忘记带了，这年头，钥匙、钱包、手机三大件，出门哪样也不能少呀。于是回家找。打开门一看，手机就在门口玄关的台子上，原来是出门穿鞋时忘记拿了。这当然是比较好，基本没花什么时间寻找。可如果不是放在那里，你就得进去到处找，找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间，就是找不到，时间一分一秒的过去，你突然想起来，可以用家里座机打一下手机，听着手机铃声来找呀，真是笨。终于找到了，在床上枕头下面。你再去上班，迟到。见鬼，这一年的全勤奖，就因为找手机给黄了。
找东西有运气好的时候，也有怎么也找不到的情况。但在现实中，通常我们碰到的绝大多数既不是最好的也不是最坏的，所以算下来是平均情况居多。
算法的分析也是类似，我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。
最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。”
摘录来自: 程杰. “大话数据结构。”
2.7.2、平均情况
“而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。”
摘录来自: 程杰. “大话数据结构。”
网友评论