算法设计和复杂度分析.pptVIP

算法设计与复杂度分析  算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性,需要的空间资源的 量称为空间复杂性。这个量应该只依赖于算法要解的 题的规模、算法的输入和算法本身的函数。如果分别用 N、I和A表示算法要解问题的规模、算法的输入和算法 本身,而且用C表示复杂性,那么,应该有 C=F(N,I,A)。 般把时间复杂性和空间复杂性分开,并分别用T和S来 表示,则有: T-T(N,D和S=S(N,D (通常,让A隐含在复杂性函数名当中  算法复杂性分析 最坏情况下的时间复杂性: Tmax(N)=max T(N, 1)=maxt e, (N,D) lEDN j x1(M,1)=T(N 最好情况下的时间复杂性: 7N=m=mn∑(MD=∑(N)=T(N) 平均情况下的时间复杂性: T(N=∑P(D)(N,D=∑P()∑1e 其中D是规模为N的合法输入的集合;I·是D中使T(N,I 达到TmxN的合法输入;了是中使T(N,7)达到Tnn(的合法 输入;而P(I是在算法的应用中出现输入I的概率  算法复杂性分析 算法复杂性在渐近意义下的阶 渐近意义下的记号:0、Ω、θ、o 设f(N和g(N是定义在正数集上的正函数 0的定义:如果存在正的常数C和自然数N,使得当N≥N0时 有f(N≤Cg(N,则称函数fQN当N充分大时上有界,且g(N是它 的一个上界,记为f(N=0(g(N)。即f(N的阶不高于g(N的阶 根据0的定义,容易证明它有如下运算规则 (1)0(f)+0(g)=0(max(f,g)); (2)0(f)+0(g)=0(f+g) (3)0(f)0(g)=0(fg) (4)如果g(N)=0(f(N),则0(f)+0(g)=0(f); (5)o(CfQN)=0(f(N),其中C是一个正的常数; (6)f=0(f)  算法复杂性分析 Ω的定义:如果存在正的常数C和自然数N0,使得当N≥N0时 有f(N≥Cg(N,则称函数f(N当N充分大时下有界,且g(N是它 的一个下界,记为f(N=Ω(g(N)。即f(N的阶不低于gQN的阶 θ的定义:定义f(N=日(g(N)当且仅当f(N=0(g(N)且 f(N=Ω(g(N)。此时称f(N与g(N同阶 o的定义:对于任意给定的E0,都存在正整数N0,使得 当N≥N0时有f0N/Cg(N≤E,则称函数f(N当N充分大时的阶比 g(N低,记为f(N=o(g(N)。