第四課：線性表的類型定義

第四課

本課主題 算法效率的度量和存儲空間需求

教學目的 掌握算法的漸近時間復雜度和空間復雜度的意義與作用

教學重點 漸近時間復雜度的意義與作用及計算方法

教學難點 漸近時間復雜度的意義

授課內容

一算法效率的度量

算法執行的時間是算法優劣和問題規模的函數評價一個算法的優劣可以在相同的規模下考察算法執行時間的長短來進行判斷而一個程序的執行時間通常有兩種方法

事後統計的方法

缺點不利於較大范圍內的算法比較（異地異時異境）

事前分析估算的方法

程序在計算機上運行所需時間的影響因素

算法本身選用的策略

問題的規模

規模越大消耗時間越多

書寫程序的語言

語言越高級消耗時間越多

編譯產生的機器代碼質量

機器執行指令的速度

綜上所述為便於比較算法本身的優劣應排除其它影響算法效率的因素

從算法中選取一種對於所研究的問題來說是基本操作的原操作以該基本操作重復執行的次數作為算法的時間量度（原操作在所有該問題的算法中都相同）

T(n)=數據結構免費提供，內容來源於互聯網,本文歸原作者所有。