(算法12章整理版.pptVIP

* 控制结构：顺序、循环、条件分支，不同的组合可以产千变万化的程序框架来，while if和if while,模块对自身的调用（递归）等。 数据结构是算法操作的对象，通常是与算法紧密相关的，比如折半查找，用数组就比用指针方便 * 如果a/c与b/c不互质，则不是最大公约数，还有当前数的倍数可以当公约数 辗转相除法 * 正常的编码是什么 Ip电话即时压缩 生活中，也经常使用压缩数据:短信回答:1—换登机牌，2—不换登机牌 * 加密与解密：古典、对称/非对称：DES/RAS 其它方面：数据传输/软件加密 * 加密与解密：古典、对称/非对称：DES/RAS 其它方面：数据传输/软件加密 * 理解问题的本质及可能求解的技术，算法与问题的对应 * 算法在实现运行时占有的机器资源的多少即 算法的运行的时间和空间效率 算法在完成功能的前题下最好是占用空间少而且执行时间短。 另外在算法实现时,要考虑算法在运行过程中与使用者进行交互的情况。这就要求,算法的交互部分要具有友好性和健壮性。 * 可以引导用学生，不要光去考虑绝对时间，要学会转化，分秒不一定衡量时间长短的唯一计量单位 数据结构：存储学生档案信息，两种办法：数组和结构体 数学模型对算法的影响：求最大公约数 * 先实现，再判断 C=F(N,I,A) = C=F(N,I) Oi—为元运算，元运算的时间为ti，其运算次数为ei（N, I）, T(N, I)=ti*ei(N, I)，当NI时，T(N)代表其复杂度 N-足够大时，(T(N)-T1(N))/T(N)?0 T（N）=3N2+4NlogN+7 * 对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或主要) 的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。 * 原则上一个算法的时间复杂度, 最好不要采用指数级和阶乘级的算法, 而应尽可能选用多项式级或线性级等时间复杂度级别较小的算法。 对于较复杂的算法，可将它分隔成容易估算的几个部分，然后再利用O的求和原则得到整个算法的时间复杂度。 例：若算法的两个部分的时间复杂度分别为 T1(n)=O(f(n)) 和 T2(n)=O(g(n))， 则总的时间复杂度为： T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))。 * O表示上界 Ω下界 这五个定义帮我们进一步理解时间渐近复杂度的数学函义，是对进一步的扩充 * 引用自《数值分析与算法》徐士良 机械工业出版社 p27 * 以上三种情况下的时间复杂性, 各从某一个角度来反映算法的效率,各有各的用处,也各有各的局限性。但实践表明可操作性最好的,且最有实际价值的,是最坏情况下的时间复杂性。 一般来说, 最好情况和最坏情况的时间复杂性是很难计量的。有时也按平均情况计量时间复杂性，但要对输入不同数据的概率做人为的假设(一般是假设等概率)之后才能进行, 所做的假设缺乏必要的根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。 这里可以举：快速排序的内容 * 时间复杂性: P p1=f1(n)+f2(n)+…+fm(n) 如果一个判定性问题的复杂度是该问题的一个实例的规模n 的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题类。 可以在多项式时间内验证一个解是否正确的问题称为P问题,亦称为易验证问题类。 * * 定义1:如果存在两个正常数c和n0，对于所有的n=n0,有 |f(n)|≤c|g(n)|，则记作 : f(n)=Ο(g(n))。 定义2：如果存在两个正常数c和n0，对于所有的n=n0，有|f(n)|≥c|g(n)|,则记作 : f(n)=Ω(g(n))。 定义3：当 f(N)=Ο(g(N)) 且 f(N)=Ω(g(N))时，则记 f(N)=θ(g(N))。也就是说f(N)与g(N)同阶。 定义4：如果对于任意给定的S≥0，都存在非负整数N0，使得当N≥N0时有f(N)≤Sg(N)，则称函数f(N)当N充分大时，比g(N)低阶，记为f(N)=o(g(N))。 定义5:若g(N)=o(f(N)), 即当N充分大时, f(N)的阶比g(N)高，则记f(N)=ω(g(N))。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2