時間復(fù)雜度的計算

1、如何計算算法時間復(fù)雜度1 計算算法時間復(fù)雜度過程：（1）確定基本操作（2）構(gòu)造基于基本操作的函數(shù)解析式（3）求解函數(shù)解析式2 如果構(gòu)建的是遞推關(guān)系式，那么常用的求解方法有：（1）前向替換法 可以從初始條件給出的序列初始項開始，使用遞推方程生成序列的前面若干項，寄希望于從中找出一個能夠用閉合公式表示的模式。如果找到了這樣的公式，我們可以用兩種方法對它進(jìn)行驗證：第一，將它直接代入遞歸方程和初始條件中。第二，用數(shù)學(xué)歸納法來證明。3例如，考慮如下遞推式： X(n) = 2X(n-1) +1 n1 X(1) = 1x(1)=1x(2)=2x(1)+1 = 2*1+1=3x(3)=2x(2)+1=2*3+

2、1=7x(4)=2x(3)+1=2*7+1=15X(n)=2n-1 n04（2）反向替換法例如：X(n)=x(n-1)+n 使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個結(jié)果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過程。X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/25（3）換名 上面形式的在遞推關(guān)系式，一個規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡化為n/k規(guī)模的問題，為了方便求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡化為： f(n)= f(km-1)+b = f(km-2)+2b = = f(k0)+m

3、b = f(1) + blog n 6第一種遞歸關(guān)系式：因為規(guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所以采用換名方法求解，設(shè) n = 2k：C(n) = C(2k)= C(2k-1)+1 = C(2k-2) + 2 = =C(2k-k)+k =C(1) + k = logn+17第二種遞歸調(diào)用，每次規(guī)模是原來的1/2：因為每一次規(guī)模都減到原來的1/2，所以用換名的方法設(shè) n = 2k：T(n) = T(n/2) + (n-1) = T(2k-1) + (2k-1) =T(2k-2) + (2k-1-1)+ (2k-1) = =T(2k-k) + (21-1) + +(2k-1-1) +(2k

4、-1) =T(1)+(2k+1-2)-k =2n-logn-18算法時間復(fù)雜度：O(n)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是 n。9第三種遞推關(guān)系式：10T(n)=2T(n/2) +n 設(shè)n= 2k =2T(2k-1)+2k =22T(2k-2)+2k-1+2k =22T(2k-2)+2*2k = =2k-1T(2k-(k-1) + (k-1)*2k =n/2 + (logn-1) *n11不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個子問題，設(shè)n =mk，則：12T(n)=mT(n/m) +n =mT(mk-1)+mk =mmT(mk-2)+

5、mk-1+mk =m2T(mk-2)+2*mk = =mkT(2k-k) + k*mk =n + logn *n13算法時間復(fù)雜度：O(nlogn)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是 nlogn。14減治法的基本思想 將規(guī)模為n的問題遞減為規(guī)模為n-1或n/2的子問題,反復(fù)遞減后對子問題分別求解,再建立子問題的解與原問題的解的關(guān)系。減治法有兩個變形: 減因子(如1/2):每次迭代規(guī)模減半n n/2 減可變規(guī)模:每次迭代減小的規(guī)模不同15遞歸復(fù)雜性的一般形式一般的，遞歸復(fù)雜性可描述為遞歸方程： 1 n = 1 af(n b) + D(n) n1f(n) =其中，a是子問題個數(shù)， 表示遞減方式， b是遞減步長， D(n)是合成子問題的開銷。通常，遞歸元的遞減方式有兩種：1、減法，即n b，的形式。2、除法，即n / b，的形式；分治法遞推法2022/8/1316分治