算法設(shè)計技巧與分析第1章算法基本概念之計算法-展示頁
2025-01-15 18:36本頁面
【正文】 ：計算類循環(huán)的迭代次數(shù)； 2）操作計數(shù)：找出一個或多個 關(guān)鍵 操作，確定這些關(guān)鍵操作所需要的執(zhí)行時間； ? 實驗方法 ： ? 利用編譯器提供的時間函數(shù)來計算。 Iterative Count ? 算法運行時間常常和 While循環(huán)及類似結(jié)構(gòu)的執(zhí)行次數(shù)成正比。 輸入 : n = , k 為正整數(shù)。 k２ count ← 0 while n ≥ 1 for j ← 1 to n count ← count + 1 end for n ← n /2 end while return count Analysis ? 包含 ： 兩個嵌套循環(huán)和一個變量 count； ? 對 為正整數(shù) ： while循環(huán)執(zhí)行 K+1次， for循環(huán)執(zhí)行 n次，之后是 n/ n/4， ‥ 2,knk?0011 ( 2 ) 2 1 ( )2 2 2kkj j kjjn n n n n??? ? ? ? ? ? ???? 考察對象 1：算法中第 4步的執(zhí)行次數(shù)； ? 第 4步的執(zhí)行次數(shù)是： 輸入 : 正整數(shù) n 。 n ← 0 for i ← 1 to n for j ← 1 to m count ← count + 1 end for end for return count m ← ? ?in／Analysis ? 包含 ： 兩個嵌套循環(huán)和一個變量 count； ? n 取下列不同值時，內(nèi)循環(huán)反復(fù)執(zhí)行 ： , / 2 , / 3 , , /n n n n n? ? ? ? ? ?? ? ? ? ? ?? 考察對象 1：算法中第 5步的執(zhí)行次數(shù)； 1 1 1( 1 )n n ni i in n ni i i? ? ???? ? ?????? ? ?? 由于 ： ? 結(jié)論 ： 第 5步執(zhí)行 次。 輸出 : 第 6步的執(zhí)行次數(shù) count 。 22k? 考察對象 1：算法中第 6步的執(zhí)行次數(shù)； ? 對每個 for循環(huán)： while的執(zhí)行次數(shù)是 k+1=log log n+1 2 4 22 , 2 , 2 , , 2 kj ?? 對于 i所取的每一個值 ：當(dāng) 時，執(zhí)行 while循環(huán)。 輸出 : 對于１和 n 之間的每個完全平方數(shù) j ,輸出 。 ()n?? 假定 ： 可以在 O(1)時間計算出來； n? 內(nèi)部 for循環(huán)的執(zhí)行次數(shù)： 22 3 1 . 51 1 1( 1 ) ( 2 1 )1 ( ) ( )6jkkj i jk k kj k n? ? ???? ? ? ? ? ?? ? ?Meta Operation ? 定義 ： ? 對任何計算步驟，它的代價總是以一個時間常量為上界，而不管輸入數(shù)據(jù)或執(zhí)行的算法，我們稱該計算步驟為 “ 元運算 ” 。 ? Candidate： ? 搜索和排序算法中，選元素比較運算 ? 矩陣乘法算法中，選數(shù)量乘法運算
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1