計(jì)算復(fù)雜性理論(編輯修改稿)
2024-09-11 23:45 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1千 2千 ? 2n 23 27 30 33 ? n! 10 11 12 13 ? 1000倍 ? 1step 用 109秒 ? 109秒 光 可以行進(jìn) 30cm 計(jì)算機(jī)速度增加的效果（ 2） 計(jì)算速度 1秒可以求解問題的規(guī)模 O(2n) O(n) O(n2) O(n5) O(n10) 1 100 100 100 100 100 2 101 200 141 115 107 10 103 1000 316 158 126 100 107 10000 1000 251 158 1000 110 100000 3162 398 200 10000 113 1000000 10000 631 251 100000 117 10000000 31623 1000 316 1000000 120 100000000 100000 1585 398 平行（并列） 計(jì)算 的場(chǎng)合 cm 見 方 小碎片，覆蓋 地球表面 需要 1019個(gè) . 與 100MIPS的單個(gè) 計(jì)算機(jī) 相比 ，能加速多少 ？ n 100 1,000 . 2n 1014世紀(jì) → 秒 10284世紀(jì) → 10 263世紀(jì) n! 10141世紀(jì) → 10 120世紀(jì) 102551世紀(jì) → 10 2530世紀(jì) 問題與算法 ? 每個(gè) 問題 都可能有多個(gè)算法存在 ． ? 每個(gè)算法的計(jì)算量（速度）都不同。 例： ? 贗品 金 幣 問題： ? 問題 ： 9個(gè) 外觀完全一樣的 金 幣 .，有一個(gè)是假的（重量輕） ． ? 提問 ： 用 天秤 來(lái)鑒別真?zhèn)危?天秤 需要使用幾次？ 贋 品 金 幣 問題 算法 ? 使用 2次 天秤 ,就可以鑒別出假幣 . 7 8 9 １ 2 3 4 5 6 左 邊 軽 右 邊 軽 平衡 １ 2 3 中有 偽 幣 7 8 9 中有 偽 幣 4 5 6 中有 偽 幣 左 邊 軽 １ 3 2 右 邊 軽 平衡 １ 3 2 4 5 6 7 8 9 計(jì)算量的表示法 : 上界值表示法 ? O記號(hào) ： (Big O Notation) ?定 義 : O(f(n)) 讀作 order f(n), 或階 f(n) 即： g(n)=O(f(n)) –表示對(duì)于任意 定數(shù) c 和 m，以及對(duì)所有 n＞ m， 有下式成立： g(n)＜ cf(n) 計(jì)算量的表示法 —— 例 ? n２ +1000n→ O(n２ ) ? log n+n3+1000n2 → O(n3) 判斷： ? n! → O(nn)？ ? 10n2 → O(n3)？ ? log n → O(n)？ 思考： ????是偶數(shù)時(shí)是奇數(shù)時(shí)nnnng,1)(2O()? 優(yōu)化問題的規(guī)模 表示優(yōu)化 問題 大小的參數(shù) 例如： 旅行商問題： 都市 的個(gè) 數(shù) 。 背包問題：物品的個(gè)數(shù) 注：參數(shù)的個(gè)數(shù)并不僅限于 1個(gè) Input Size 多項(xiàng)式時(shí)間算法與指數(shù)時(shí)間算法 指數(shù)時(shí)間 算法 = 用問題規(guī)模的 指數(shù) 函數(shù)來(lái)表示 計(jì)算時(shí)間 的算法 非有效算法的 代名詞 多項(xiàng)式時(shí)間 算法 = 能用問題規(guī)模的多項(xiàng)式函數(shù)來(lái)表示 計(jì)算時(shí)間 的算法 高效率算法的 代名詞 多項(xiàng)式時(shí)間算法的計(jì)算時(shí)間 問題規(guī)模 計(jì)算時(shí)間 10 20 30 40 50 100 1000 10000 秒7101 ?? ??秒7102 ?? 秒7103 ? 秒74 ?? 秒7105 ?秒6101 ?? 秒5101 ?? 秒4? ?? ?? ? 秒682. ? ? 秒 ? ??n nn 2log2n 3n 5n 秒6101 ?? 秒6104 ?? 秒6109 ? ?? 秒 ?秒4101 ?? 秒210??秒1秒5101 ?? 秒5108 ? ?? ? ??秒10 秒021 日115世紀(jì)31100MIPS(million instructions per second) 計(jì)算機(jī)的情形 指數(shù)時(shí)間算法 的計(jì)算時(shí)間 100MIPS(million instructions per second) 計(jì)算機(jī)的情形 問題 規(guī)模 計(jì)算時(shí)間 10 20 30 40 50 100 1宙齢 =150億年 n2 nn 22n3 !n 秒5101. ?? ??秒10 日130 宙齢26798 日
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1