经常可以在一些书上看到这样的公式:程序=数据结构+算法所以算法 的重要性是不言而喻的.
那么什么是算法呢？
算法的基本特性有:
1.确定性-----算法中的每一条指令无二义性.
2.有穷性-----算法经过有限的计算次数后结束.
3.可行性-----算法是由一些基本可行的运算实现.
4.算法有0个或者多个输入.
5.算法有1个或者多个输出.
那么我们又依据什么规则来设计一种特定的算法呢?
1.首先设计的算法要是正确的.根据严蔚敏数据结构一书中介绍了算法的这种正确性的四个层次.
层次一：程序不含语法错误.这是最基本的,也是在初学者最容易出现错误的地方
层次二：程序对于几组输入能够得到符合规格的结果.
层次三：程序对于精心挑选,条件苛责的输入仍然能得到符合规格的结果.这是大多数程序能够达到的层次.
层次四：程序对于任何输入都能得到符合规格的结果.这样的程序可以称得上完美,但是要实现这样的程序绝非易事.
在实际工作中,层次一往往是通过编译工具进行检查修正,否则存在语法错误的程序是无法运行的.而后几个层次
往往是使用专门的测试工具进行测试.
2.其次程序是可读的,算法不仅是面向机器,更重要的是面向读者.如果实现算法的程序是晦涩难懂的,那么这样的算法
肯定称不上好的算法.
3.还要程序是健壮的.所谓健壮是指实现算法的程序,不仅对于正确的输入能够给出正确的结果.对于不合要求的输入
仍然能够进行错误判别.识别出究竟是哪类错误.
4.最后就是算法时间效率和空间效率.所谓时间效率是指算法执行的时间.当然越快越好.空间效率是指算法执行所占
用的内存空间.当然是越小越好.
而对于算法最重要的就是效率了,那么效率如何度量呢
一种方式是将不同算法用程序实现,然后比较运行时间.这是一种最直观的比较算法效率的方法.很明显这种方式要求
我们将要比较的算法首先一一实现之后再来进行比较.不难看出这种比较方式是比较笨拙的.而且不同的硬件条件下
运行的时间也肯定是有差异的.
二种方式是不需要事先将算法实现来计算算法的时间效率：
这种方式需要考虑如下几个方面的因素:
1.问题的规模.比如计算100的阶乘肯定和计算1000的阶乘肯定运行时间不同.100和1000就是规模
2.书写算法的程序语言越高低,时间效率越低.反之,效率越高.
3.代码本身的质量,是否有冗余代码等等
4.计算机指令执行的快慢.
我们撇开语言,代码质量,硬件质量快慢这些认为可控因素不谈.
同一算法的时间效率主要取决于问题规模的大小.
对于同一问题的不同算法,在相同的问题规模下:
我们以100的累加为例.
计算100的阶乘,可以是1+2+3+4+5......100
也可以是(1+100)+(2+99)+(3+98)+......+(50+51)即简化为101*50;
很显然第二种计算方法要便于计算,时间效率高于第一种.
接下来我们将上例用代码进行描述：
第一种方式的累加1 int sum=0; ① 2 for(int i=1;i<=100;i++) ② 3 sum=sum+i; ③