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