算法設(shè)計(jì)技巧與分析第1章算法基本概念之計(jì)算法-資料下載頁
2025-01-06 18:36本頁面
【正文】 INSERTIONSORT的平均情況。 ? 假定 1： A[]包含 1到 n的數(shù)字，這意味著 A中所有的元素都是不同的。 ? 假定 2： 數(shù)字 1， 2， 3， ， n的所有 n!個(gè)排列 以相等可能性出現(xiàn)。 ? 則 ： 要將元素 A[i]插入 A[1i]中合適的位置上，若這個(gè)位置是 j， 1≤j≤i，所執(zhí)行的比較次數(shù)為： Analysis ? j=1時(shí) ： ij； ? 2≤j≤i 時(shí) ： ij+1； 由于這個(gè)合適位置在 A[1 i]中的概率是 1/i ，則 將 A[i]插入到 A[1 i]中合適位置上所需要的平均 比較次數(shù)是： 1211 1 1 1 1 1 112 2 2iijji i j f i j i ii i i i i i???? ? ? ? ?? ? ? ? ? ? ? ? ???則 ：算法 INSERTIONSORT執(zhí)行的平均比較次數(shù)是 22 2 11 1 ( 1 ) 1 1 1 3 1()2 2 4 2 2 4 4n n ni i ii n n n n ni i i? ? ???? ? ? ? ? ? ? ? ?? ? ?由于 ： 11l n ( 1 ) l n 1ninn i?? ? ? ??因此 ： 執(zhí)行算法 INSERTIONSORT的平均比較次數(shù) 223 l n ( )44nn nn? ? ? ?Input Size and Instance ? 一個(gè)算法執(zhí)行性能的測度通常是它輸入的大小、順序和分布等的函數(shù)。 ? 輸入的大小作為一個(gè)數(shù)量，不是輸入的精確測度，它解釋為從屬于已設(shè)計(jì)或?qū)⒁O(shè)計(jì)的算法的問題。 Size Measurement 問題 輸入大小測度 排序 /搜索 數(shù)組或表中元素的數(shù)目 圖的算法 圖中邊 /頂點(diǎn)的數(shù)目 計(jì)算幾何 點(diǎn) /頂點(diǎn) /邊 /線段 /多邊形的個(gè)數(shù) 矩陣運(yùn)算 輸入矩陣的維數(shù) 數(shù)論算法 /密碼學(xué) 輸入的比特?cái)?shù) /字?jǐn)?shù) 輸入 : 一個(gè)正整數(shù) n 和一個(gè)數(shù)組 A [ i ], A [ j ] = j , 1 ≤ j ≤ n。 輸出 : ??nj jA1 ][ sum ← 0 for j ← 1 to n sum ← sum + A [ j ] end for return sum sum ← 0 for j ← 1 to n sum ← sum + j end for return sum 輸入 : 正整數(shù) n 。 輸出 : 。 ??nj i1Analysis ? 數(shù)論：是研究數(shù)的性質(zhì)的一門學(xué)科。 數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)中的皇冠。 ——高斯 算法 輸入 輸出 時(shí)間復(fù)雜度 FIRST n、 A[1n] SECOND k= ()n?(2 )k?1 []nj Aj??1nj j??? ?)1log(
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1