數據結構課件緒論-資料下載頁
2025-08-01 15:06本頁面
【正文】 間復雜度 （ 2）定義： 一般情況下，算法中 基本操作 重復執(zhí)行 的時間是問題規(guī)模 n的某個函數 f(n)，算法的時間量度記作 T(n) = O(f(n)) 它表示隨問題規(guī)模 n的增大，算法執(zhí)行時間的增長率和 f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱 時間復雜度 。 ? 語句的 頻度 ：該語句重復執(zhí)行的次數。頻度統計法 表：時間復雜度和算法運行時間的關系 T(n) n O(logn) O(n) O(nlogn) O(n2 ) O(n3 ) O(n5 ) O(2n ) O(n!)) 20 20us 400us 8ms 771世紀 40 40 213 1600 64ms *1032世紀 60 60 354 3600 216ms 13min 366世紀 *1066世紀 結論 （ 1）當 f(n)為對數函數、冪函數、或它們的乘積時，算法的運行時間是可以接受的，稱這些算法是有效算法；當 f(n)為指數函數或階乘函數時，算法的運行時間是不可接受的，稱這些算法是無效的算法。 （ 2）隨著 n值的增大，增長速度各不相同， n足夠大時，存在下列關系： 對數函數 冪函數 指數函數 常見函數的增長率 O(1) 常量階，與 n無關 O(log n) log n階 O(n) n階 O(n log n) n log n階 O(n2) 平方階 O(n3) 立方階 O(2n) 指數階 ? 增長率由慢到快 圖示見 p16圖 17 ? 盡量少用指數階的算法 ? 說明：教材 p17第 2行 除特別指明外，均指最壞情況下的時間復雜度 6. 空間復雜度 （ 1）存儲算法本身所占用的空間 （ 2）算法的輸入 /輸出數據占用的空間 （ 3）算法在運行過程中臨時占用的輔助空間 ? 原地工作：若輔助空間相對于輸入數據量是常數，則稱此算法是原地工作。 ? 若所占空間量依賴于特定的輸入，按最壞情況來分析。
環(huán)評公示相關推薦
鄂ICP備17016276號-1