可以做宣传的网站,wordpress 免费主机,网页编辑面试知识,html常用标签文章目录
绪论#xff1a;
2.算法和算法评价
知识总览
2.1算法的基本概念
知识点回顾与重要考点
2.2算法效率的度量
知识总览
1.时间复杂度
2.空间复杂度
知识点回顾与重要考点
归纳总结 绪论#xff1a;
2.算法和算法评价
知识总览 2.1算法的基本概念 算法( Al…文章目录
绪论
2.算法和算法评价
知识总览
2.1算法的基本概念
知识点回顾与重要考点
2.2算法效率的度量
知识总览
1.时间复杂度
2.空间复杂度
知识点回顾与重要考点
归纳总结 绪论
2.算法和算法评价
知识总览 2.1算法的基本概念 算法( Algorithm是对特定问题求解步骤的一种描述它是指令的有限序列其中的每条指令表示一个或多个操作。此外一个算法还具有下列五个重要特性:
1) 有穷性。一个算法必须总在执行有穷步之后结束且每一步都可在有穷时间内完成。 2确定性。算法中每条指令必须有确切的含义对于相同的输入只能得出相同的输出。
3可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4输入。一个算法有零个或多个输入这些输入取自于某个特定的对象的集合。
5输出。一个算法有一个或多个输出这些输出是与输入有着某种特定关系的量。通常设计一个“好”的算法应考虑达到以下目标: 1) 正确性。算法应能够正确地解决求解问题。 2可读性。算法应具有良好的可读性以帮助人们理解。 3健壮性。算法能对输入的非法数据做出反应或处理而不会产生莫名其妙的输出。 4高效率与低存储量需求。效率是指算法执行的时间存储量需求是指算法执行过程中所 需要的最大存储空间这两者都与问题的规模有关。 知识点回顾与重要考点 2.2算法效率的度量
知识总览 1.时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)它是该算法问题规模n的函数时间复杂度主要分析T(n)的数量级。
算法中基本运算最深层循环中的语句的频度与T(n)同数量级因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是算法的时间复杂度记为T(n)O(fn)
式中O的含义是T(n)的数量级其严格的数学定义是:若T(n)和 fn)是定义在正整数集合上的两个函数则存在正常数C和n使得当n≥n时都满足0≤T(n)≤Cf(n)。
算法的时间复杂度不仅依赖于问题的规模n也取决于待输入数据的性质如输入数据元素的初始状态)。例如在数组A [ 0...n- 1]中查找给定值k的算法大致如下:
in-l;
while (i0(A[i]!k))
i--;
return i;
该算法中语句3(基本运算的频度不仅与问题规模n有关而且与下列因素有关:
若A中没有与k相等的元素则语句3的频度f(n)n。 ②若A的最后一个元素等于k则语句3的频度f(n)是常数0。最坏时间复杂度是指在最坏情况下算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下算法的期望运行时间。
最好时间复杂度是指在最好情况下算法的时间复杂度。
一般总是考虑在最坏情况下的时间复杂度以保证算法的运行时间不会比它更长。在分析一个程序的时间复杂性时有以下两条规则:
1加法规则:T(n)T(n)T,(n)O(f(n))O(gn))O(max(f(n), g(n))
2乘法规则: T(n)T(n)xT;(n)O(f(n))×O(g(n))o(f (n)×g(n)) 2.空间复杂度
算法的空间复杂度S(n)定义为该算法所需的存储空间它是问题规模n的函数记为
S(n)O(g(n))
一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身和算法无关则只需分析除输入和程序之外的额外空间。例如若算法中新建了几个与输入数据规模n相同的辅助数组则空间复杂度为O(n)。
算法原地工作是指算法所需的辅助空间为常量即O(1)。 知识点回顾与重要考点 归纳总结
本章的重点是分析程序的时间复杂度。一定要掌握分析时间复杂度的方法和步骤很多读者 在做题时一眼就能看出在厅出的两种形式供大家参考。人众多资料总结出了此类题型的两种形式供大家参考。
1循环主体中的变量参与循环条件的判断 在用于递推实现的算法中首先找出基本运算的执行次数x与问题规模n之间的关系式,解得xf(n)f(n)的最高次幂为k则算法的时间复杂度为。例如
1.
int i1;
while(in)
ii*2;
2.
int y5;
while((y1)*(y1)n)
yy1; 在例1中设基本运算ii*2的执行次数为t则解得故
在例2中设基本运算yy1的执行次数为t则ty-5且(t51)(t51)n解得t√n-6即 T(n) O( √n )。
2循环主体中的变量与循环条件无关 此类题可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析忽略单步语句、条件判断语句只关注主体语句的执行次数。
此类问题又可分为递归程序和非递归程序:
·递归程序一般使用公式进行递推。时间复杂度的分析如下: T(n)1T(n-1)11T(n-2)…n-1 T(1) 即T(n)O(n)
·非递归程序的分析比较简单可以直接累计次数。
