算法時間復雜度的計算.doc

精品文檔算法時間復雜度的計算 整理 基本的計算步驟 時間復雜度的定義 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)，稱O(f(n)為算法的漸進時間復雜度(O是數(shù)量級的符號 )，簡稱時間復雜度。根據(jù)定義，可以歸納出基本的計算步驟 1. 計算出基本操作的執(zhí)行次數(shù)T(n) 基本操作即算法中的每條語句（以;號作為分割），語句的執(zhí)行次數(shù)也叫做語句的頻度。在做算法分析時，一般默認為考慮最壞的情況。2. 計算出T(n)的數(shù)量級 求T(n)的數(shù)量級，只要將T(n)進行如下一些操作： 忽略常量、低次冪和最高次冪的系數(shù) 令f(n)=T(n)的數(shù)量級。3. 用大O來表示時間復雜度 當n趨近于無窮大時，如果lim(T(n)/f(n)的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)。一個示例： (1) int num1, num2;(2) for(int i=0; in; i+) (3) num1 += 1;(4) for(int j=1; j=n; j*=2) (5) num2 += num1;(6) (7) 分析：1.語句int num1, num2;的頻度為1；語句i=0;的頻度為1；語句in; i+; num1+=1; j=1; 的頻度為n；語句j=n; j*=2; num2+=num1;的頻度為n*log2n；T(n) = 2 + 4n + 3n*log2n2.忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)f(n) = n*log2n3.lim(T(n)/f(n) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3當n趨向于無窮大，1/n趨向于0，1/log2n趨向于0所以極限等于3。T(n) = O(n*log2n)簡化的計算步驟 再來分析一下，可以看出，決定算法復雜度的是執(zhí)行次數(shù)最多的語句，這里是num2 += num1，一般也是最內循環(huán)的語句。并且，通常將求解極限是否為常量也省略掉？于是，以上步驟可以簡化為： 1. 找到執(zhí)行次數(shù)最多的語句 2. 計算語句執(zhí)行次數(shù)的數(shù)量級3. 用大O來表示結果 繼續(xù)以上述算法為例，進行分析：1.執(zhí)行次數(shù)最多的語句為num2 += num12.T(n) = n*log2nf(n) = n*log2n3./ lim(T(n)/f(n) = 1T(n) = O(n*log2n)-一些補充說明 最壞時間復雜度 算法的時間復雜度不僅與語句頻度有關，還與問題規(guī)模及輸入實例中各元素的取值有關。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。這就保證了算法的運行時間不會比任何更長。求數(shù)量級 即求對數(shù)值(log)，默認底數(shù)為10，簡單來說就是“一個數(shù)用標準科學計數(shù)法表示后，10的指數(shù)”。例如，5000=5x10 3 (log5000=3) ，數(shù)量級為3。另外，一個未知數(shù)的數(shù)量級為其最接近的數(shù)量級，即最大可能的數(shù)量級。求極限的技巧 要利用好1/n。當n趨于無窮大時，1/n趨向于0 -一些規(guī)則(引自：時間復雜度計算 ) 1) 加法規(guī)則 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )2) 乘法規(guī)則 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m)3) 一個特例（問題規(guī)模為常量的時間復雜度） 在大O表示法里面有一個特例，如果T1(n) O(c)， c是一個與n無關的任意常數(shù)，T2(n) = O ( f(n) ) 則有T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )也就是說，在大O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級，記為O(1)。4) 一個經(jīng)驗規(guī)則 復雜度與時間效率的關系：c log2n n n*log2n n2 n3 2n 3n n! （c是一個常量）|-|-|-| 較好 一般 較差其中c是一個常量，如果一個算法的復雜度為c 、 log2n 、n 、 n*log2n,那么這個算法時間效率比較高 ，如果是 2n , 3n ,n!,那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強人意。 -復雜情況的分析 以上都是對于單個嵌套循環(huán)的情況進行分析，但實際上還可能有其他的情況，下面將例舉說明。1.并列循環(huán)的復雜度分析 將各個嵌套循環(huán)的時間復雜度相加。例如：for (i=1; i=n; i+) x+;for (i=1; i=n; i+) for (j=1; j=n; j+) x+;解：第一個for循環(huán)T(n) = nf(n) = n時間復雜度為(n)第二個for循環(huán)T(n) = n2f(n) = n2時間復雜度為(n2)整個算法的時間復雜度為(n+n2) = (n2)。2.函數(shù)調用的復雜度分析 例如：public void printsum(int count) int sum = 1; for(int i= 0; in; i+) sum += i; System.out.print(sum);分析：記住，只有可運行的語句才會增加時間復雜度，因此，上面方法里的內容除了循環(huán)之外，其余的可運行語句的復雜度都是O(1)。所以printsum的時間復雜度 = for的O(n)+O(1) = 忽略常量 = O(n)*這里其實可以運用公式 num = n*(n+1)/2，對算法進行優(yōu)化，改為：public void printsum(int count) int sum = 1; sum = count * (count+1)/2; System.out.print(sum);這樣算法的時間復雜度將由原來的O(n)降為O(1)，大大地提高了算法的性能。 3.混合情況（多個方法調用與循環(huán)）的復雜度分析 例如：public void suixiangMethod(int n) printsum(n);/1.1 for(int i= 0; in; i+) printsum(n); /1.2 for(int i= 0; i 忽略常數(shù) 和 非主要項 = O(n2)-更多的例子 O(1) 交換i和j的內容temp=i;i=j;j=temp; 以上三條單個語句的頻度為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關的常數(shù)。算法的時間復雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復雜度是O(1)。O(n2) sum=0； /* 執(zhí)行次數(shù)1 */ for(i=1;i=n;i+) for(j=1;j=n;j+) sum+； /* 執(zhí)行次數(shù)n2 */解：T(n) = 1 + n2 = O(n2) for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; 解： 語句1的頻度是n-1 語句2的頻度是(n-1)*(2n+1) = 2n2-n-1 T(n) = 2n2-n-1+(n-1) = 2n2-2 f(n) = n2 lim(T(n)/f(n) = 2 + 2*(1/n2) = 2 T(n) = O(n2).O(n) a=0; b=1; for (i=1;i=n;i+) s=a+b; b=a; a=s; 解： 語句1的頻度：2, 語句2的頻度：n, 語句3的頻度：n, 語句4的頻度：n, 語句5的頻度：n, T(n) = 2+4n f(n) = n lim(T(n)/f(n) = 2*(1/n) + 4 = 4 T(n) = O(n). O(log2n) i=1; while (i=n) i=i*2; 解： 語句1的頻度是1, 設語句2的頻度是t, 則：nt=n; t=log2n 考慮最壞情況，取最大值t=log2n, T(n) = 1 + log2n f(n) = log2n lim(T(n)/f(n) = 1/log2n + 1 = 1 T(n) = O(log2n)O(n3) for(i=0;in;i+) for(j=0;ji;j+) for(k=0;kj;k+) x=x+2; 解：當i=m, j=k的時候,內層循環(huán)的次數(shù)為k當i=m時, j 可以取 0,1,.,m-1 , 所以這里最內循環(huán)共進行了0