1、1、算法和算法分析1、算法：一個(gè)算法就是有窮規(guī)那么的集合，其中的規(guī)那么規(guī)定了一個(gè)處理某一個(gè)特定問題的運(yùn)算 序列。2、算法的時(shí)間復(fù)雜性和空間復(fù)雜性：問題的規(guī)模(n)：或大小。如：矩陣的階數(shù)、圖的結(jié)點(diǎn)個(gè)數(shù)、被分類序列的正整數(shù)個(gè)數(shù) 時(shí)間復(fù)雜性：算法的所需的時(shí)間和問題規(guī)模的函數(shù)。記為 T(n)。當(dāng) n- 時(shí)的時(shí)間復(fù)雜 性，被稱之為漸進(jìn)時(shí)間復(fù)雜性?？臻g復(fù)雜性：算法的所需的空間和問題規(guī)模的函數(shù)。記為 T(n)。當(dāng) n- 時(shí)的時(shí)間復(fù)雜 性，被稱之為漸進(jìn)空間復(fù)雜性。最壞情況下的時(shí)間復(fù)雜性和平均情況下的時(shí)間復(fù)雜性。 最壞情況下的時(shí)間復(fù)雜性： 平均情況下的時(shí)間復(fù)雜性： 3、大 O 表示法：定義；假設(shè)存在著正的常數(shù)

2、 c 和自然數(shù) n0，當(dāng) n = n0 時(shí)；有 f (n) = Cg(n) 成立，那么 稱 f( n ) = Og( n ) 。 在算法分析中， 假設(shè)一個(gè)的算法的時(shí)間復(fù)雜性是O(g( n )，讀作 g( n ) “ 級(jí) 的 或 “ 階 的。 如： 線性階的、平方階的、立方階的 1、算法和算法分析例1、 設(shè) T(n) = (n+1)2 = n2+2n2 +1 1 時(shí)， 式成立 選 n0 = 1, c=4 ; T(n) = 4n2。所以，T(n) = O(n2)例2、 設(shè) T(n) = 3n3+2n2 選 n0 = 0, c=5 ; T(n) = 5n3。所以，T(n) = O(n3) 同理：選

3、n0 = 0, c=5 ; T(n) = n0 ，3n+5 = 0，有 n = 3n+5 ，所以 g(n) =if Lim f(n)/g(n) = 0; 這里 c 是常數(shù)。 f(n) 級(jí)別低。n-if Lim f(n)/g(n) = ; 這里 c 是常數(shù)。 g(n) 級(jí)別低。n-如：Lim logn/n = Lim Ln(n)loge/n = Lim (loge/n)/1 = Lim loge/n = 0; logn 級(jí)別低。 留意：這里運(yùn)用了羅彼特的求極限的法那么。n-n-n-n-O(logn) 和 O (n1/2) ？ 1、算法和算法分析5、大 表示法：定義；假設(shè)存在著正的常數(shù) c 和自然

4、數(shù) n0，當(dāng) n = n0 時(shí)；有 f (n) = Cg(n) 成立，那么 稱 f( n ) = (g( n ) 。例1、 設(shè) T(n) = (n+1)2 = n2+2n2 +1 = n2 ; 在 n 為任何數(shù)時(shí)，所以，T(n) = (n2)例2、 設(shè) T(n) = 3n3+2n2 T(n) = 3n3。所以，T(n) = (n3) 同理：T(n) = 5n2。所以，T(n) = (n2) ？ 留意：符合定義，但在算法分析中是沒有意義的。 :找盡能夠高的下界。6、 表示法：定義；假設(shè)存在著正的常數(shù) c1、c2 和自然數(shù) n0，當(dāng) n = n0 時(shí)；有 C1 g(n) = f (n) = C2

5、g(n) 成立，那么稱 f( n ) = (g( n ) 。例1、 設(shè) T(n) = (n+1)2 = ( n2)1、算法和算法分析1。下述兩個(gè)程序段的作用都是將數(shù)組 int an 的前 n-1 數(shù)組元素置為和其 數(shù)組元素的下標(biāo)一樣的值，且最后一個(gè)數(shù)組元素置為 -1, 即 an-1= -1。 兩段程序那個(gè)好一些，那個(gè)差一些 ( 從算法的時(shí)間復(fù)雜性角度思索 )A. for ( i = 0 ; i n-1; + i ) ai= i; an-1= -1;B. for ( i = 0 ; i n; + i ) if ( i = = n-1 ) a n-1 = -1; else ai= i; 解：程序

6、A 執(zhí)行的語句次數(shù)為 n 次，而程序 B 執(zhí)行的語句次數(shù)為 2 n 次, 故而程序 B 更好一些。時(shí)間省。 2。以下是計(jì)算 n! 的遞歸程序，求其時(shí)間復(fù)雜性的級(jí)別： int f ( int n) int m; if ( n 1 ) y = y * x ; n = n-1 printf(“%d , y );.解： 調(diào)查各個(gè)語句的執(zhí)行次數(shù)，并把他們相加，可得到該程序的時(shí)間復(fù)雜性級(jí)別為：T(n)= 1+1+1+n+2n-2+1=O(n)111n2n-211、算法和算法分析111111Log n + 2Log n + 1Log n + 1Log n + 2Log n + 1Log n + 1Log n + 1代價(jià) = 55 的最小的2的正整數(shù)冪 64，64/2 可得到32，在程 序的 第二個(gè) while 中用到它。在程 序的 第二個(gè) while 中：55 - 32 = 23 得到 x110111 中的 冪指數(shù)中的最左位的123 - 16 = 7 得到 x110111 中的 冪指數(shù)中的左起