算法的描述:
1:自然语言:英语,中文
2:流程图:传统流,NS流程图
3:伪代码:类语言,类c语言
4:程序代码:c语言程序,java语言程序
算法:
是解觉问题的一种方法或一个过程,考虑如何将输入转换成输出,一个问题可以有多种算法
程序:
是用某种程序设计语言对算法的具体实现。
程序=数据结构+算法
算法的定义:
1:有穷性
2:确定性
3:可行性
4:输入,输出。
算法设计的要求:
1:正确性
2:可读性
3:健壮性
4:高效性。
若是以上都要求:则主要考虑算法的效率:
时间效率:算法所耗费的时间
空间效率:算法所耗费的存储空间
算法的时间效率度量:两种
事后统计:将算法实现测算其时间和空间开销
事前分析:对算法所耗资源的一种估算方法
一个算法运算时间:
每条语句频率(每条语句执行的次数)* 该语句执行一次所要的时间
算法的执行时间大致上等于其所有语句执行时间的总和。
算法的时间复杂度定义:
一般情况下,算法中基本语句重复执行的次数是问题规模n的每个函数f(n),算法的时间量度记作:T(n)=O(f(n))
算法的时间复杂度分析:
1:找出所有语句中语句频率最大的那条语句作为最基本语句,
2:计算基本语句的品读得到问题规模你的每个函数f(n)
3:取其数量级用符号“O”表示即可。
若是f(n)是一个m次多项式,则T(n)=O(n的m次方)。
平方实例:
(1) x=0;y=0;
(2) for (k=1;k<=n;k++) //执行n次
(3) x++; //执行n次
(4) for(i=1;i<=n;i++) //执行n次
(5) for(j=1;j<=n;j++) //执行n次
(6) y++; //执行n*n次
所以综上所述频率最大的语句是(6),其频道为f(n)=n*n,所以该算法的时间复杂度为:T(n)=O(n*n),称为平方阶。
算法空间复杂度:
关于算法的存储空间要求
S(n)=O(f(n)),其中n为问题的规模(或大小)
例题(二):
i=1;
while(i<=n)
i=i*2;
以上若是执行一次为2,两次为2的平方,三次为2的3次方,若是循环x次则为:i=2的x次方
因为:i<=n , 所以:2的x次方<=n , 所以 x<=log以2为底n的对数。
即f(n)<=log以2为底n的对数。最大值:f(n)=log以2为底n的对数。
T(n)=O(log以2为底n的对数)