算法分析基本概念.ppt

* 例：f(n)=3n+2，求g(n)，使得f(n) =Θ(g(n))。 解： 当n≥2，f(n)=3n+2≤3n+n=4n 当n≥1，f(n)=3n+2≥3n 故当n≥2，有3n≤f(n)≤4n 令g(n)=n，因为当n≥2时有3g(n)≤f(n)≤4g(n) 所以 f(n)= Θ(n) 解2：令g(n)=n * Θ符号提供了算法运行时间的精确描述，由于算法InsertionSort的运行时间由线性到平方排列，因此不能用Θ描述。而SelectionSort算法和BottomUpSort算法可分别使用Θ(n2)和Θ(nlog2n)精确描述。 f(n)=Θ(g(n))是一个等价关系，由这个关系导出一个等价类，称为复杂性类。 例：f(n)=3n+2、g(n)=n，显然有f(n)=Θ(g(n))。 表示这二个函数属同一复杂性类。 ㈤ o符号（读作小o） 由等价关系f(n)=Θ(g(n)) 导出了一个等价类，为了说明二个函数属于不同类，引入了o符号。f(n)=o(g(n))，当且仅当f(n)=O(g(n))，但g(n)≠O(f(n))。 * 定义1.3（Page 19） 令f(n)和g(n)是从自然数集到非负实数集的二个函数。如果对于每一个常数c0，存在一个自然数n0，使得 n≥n0 ，f(n)cg(n) 则称f(n) = o(g(n)) 。 形式地说明了当n→∞时，f(n)对于g(n)来说可以忽略不计。f(n)=o(g(n))，当且仅当f(n)=O(g(n)，但g(n) ≠O(f(n))。 例如：“n是o(n2)的”等价于“n是O(n2)，但n2≠O(n)”。 * * 我们用f(n)﹤g(n)来表示f(n)是o(g(n))的。用该记号可简明地表示复杂性的层次 。 1﹤log n﹤n1/2﹤n﹤n log n﹤n2﹤n3﹤2n﹤n! Ｏ 类似于 ≤ Ω 类似于 ≥ Θ 类似于 ＝ o 类似于 ＜ 不要将确切的关系和渐近符号相混淆。例如： 100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n) 一般地，设f(n)=aknk+ak-1nk-1+…+a1n+a0，则f(n)=Θ(nk)，它蕴含着f(n)=O(nk)，f(n)=Ω(nk) 。 * 例1.5（Page17) f(n)=10n2+20n，求g(n)，使得f(n) =Θ(g(n))。 解： 当n≥1，f(n)= 10n2+20n ≤30n2 ，f(n)=Ｏ(n2) 当n≥1，f(n)=10n2+20n ≥n2 ，f(n)= Ω(n2) 故当n≥1，有n2 ≤f(n)≤ 30n2 令g(n)=n2，因为当n≥1时有g(n)≤f(n)≤30g(n) 所以 f(n)= Θ(n2) 解2：令g(n)=n2 * 例1.6（Page 17） 令f(n) =aknk+aknk+…+akn+a0 ， 则f(n) =Θ(nk)= f(n)=Ｏ(nk), f(n)= Ω(nk) 例1.7（Page 17） 例1.9（Page 17） 任一常函数是Θ (1),Ｏ(1),Ω (1) * 证明当n≥？时有2n＜n! 证： 由此可得：2n=o(n!) * 例1.12 （Page 17） * 例1.14 （Page 18） 同理： * * 1.9 空间复杂性 空间复杂性定义（P19） 为了求解问题的实例，执行计算步骤所需要的内存空间的数目，它不包括分配用来存储输入的空间。换句话说，仅仅是算法需要的工作空间。 空间复杂性的计算要比时间复杂性简单得多，可将时间复杂性的定义和符号移植到空间复杂性的表示。 例1：在算法LinearSearch中，仅需要一个内存单元保存搜索结果。如果加上局部变量，可以得出需要的空间数量为Θ(1)。同理算法BinarySearch、SelectionSort和InsertionSort。 * 例2： 在算法Merge中，需要和输入大小相同的存储器n个，因此空间复杂性为Θ(n)。同理算法BottomUpSort。 许多问题的处理需要在时间和空间之间平衡。一般来说，给算法分配的空间越大，算法运行速度就越快，反之亦然。 迄今为止所讨论的大多数算法中，增加空间并不可能导致算法速度的加快，有可能反而降低。但是，减小空间会导致算法速度的降低是毫无疑问的。 * 1.11 如何估计算法运行时间 通过计算迭代