算法與數(shù)據(jù)結(jié)構(gòu)-算法與流程-資料下載頁
2025-05-14 03:42本頁面
【正文】 從四個方面進行：正確性、簡單性、運行時間、占用空間。但主要看這個算法所要占用機器資源的多少。而在這些資源中時間和空間是兩個最主要的方面，因此算法分析中最關(guān)心的也就是算法所需的時間代價和空間代價。 算法分析 41 34 1. 空間 所謂算法的空間代價 (或稱空間復(fù)雜性 )，是指當(dāng)問題的規(guī)模以某種單位由 1增至 n時，解決該問題的算法實現(xiàn)所占用的空間也以某種單位由 1增至 f(n)，并稱該算法的空間代價是 f(n)。 算法分析 42 35 2. 時間 (1) 語句頻度 (Frequency Count)：指的是在一個算法中該語句重復(fù)執(zhí)行的次數(shù)。 (2) 算法的漸近時間復(fù)雜度 (Asymptotic Time Complexity)：算法中基本操作重復(fù)執(zhí)行的次數(shù)依據(jù)算法中最大語句頻度來估算，它是問題規(guī)模 n的某個函數(shù) f(n)，算法的時間量度記作T(n)=O(f(n))，表示隨著問題規(guī)模 n的增大，算法執(zhí)行時間的增長率和 f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。時間復(fù)雜度往往不是精確的執(zhí)行次數(shù)，而是估算的數(shù)量級。它著重體現(xiàn)的是隨著問題規(guī)模的增大，算法執(zhí)行時間增長的變化趨勢。 算法分析 43 36 例如，在下列三個程序段中： (a) x=x+1。 (b) for(i=1。i=n。i++) x=x+1。 (c) for(j=1。j=n。j++) for(k=1。k=n。k++) x=x+1。 語句 x=x+1的頻度分別為 n和 ，則 (a)、 (b)、 (c)的時間復(fù)雜度分別是 O(1)、 O(n)、 O( )。由此可見，隨著問題規(guī)模的增大，其時間消耗也在增大。 算法分析 44：常用算法實現(xiàn)與分析 37 結(jié)構(gòu)化程序設(shè)計基本要求 ?自頂向下，模塊化設(shè)計 ?使用三種基本結(jié)構(gòu)構(gòu)造程序 ?程序書寫規(guī)范，切勿隨心所欲 ?清晰第一，效率第二 思路清晰 書寫清晰（變量名、函數(shù)、注解等） 書寫注意縮進 38 總結(jié) ?算法和數(shù)據(jù)結(jié)構(gòu) ?用流程圖描述算法 ?用 C語言描術(shù)算法
試題試卷相關(guān)推薦
鄂ICP備17016276號-1