数据结构与算法学习笔记 4 （2018.10.08）

渐进分析：大o记号

• 回到原先的问题：随着问题规模的增长，计算成本如何增长？

        注意：这里更关心足够大的问题，注重考察成本的增长趋势

• 渐进分析：在问题的规模足够大后，计算成本如何成长？

            Asymptomatic analysis ：当n>>2后，对于规模为n输入，算法

                                                         需执行的基本操作次数：T（n）=？

                                                          需占用的存储单元数：S（n）=？ //通常可不考虑，为什么？

横轴（n）表示问题的规模，纵轴（f（n））表示相应的计算成本。

不需要关注局部的，暂时的一些趋势，而是看长远的，主要的变化趋势，个人理解为大的方向。

渐进分析：大o记号

渐进分析：其它记号

用的最多的是大 o 记号。

o（1）

• 常数（constant function）

                     2 = 2013 = 2013×2013 = o（1），甚至  = o（1） //含RAM各基本操作

• 这类算法的效率最高                                                                   //不能奢望不劳而获
• 什么样的代码段对应于常数执行时间？                                   //应具体分析

                     一定不含循环？不一定。

                             for (i=0; i<n; i+=n/2013 + 1);

                             for(i=1; i<n; i=i <<i);                                                                  //long‘n，几乎常数

                     一定不含分支转向？不一定。

                          if（（n+m)*(n+m)<4*n*m)  goto UNR EACHABLE;                 //不考虑溢出

                     一定不能有（递归）调用？不一定。

                         if (2== （n*n) % 5) o1(n);

o（log）

o（）

o（）

2-Subject