算法设计与分析〉算法概述 1.2算法复杂性分析 1.复杂性的计量 算法的复杂性：算法执行所需的时间和空间的数量、 显然，它与问题的规模，算法的输入数据及算法本身有关。 令N:问题的规模：输入数据A:算法本身 则算法的复杂性C=F(N,I,A) 将时间复杂性和空间复杂性分别考虑，并用T和$表示.则 T=TN,I,A) S=S(N,I,A) 将A隐含在函数名中，则T=T(N,I,A)简化为T=TN,I) 设一台抽象计算机提供的元运算有k种，分别记作O1,,OB 设这些元运算每执行一次所需时间分别为t1,t2,,t, 设算法A中用到O,的次数为e,1,…,k,则e=e(N,I) T=TN,I)=2t,·e,N,) 13
13 算法设计与分析 > 算法概述 1.2 算法复杂性分析 1.复杂性的计量 = k 1 t e (N,I) i i i 显然,它与问题的规模,算法的输入数据及算法本身有关. 将时间复杂性和空间复杂性分别考虑,并用T和S表示.则 T=T(N,I,A) S=S(N,I,A) 将A隐含在函数名中,则 T=T(N,I,A) 简化为T=T(N,I) 算法的复杂性:算法执行所需的时间和空间的数量. 令 N:问题的规模 I:输入数据 A:算法本身 则算法的复杂性 C=F (N,I,A) 设一台抽象计算机提供的元运算有k种,分别记作O1 ,…,Ok 设这些元运算每执行一次所需时间分别为t1 , t2 ,…,tk , 设算法A中用到Oi的次数为 ei , i=1,…,k,则 ei= ei (N,I ) T=T(N,I)=
算法设计与分析〉算法概述>算法的复杂性 最好情况：Tmin(N)in T(N,I)=min te,(W,) IEDN I∈DNi 6e,N,7) T(W51) i=1 最坏情况：Tmax(N)=max T(N,Imax e(N,1) IEDN I∈DNi=1 =t..e.(N,J) T(N,I9 i=1 平均情况：Tavg(N)=∑P(I)·TN,) ∑P(庄t·e,(N,) I∈DN IEDn i=1 其中Dw:规模为N的所有合法输入的集合 I:Dv中达到Tmax(N)的一个输入 了：Dv中达到Tmn(N)的一个输入 P(I):出现输入为I的概率 14
最好情况: Tmin(N) = T(N,I) = = = 最坏情况: Tmax(N) = T(N,I) = = = 平均情况: Tavg(N) = = 14 算法设计与分析 > 算法概述 >算法的复杂性 = k i i i t e N I 1 ( , ) = k i i i t e N I 1 ( , ) = k i i i t e N I 1 ( ) ~ , T(N I ) ~ , IDN min = k i i i t e N I 1 ( , ) IDN max = k i i i t e N I 1 ( , * ) IDN P(I ) T(N, I) T(N , I * ) IDn P(I) IDN min IDN max I ~ 其中 DN:规模为N的所有合法输入的集合 I*: DN中达到Tmax (N)的一个输入 : DN中达到Tmin (N)的一个输入 P(I): 出现输入为I的概率
算法设计与分析 例题1-1已知不重复且从小到大排列的m个整数的数组A[1…m],m=2,K 为正整数.对于给定的整数c,要求找到一个下标i,使得A[]=c.找不到返回0. 算法1-1：顺序查找 function search(c) {i=1; a while A[i]<c and i<m do 2mt i=i+1; (m-1)(s+a) if A[i]=c t then search:=i; else search:=0; a 分析：问题的规模为m,设元运算执行时间为赋值：a,判断：t,加法：s,并设c在A中 最好情况Tmim(m)=a+2t+t+a=2a+3t 最坏情况Tmax(m)=(m+1)a+(2m+1)t+(m-1)s 平均情况Taug(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s
算法设计与分析 已知不重复且从小到大排列的m个整数的数组A[1...m],m=2 K,K 为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0. function search(c) { i:=1; a while A[i]<c and i<m do 2mt i:=i+1; (m-1) (s+a) if A[i]=c t then search:=i; else search:=0; a } 算法1-1:顺序查找 例 题 1-1 分析:问题的规模为m,设元运算执行时间为赋值:a,判断:t,加法:s, 并设c在A中. 最好情况Tmin (m)=a+2t+t+a=2a+3t 最坏情况Tmax(m) =(m+1)a+(2m+1)t+(m-1)s 平均情况Tavg(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s
算法设计与分析 例题1-2 算法1-2：二分查找（假定c是A的最后一元） function b-search(c) {L:=1;U:=m; 2a found:=false; a while not found and U>=L do 3t (logm+2) {i:=(L+U)div2; (a+s+d)(logm+1) if c=A[] 2t(1ogm+1) then found:=true a else if c>A[i] 2t(1ogm+1) then L:=i+1 (s+a)(logm+1) else U:=i-1 if found t then b-search:=i else b-search:=0 a 分析：问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b. 最坏情况Tmax(m)=7a+11t+2s+d+(2a+2s+7t+d)logm
算法设计与分析 例 题 1-2 算法1-2:二分查找 (假定c是A的最后一元) 分析:问题规模为m,元运算执行时间设为赋值a,判断t, 加法s, 除法d, 减法b. 最坏情况Tmax(m) = 7a+11t+2s+d+(2a+2s+7t+d) logm function b-search(c) { L:=1; U:=m; 2a found:=false; a while not found and U>=L do 3t (logm+2) { i:=(L+U)div2; (a+s+d)(logm+1) if c=A[i] 2t (logm+1) then found:=true a else if c>A[i] 2t (logm+1) then L:=i+1 (s+a)(logm+1) else U:=i-1 } if found t then b-search:=i else b-search:=0 a }
算法设计与分析〉算法概述>算法的复杂性 2复杂性的渐进性态 1).渐进性态 设T(n)为算法A的时间复杂性函数，则它是n的单增函数，如果存在 一个函数T(n)使得当n→oo,有 (T(d) )/T(n)→>0 称T(n)是T(n)当n→o时的渐进性态或渐进复杂性. ● 在数学上，T(n)与(n)有相同的最高阶项可取(n) 为略去T(n) 的低阶项后剩余的主项.当充分大时我们佣) 代替T(n)作为算 法复杂性的度量，从而简化分析： 例如T(n)=3n2+4 nlogn+-7,则n) 可以是3n2. 若进一步假定算法中所有不同元运算的单位执行时间相同，则可不考 虑T(n)所包含的系数或常数因子。 。渐进分析适用于充分大的情况，当问题的规模很小时，或比较的两算 法同阶时，则不能做这种简化 17
若进一步假定算法中所有不同元运算的单位执行时间相同,则可不考 虑 所包含的系数或常数因子。 例如 T(n)=3n2+4nlogn+7, 则 可以是3n2. 在数学上,T(n)与 有相同的最高阶项.可取 为略去T(n) 的低阶项后剩余的主项.当n充分大时我们用 代替T(n)作为算 法复杂性的度量,从而简化分析. 设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在 一个函数 使得当n→ ,有 (T(n) - ) / T(n)→0 称 是T(n)当 n→ 时的渐进性态 或 渐进复杂性. 17 算法设计与分析 > 算法概述 >算法的复杂性 2 复杂性的渐进性态 1).渐进性态 T(n) ~ T(n) ~ T(n) ~ T(n) ~ T(n) ~ T(n) ~ T(n) ~ T(n) ~ 渐进分析适用于n充分大的情况,当问题的规模很小时,或比较的两算 法同阶时,则不能做这种简化