什么是算法?
算法其实就是对一个问题或一类问题的解决过程的描述。大家对高斯不陌生吧?以首项加末项乘以项数除以2用来计算“1 + 2 + 3 + 4 + 5 +···+ (n - 1) + n”的结果。我们把它叫做高斯算法,因为可以通过公式来解决复杂的问题,大大缩短了解题时间。当然算法的魅力还不止如此,我们接着往下看:
这两段代码都可以称之为算法,因为分别可以解决两个数相加和加从1到n的问题。算法并不一定要非常复杂,小到一行代码,多到上万行代码,只要能解决特定问题,就是算法。
如何评估算法优劣
<强>使用不同算法,解决同一个问题,效率可能相差非常大
现有两个求斐波那契数(斐波纳契数)的算法
(斐波那契数列:1 1 2 3 5 8……)
这里
<代码类="语言java ">公共静态int fib1 (int n) {
如果返回n (n & lt;=1);
返回fib1 (n - 1) + fib1 (n - 2);
}
<代码类="语言java ">公共静态int fib2 (int n) {
如果返回n (n & lt;=1);
int第一=0;
int第二=1;
for (int i=0;我& lt;n - 1;我+ +){
int和=第一+第二;
第一次=第二;
第二个=总和;
}
返回第二;
}
这两个算法哪个更优呢?
如果单从执行效率上进行评估,可能会想到这么一种方案
比较不同算法对同一组输入的执行处理时间
这种方案也叫做:事后统计法
我们的做法是:
<代码类="语言java ">公共静态void main (String [] args) {
int n=45;//求第45个斐波那契数
TimeTool。检查(“fib1”,新任务(){
公共空间execute () {
System.out.println (fib1 (n));
}
});//5.815秒
TimeTool。检查(“fib2”,新任务(){
公共空间execute () {
System.out.println (fib2 (n));
}
});//0.0秒
}
上述方案有比较明显的缺点
执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性(n=100时可能第一种算法时间更短,n=200时可能第二种算法时间更短)
<强>一般从以下维度来评估算法的优劣
正确性,可读性,健壮性(对不合理输入的反应能力和处理能力)
时间复杂度(时间复杂度):估算程序指令的执行次数(执行时间)
空间复杂度(空间复杂性):估算所需占用的存储空间
我们用这种方案评估一下计算1 + 2 +…+ n的算法
显然第二种算法更好。难道是因为第二种方法代码更短吗?斐波那契数列的例子已经告诉我们并不是代码越短越好。这个例子中第二个算法只需要三步运算就可以解决问题,而第一种需要循环n次。首先都满足正确性,可读性,健壮性的条件,然后从时间复杂度来讲,假定一步运算的执行时间的一定的,我们考察一下大致需要执行多少次指令,就可以比较出两种算法的时间长短;再从空间复杂度考虑,需要的变量越少,开辟的存储空间越小,算法更好。
大O表示法
一般用大O表示法来描述复杂度,它表示的是数据规模n对应的复杂度
<强>方法步骤:
(1)估算时间复杂度/空间复杂度(主要是时间复杂度)
(2.1)忽略常数,系数,低阶
?9美元的在比;O (1)
?,2 n + 6美元祝辞的在O (n)
?n ^ 2 + 2 + 6美元的在比;O (n ^ 2美元)
?4美元n ^ 3 + 3 ^ 2 + 22 n + 100美元在祝辞O (n ^ 3美元)
(2.2)对数阶一般省略底数
?美元log_2n=log_29 + log_9n $(任意底数的对数可通过乘以一个常数相互转化)
?所以log_2n,美元log_9n统美元称为logn
美元注意:大O表示法仅仅是一种粗略的分析模型,是一种估算,能帮助我们短时间内了解一个算法的执行效率
计算下面几段代码的时间复杂度
<代码类="语言java ">公共静态孔隙test1 (int n) {//1(进行一次判断操作)
如果(n比;10){
system . out。println (“n比;10”);
}else if (n比;5){//2
system . out。println (“n比;5”);
其他}{
system . out。println (“& lt; n=5”);
}//1(定义一次我)+ 4(我累加四次)+ 4(判断i化繁为简——算法之魅力
