数据结构溢彩加强版——（二）算法篇
算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
@[toc]
两种算法的比较
要求写一个求1+2+3+……+100结果的程序
int i , sum = 0, n = 100;
for(int = 1; i <= n; i++)
{
sum = sum + i;
}
printf("%d ", sum);
用程序来实现如下：
int sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d "sum);
算法的特征
1.输入输出
2.有穷性
有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
3.确定性
4.可行性
可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
算法设计的要求
1.正确性
正确性：算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。
但是算法的“正确”通常在用法上有很大的差别，大体分为一下四个层次：
（1）算法程序没有语法错误。
（2）算法程序对于合法的输入数据能够产生满足要求的输出结果。
（3）算法程序对于非法的输入数据能够得出满足规格说明的结果
（4）算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
2.可读性
3.健壮性
健壮性：当输入数据不合法时，算法也能做出相应的处理，而不是产生异常或莫名奇妙的结果。
4.时间效率高和存储量低
设计算法应该尽量满足时间效率高和存储量低的需求。
算法效率的度量方法
1.事后统计方法
1.事后统计法
衡量算法效率最简单的一个办法就是把算法变成一个程序，然后再机器上执行，然后计时，这就是事后统计法。
这样显然有一些缺点：
（1）必须到机器上去计算，而且这个计算不只是一次，我们要用多组数据对其进行重复的运算，然后得到一个统计的结果，那么你要算上机器的时间。
（2）肯定会有一些其他因素掩盖算法的本质。
2.事前分析估算法
通常比较算法好坏，都是在设计算法的时候就应该知道它的效率，这就是事前分析估算法。
说明： 要比较两个算法，实际上在设计的时候就做着工作来衡量它们的效率，因此更常用的方法是事前分析估算法。
我们来看看两种求和的算法：
第一种算法：
int i, sum = 0, n = 100; /*执行一次*/
for(i = 1; i<= n; i++) /*执行了n+1次*/
{
sum = sum + i; /*执行n次*/
}
printf("%d ",sum); /*执行一次*/
第二种算法：
int sum = 0, n = 100; /*执行一次*/
sum = (1 + n) * n / 2; /*执行一次*/
printf("%d "sum); /*执行一次*/
显然，第一种算法，执行了1+(n+1)+n+1次=2n+3次；而第二种算法，是1+1+1=3次。
我们再来延伸一下上面这个例子：
int x, j, x = 0, sum = 0, n = 100; /*执行1次*/
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
x++; /*执行n*n次*/
sum = sum + x;
}
}
printf("%d ",sum); /*执行1次*/
在这个例子中，i到1到100，每次都要让j循环100次，而当中x++和sum=sum+x;其实就是1+2+3+……+10000，也就是1002次，所以这个算法当中，循环部分的代码整体需要执行n2。
此时你会看到，测试运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，运行时间与这个数成正比。最终，在分析程序的运行期间时，最终要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
函数的渐近增长
我们先通过一个例子来看一下，假设两个算法的输入规模都是n，算法A要做2n+3次操作，可以理解为先有一个n次的循环，执行完成后，再有一个n次的循环，最后有三次赋值或运算，共2n+3次操作，算法B要做3n+!次操作，那么这两个算法那个更快呢？
当n = 1时，算法A的效率不如算法B(次数比B多一次)。而当n = 2时，两者效率相同；当n >2时，算法A就开始优于算法B了，随着n的增加，算法A比算法B越来越好了。我们可以说，算法A总体上要好于算法B。
此时我们给出这样的定义，输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐进增长的。
函数的渐进增长：给定两个函数 f (n) 和 g (n)，如果存在一个整数N，使得对于所有的 n > N，f (n)总是比 g (n) 大，那么，就可以说 f (n) 的渐进增长大于 g (n) 。
从中我们可以发现，随着n的增大，后面的+3还是+1其实是不影响最终的算法变化的，所以，我们可以忽略这些加法常数。
再来看第二个例子，算法C是4n + 8，算法D是2n2 + 1。
当n≤3的时候，算法C要差于算法D（因为算法C次数比较多），但当n>3后，算法C的优势就越来越优于算法D了，到后来更是远远胜过。而当后面的常数去掉后，我们发现其实结果没有发生改变。甚至我们再观察发现，哪怕去掉与n相乘的常数，这样的结果也没发生改变，算法C′的次数随着n的增长，还是远小于算法D′。也就是说，与最高次项相乘的常数并不重要。
再看第三个例子，算法E是2n2+3n+1，算法F是2n3+3n+1。
请添加图片描述
当n=1的时候，算法E与算法F结果相同，但当n>1后，算法E的优势就要开始优于算法F，随着n的增大，差异非常明显。通过观察发现，最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快。
来看最后一个例子。算法G是2n2，算法H是3n+1，算法I是2n2+3n+1。
这组数据应该就看得很清楚。当n的值越来越大时，你会发现，3n+1已经没法和2n2的结果相比较，最终几乎可以忽略不计。也就是说，随着n值变得非常大以后，算法G其实已经很趋近于算法I。于是我们可以得到这样一个结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。
判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的。根据刚才的几个样例，我们发现，如果我们可以对比这几个算法的关键执行次数函数的渐近增长性，基本就可以分析出：某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法。这其实就是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。
算法时间复杂度
1.算法时间复杂度定义
在进行算法分析时，语句总的执行次数T (n)是关于问题规模n的函数，进而分析 T (n) 随 n 的变化情况并确定 T (n) 的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T (n) = O (f(n))。它表示随问题规模 n 的增大，算法执行时间的增长率和 f (n) 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中 f (n)是问题规模 n 的某个函数。
这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
显然，由此算法时间复杂度的定义可知，在函数的渐进增长一文中前三个例子的求和算法的时间复杂度分别为O(n)，O(1)，O(n2)。我们分别可以称之为，O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶，当然，还有其他的一些阶，请接着往下看！
2.推导大o阶方法
(1)．用常数1取代运行时间中的所有加法常数。
(2)．在修改后的运行次数函数中，只保留最高阶项。
(3)．如果最高阶项存在且不是1，则去除与这个项相乘的系数，得到的结果就是大O阶。
3.常数阶
首先顺序结构的时间复杂度。下面这个算法，也就是高斯算法，为什么时间复杂度不是O(3)，而是O(1)。
int sum = 0, n = 100; /* 执行一次 */
sum = (1 + n) * n / 2; /* 执行一次 */
printf("%d",sum); /* 执行一次 */
这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法，第一步就是把常数项3改为1。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)。
另外，我们试想一下，如果这个算法当中的语句sum=(1+n)*n/2有10句，即：
int sum = 0, n = 100; /*执行1次*/
sum = (1+n) *n/2; /*执行第1次*/
sum = (1+n) *n/2; /*执行第2次*/
sum = (1+n) *n/2; /*执行第3次*/
sum = (1+n) *n/2; /*执行第4次*/
sum = (1+n) *n/2; /*执行第5次*/
sum = (1+n) *n/2; /*执行第6次*/
sum = (1+n) *n/2; /*执行第7次*/
sum = (1+n) *n/2; /*执行第8次*/
sum = (1+n) *n/2; /*执行第9次*/
sum = (1+n) *n/2; /*执行第10次*/
printf("%d ",sum); /*执行1次*/
事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。
注意：不管这个常数是多少，我们都记作 O（1），而不能是O（3），O（12）等其它任何数学，这就是初学者尝尝犯的错误。
对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着n的变大而发生变化，所以单纯的分支结构（不包含在循环结构中），其时间复杂度也是O(1)。
4.线性阶
线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。
下面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码须要执行n次。
int i;
for (i = 0; i < n; i++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
5.对数阶
来看一下下面这段代码的时间复杂度是多少？
int count = 1;
while (count < n)
{
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2x(次幂)=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。
6.平方阶
下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n2)(n的平方)。
如果外循环的循环次数改为了m，时间复杂度就变为O(m×n)。
int i, j;
for (i = 0; i < n; 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次。所以总的执行次数为：
n + (n - 1) + (n - 2) + … + 1 = n(n+1) / 2 = n^2 / 2 + n / 2
用推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n2/2；第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O(n2)。
接下来看一下对于方法调用的时间复杂度该怎样分析。
int i, j;
for (i = 0; i <n; i++)
{
function(i);
}
上面这段代码调用一个函数 function()。
void function(int count)
{
print(count);
}
函数体是打印这个参数。其实这很好理解，function函数的时间复杂度是O(1)。所以整体的时间复杂度为O(n)。
如果 function 是下面这样的：
void function(int count)
{
int j;
for (j = count; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
事实上，这和上面举的例子是一样的，只不过把嵌套内循环放到了函数中，所以最终的时间复杂度为O(n2)。
常见的时间复杂度
最后我们来看一下常见的时间复杂度有哪些吧：
执行次数 函数阶 非正式术语
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n2+2n+1 | O(n2) | 平方阶 |
| 5log2n+19 | O(logn) | 对数阶 |
| 2n+3nlog2 | O(nlogn) | nlogn阶 |
| 6n3+2n2+3n+4 | O(n3) | 立方阶 |
| 2n | O(2n) | 指数阶 |
常用的时间复杂度所耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(n^n)
最坏情况与平均情况
你早晨上班出门后突然想起来，手机忘记带了，这年头，钥匙、钱包、手机三大件，出门哪样也不能少呀。于是回家找。打开门一看，手机就在门口玄关的台子上，原来是出门穿鞋时忘记拿了。这当然是比较好，基本没花什么时间寻找。可如果不是放在那里，你就得进去到处找，找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间，就是找不到，时间一分一秒的过去，你突然想起来，可以用家里座机打一下手机，听着手机铃声来找呀，真是笨。终于找到了，在床上枕头下面。你再去上班，迟到。见鬼，这一年的全勤奖，就因为找手机给黄了。
找东西有运气好的时候，也有怎么也找不到的情况。但在现实中，通常我们碰到的绝大多数既不是最好的也不是最坏的，所以算下来是平均情况居多。
算法的分析也是类似，我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。
最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。
算法空间复杂度
我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。
总结与回顾
。。。。。。
- 点赞
- 收藏
- 关注作者
评论（0）