ds01-概論-陳越主編-數(shù)據(jù)結(jié)構(gòu)(編輯修改稿)
2024-08-21 19:01 本頁面
【文章內(nèi)容簡介】 S(n) = c n 其中 ： n是需要打印的整數(shù)的個數(shù) ，是變量； c是 1個單位的內(nèi)存空間占用存儲單元的長度，為固定常數(shù)。 當一個函數(shù) A內(nèi)部調(diào)用函數(shù) B時，必須先把 A的當前狀態(tài)保存在內(nèi)存中，當 B被調(diào)用完成后再釋放；若是遞歸調(diào)用，則必須把遇到出口以前的所有的調(diào)用狀態(tài)保存，所以參數(shù)越大，占用空間越多。 ? 例 秦九韶算法 的 T(n)比較小： T1(n) = c n 其中 ： n是 多項式的階 數(shù) ，是變量； c是執(zhí)行 1次加法和乘法需要的時間，為固定常數(shù)。 ? 而 簡單直接算法 的 T(n)比較大： T2(n) = c1n2+c2n ， 其中 ： n是 多項式的階 數(shù) ，是變量； c1是執(zhí)行 1/2次乘法需要的時間 ； c2是執(zhí)行 1次加法和 1/2次乘法需要的時間，都是固定常數(shù)。 13/25 第 1章 概論 167。 算法復(fù)雜度 ? 我們經(jīng)常關(guān)注下面兩種復(fù)雜度： ? 最壞情況復(fù)雜度： Tworst(n) ? 平均復(fù)雜度： Tavg(n) ? 顯然 : Tavg(n) ≤ Tworst(n)。 對 Tworst(n) 的分析往往比對 Tavg(n)的分析容易。 14/25 ? 如果 : 程序 A執(zhí)行了 (3n+4)步， 程序 B執(zhí)行了 (2n+2)步， A一定比 B慢嗎？ ? No！ ? Why? 第 1章 概論 167。 復(fù)雜度的漸進表示法 ? 如何來“ 度量 ”一個算法的時間復(fù)雜度呢？ ? 首先，它應(yīng)該與運行該算法的 機器和編譯器無關(guān) ； ? 其次，它應(yīng)該與要解決的問題的 規(guī)模 n 有關(guān) ； （有時，描述一個問題的規(guī)模需要多個參數(shù)） ? 再次，它應(yīng)該與算法的“ 1步 ”執(zhí)行需要的 工作量無關(guān) ！ ? 所以，在描述算法的時間性能時，人們只考慮 宏觀漸近性質(zhì) ，即當輸入 問題規(guī)模 n“充分大”時，觀察算法復(fù)雜度隨著 n 的“ 增長趨勢 ”： 當變量 n不斷增加時，解決問題所需要的時間的增長關(guān)系。 ? 比如：線性增長 T(n) = cn 即問題規(guī)模 n增長到 2倍、 3倍 …… 時，解決問題所需要的時間 T(n)也是增長到 2倍、 3倍 …… （ 與 c無關(guān) ） ? 平方增長： T(n) = cn2 即問題規(guī)模 n增長到 2倍、 3倍 …… 時，解決問題所需要的時間 T(n)增長到 4倍、 9倍 …… （ 與 c無關(guān) ） 15/25 第 1章 概論 ? 引入下面幾種數(shù)學(xué)符號： [定義 ] T (n) = O(f(n)) 表示存在常數(shù) c 0, n0 0 ， 使得當 n ≥ n0 時有 T (n) ≤ c f(n) ? 例 中秦九韶算法的時間復(fù)雜度是 O(n) ， 而簡單直接法的時間復(fù)雜度是 O(n2) 。 [定義 ] T (n) = Ω(g(n)) 表示存在常數(shù) c 0, n0 0 ， 使得當 n ≥ n0 時有 T (n) ≥ c g(n) 167。 復(fù)雜度的漸進表示法 [定義 ] T (n) = Θ(h(n)) 表示 T (n) = O(h(n)) 同時 T (n) = Ω(h(n)) 16/25 第 1章 概論 ? 常用函數(shù)增長表 167。 復(fù)雜度的漸進表示法 輸入規(guī)模 n 函數(shù) 1 2 4 8 16 32 1 1 1 1 1 1 1 log2 n 0 1 2 3 4 5 n 1 2 4 8 16 32 n log2 n 0 2 8 24 64 160 n2 1 4 16 64 256 1024 n3 1 8 64 512 4096 32768 2n 2 4 16 256 65536 4294967296 n! 1 2 24 40326 2092278988000 26313 ? 1033 17/25 0 1 2 3 4 5 6 7 8 9 1001020304050602n n2 n log n n log n f n 第 1章 概論 167。 復(fù)雜度的漸進表示法 18/25 每秒 10 億指令計算機的運行時間表 n f ( n )= n log2n n2 n3 n4 n10 2n 10 20 30 40 50 100 1, 000 10, 000 100, 000 1, 000, 000 . 01 ? s . 02 ? s . 03 ? s . 04 ? s . 05 ? s . 10 ? s 1. 00 ? s 10 ? s 100 ? s 1. 0ms . 03 ? s . 0
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1