[計算機軟件及應(yīng)用]算法及其描述-文庫吧資料
2024-12-29 12:46本頁面
【正文】 )/2（當(dāng) n個整數(shù)為從大到小排列時）。a[i]=a[j]。j=n。i=n?1。} 每個賦值語句執(zhí)行頻率為 n(n+1)/2, 該算法的時間復(fù)雜度為 :O(n^2) 一個算法的運行時間，與問題的規(guī)模相關(guān)，也與輸入的數(shù)據(jù)相關(guān)。j++) ? { x=k+j。k++) ?for(j=1。 ?for(k=1。 } “t=1” 與“ k=1” 各執(zhí)行 1次；“ k=n” 與“ k++” 各執(zhí)行 n次；“ t=t*2” 執(zhí)行 n次；“ j=1” 執(zhí)行 n次；“ j=t” 、“ j++” 與內(nèi)循環(huán)的賦值語句“ s=s+j” 各執(zhí)行頻數(shù)為 : 總的執(zhí)行頻數(shù)為： ? 時間復(fù)雜度符號 O的兩個定理 : ? 在估算算法的時間復(fù)雜度時，為簡單計，以后只考慮內(nèi)循環(huán)語句的執(zhí)行頻數(shù)，而不細(xì)致計算各循環(huán)設(shè)計語句及其它語句的執(zhí)行次數(shù)，這樣簡化處理不影響算法的時間復(fù)雜度。j=t。k++) ? { t=t*2。 } “k=1” 執(zhí)行 1次；“ k=n” 與“ k++” 各執(zhí)行 n次； 3個賦值語句，每個賦值語句各執(zhí)行 n次；共執(zhí)行 5n+1次 . 時間復(fù)雜度為 O(n). 例 13 試計算下面三個程序段的執(zhí)行頻數(shù) (3) for(t=1,k=1。 ? y=x+y。k=n。 s=s+x。 2個語句各執(zhí)行 1次，共執(zhí)行 2次 。 ? 在分析算法時，隱藏細(xì)節(jié)的數(shù)學(xué)表示方法為大寫字母 “ O”記法，它可以幫助我們簡化算法復(fù)雜度計算的許多細(xì)節(jié)，提取主要成分 。 算法的時間復(fù)雜度通常用該算法執(zhí)行的總語句（運算）的數(shù)量級決定。 一個算法的時間復(fù)雜度是指算法運行所需的時間。 數(shù)學(xué)方法能在嚴(yán)密的邏輯推理基礎(chǔ)上判斷算法的優(yōu)劣。通常我們可以利用 實驗對比方法、數(shù)學(xué)方法 來分析算法 。 ? 時間復(fù)雜度與空間復(fù)雜度集中反映算法的效率。 ? 最重要的計算機資源是時間資源與空間資源。 // 每試商一位 n增 1 ? } ? print(n)。 ? c=a%2021。n=4。每商一位，統(tǒng)計被除數(shù)中“ 1” 的個數(shù)的變量 n增 1。 ? 設(shè)置豎式除法模擬循環(huán)，循環(huán)中被除數(shù)a=c*10+1，試商余數(shù) c=a%2021。 ? 循環(huán)以余數(shù) c≠0 作為循環(huán)條件。當(dāng)除運算的余數(shù)為“ 0”時，數(shù)一數(shù)被除數(shù)中有多少個“ 1” 即可。 } ? print(b)。 b=r。 ? (2) 若 r≠0 ，以 b為 a， r為 b，繼續(xù) (1). ? 歐幾里德算法具體描述如下： ? input(a,b)； //
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1