算法的概念:
所有交给计算机的任务和计划,在完成之前的一系列的计算和流程都属于算法。
算法的特性:
1、有穷性:执行有限个操作后终止;
2、稳定性:算法中每一步的含义必须是明确的,不存在二义性;
3、有效性:算法中每一步操作必须能有效执行,不能执行的操作是无效的;
4、有零个或者是多个输入:执行算法时,从外界获的必要的信息;
5、有一个或者是多个输出:算法的姐(结果)就是输出。
如何评价算法好坏:
1、时间复杂度:
重复操作的步骤数,用函数来表示显示为T(n)=O(f(n))。需要说明的是,时间复杂度计算的不是执行的总用时,而是算法执行的次数。
计算方法
①选取相对增长最高的项
②最高项系数是都化为1
③若是常数的话用O(1)表示
如f(n)=2*n^3+2n+100则O(n)=n^3。
如 for( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) ){
...
}
} 此时的复杂度 T(n) = O ( n * m);
2、空间复杂度:
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,函数关系式表示为:S(n)=O(f(n);
参照时间复杂度,这个空间复杂度其实大致差不多,它介绍的其实还是一个空间的占用趋势,不是实际占用的空间数。
3、检查算法的五个要素:
①正确性、合法的输入数据都能得到满足要求的答案。
②可读性:算法应该易于阅读和理解。
③健壮性:当输入数据非法时,能作出反应进行相应的处理。
高效和低存储空间:对于同等规模的问题,执行的时间少,占用空间少。
网友评论