算法设计-第一章培训资料.ppt

算法渐近复杂性 T(n) ?? , as n?? ; (T(n) - t(n) )/ T(n) ?0 ，as n??; t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。 算法复杂性分析 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O、Ω、θ、o 设f(N)和g(N)是定义在正数集上的正函数。 O的定义：如果存在正的常数C和自然数N0，使得当N?N0时有f(N)?Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 根据O的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g))； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N))，则O(f)+O(g)=O(f)； (5)O(Cf(N))=O(f(N))，其中C是一个正的常数； (6)f=O(f)。 规则Ｏ(f(n))+Ｏ(g(n)) = Ｏ(max{f(n),g(n)}) 的证明： 对于任意f1(n) ∈ Ｏ(f(n)) ，存在正常数c1和自然数n1，使得对所有n ≥ n1，有f1(n) ≤ c1f(n) 。 类似地，对于任意g1(n) ∈ Ｏ(g(n))，存在正常数c2和自然数n2，使得对所有n ≥ n2，有g1(n) ≤ c2g(n) 。 令c3=max{c1, c2}，n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 则对所有的n ≥ n3，有 f1(n) +g1(n) ≤ c1f(n) + c2g(n) ≤ c3f(n) + c3g(n)= c3(f(n) + g(n)) ≤ c32 max{f(n),g(n)} ＝ 2c3h(n) ＝ Ｏ(max{f(n),g(n)}). 算法复杂性分析 Ω的定义：如果存在正的常数C和自然数N0，使得当N?N0时 有f(N)?Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ(g(N))当且仅当f(N)=O(g(N))且 f(N)= Ω(g(N))。此时称f(N)与g(N)同阶。 o的定义：对于任意给定的ε＞0，都存在正整数N0，使得 当N?N0时有f(N)/Cg(N)?ε,则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N))。 例如，4NlogN+7=o(3N2+4NlogN+7)。 渐近分析记号的若干性质 （1）传递性： f(n)=θ(g(n))，g(n)=θ(h(n)) → f(n)=θ(h(n))； f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n)) → f(n)=Ｏ(h(n))； f(n)=Ω(g(n))，g(n)=Ω(h(n)) → f(n)=Ω(h(n))； f(n)=ｏ(g(n))，g(n)=ｏ(h(n)) → f(n)=ｏ(h(n))； f(n)=ω(g(n))，g(n)=ω(h(n)) → f(n)=ω(h(n))； （2）反身性： f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)). （3）对称性： f(n)=θ(g(n)) == g(n)=θ(f(n)) . （4）互对称性： f(n)=Ｏ(g(n)) == g(n)=Ω(f(n)) ；f(n)=ｏ(g(n)) == g(n)=ω(f(n)) ； （5）算术运算： Ｏ(f(n))+Ｏ(g(n)) = Ｏ(max{f(n),g(n)}) ； Ｏ(f(n))+Ｏ(g(n)) = Ｏ(f(n)+g(n)) ；Ｏ(f(n))*Ｏ(g(n)) = Ｏ(f(n)*g(n)) ； Ｏ(cf(n)) = Ｏ(f(n)) ；g(n) = Ｏ(f(n)) → Ｏ(f(n))+Ｏ(g(n)) = Ｏ(f(n)) 。 渐近表示—Examples [例1]设f(n)=10n2+20n。则有 f(n)=O(n2) f(n)= Ω(n2) f(n)= θ(n2) [例2]设f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak0)。则有 f(n)=O(nk) f(n)= Ω (nk)： f(n)=θ (nk) 由此可见，复杂度的渐近表示可以简洁地表示出复杂 度的数量级别。 对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。 算法的平均复杂性 算法的最