Niklaus Wirth:
Algorithm + Data Structures = Programs
这句话呢,觉得很正确,算法和程序是不同的概念,算法的思想呢有递推,枚举,分治,贪婪,试探法,模拟,这些都是一些基础的算法思想,一个“好”的算法,通常要考虑如下几个目标:
正确性:算法应满足求解具体问题的需求。
对正确性的理解有不同程度
1.不含语法错误;
2.对几组输入数据能够得到满足规格需求的解;
3.对精心选择的典型数据能够得到满足规格需求的解;
4.对一切合法的输入数据都能得到满足规格需求的解。
可读性:算法要便于交流,要有助于别人对算法的理解。
健壮性:对于非法的输入,算法要能给出适当的反映,而不会出现莫名其妙的错误。
好的时空性:算法的效率要高,同时所占的存储量要低。
算法分析有两个阶段,事前分析和事后测试。
例 考虑下面三个程序段
x+=y;
程序段a
For (i=1;i<=n;++i)
x+=y;
程序段b
For (i=1; i<=n;++i)
For (j=1; j<= n;++j)
x+=y;
程序段c
对于每个程序段,假定语句x+=y仅包含在当前可以看得见的循环之中,那末,在程序段a中,此语句的频率计数为 1 ,在程序段b中为 n ,在程序段c中为 n2 。确定一个算法的数量级是十分重要的,它在本质上反映了一个算法所需要的计算时间。如下图:
开始学算法了,觉得有好的算法的思想,程序才能有条理,并且节约机器与程序的时间,才能高效,这也是算法最终的目的。