文章目錄

• 一、計(jì)算理論內(nèi)容概覽
• 二、計(jì)算問題的判定性
• 三、計(jì)算問題的 有效性
• 四、時(shí)間復(fù)雜性度量
• 五、算法有效性 數(shù)學(xué)定義需求
• 六、輸入表示
• 七、時(shí)間復(fù)雜度

一、計(jì)算理論內(nèi)容概覽

---

計(jì)算理論分為 形式語言與自動機(jī) , 可計(jì)算部分 , 計(jì)算復(fù)雜性部分 ;

形式語言與自動機(jī) 內(nèi)容 : 自動機(jī) , 確定性有限自動機(jī) , 非確定性有限自動機(jī) , 正則語言 , 泵引理 , 上下文無關(guān)語法 , 下推自動機(jī) , 都屬于 形式語言 與 自動機(jī) 部分 ;

可計(jì)算 內(nèi)容 : 圖靈機(jī) , 確定性圖靈機(jī) , 非確定性圖靈機(jī) , 丘奇-圖靈命題 , 可判定性 , 可計(jì)算性 等問題 ;

計(jì)算復(fù)雜性 內(nèi)容 : 時(shí)間復(fù)雜性 , 模型間的時(shí)間復(fù)雜性關(guān)系 , $\mathrm{P}$ 類 , $\mathrm{N}\mathrm{P}$ 類 ;

計(jì)算理論 知識點(diǎn)很枯燥 , 但是 在進(jìn)行理論研究時(shí) , 或者大的計(jì)算機(jī)工程實(shí)踐時(shí) , 很有用 ;

二、計(jì)算問題的判定性

---

根據(jù)計(jì)算模型 , 可以將判定性問題 , 總結(jié)成以下幾點(diǎn) :

① 所有 關(guān)于 圖靈機(jī) 的計(jì)算問題 , 都是 不可判定的 ; ( 萊斯定理 )

② 所有 關(guān)于 確定性有限自動機(jī) 的計(jì)算問題 , 都是可判定的 ;

③ 關(guān)于 下推自動機(jī) 的計(jì)算問題 , 有些可判定 , 有些不可判定 ;

三、計(jì)算問題的 有效性

---

可計(jì)算性 包含 可判定性 , 可判定性 包含 有效性 ;

可計(jì)算性 > 可判定性 > 有效性 ;

計(jì)算問題 對應(yīng)的算法中 , 有些算法是 有效的 , 有些算法是 無效的 ,

如 : 窮舉算法 , 蠻力搜索之類的算法 , 沒有有效性可言 , 肯定不是有效算法 ; 貪心算法 , 歐幾里得算法 是有效算法 ;

這里希望可以區(qū)分 有效算法 與 無效算法 ;

四、時(shí)間復(fù)雜性度量

---

計(jì)算機(jī)中度量時(shí)間長短有兩種方式 :

① 離散時(shí)間 ( 自然數(shù)表達(dá) ) : 時(shí)間是離散的 , 如 $1,2,3,4,?$ 秒

② 連續(xù)時(shí)間 ( 實(shí)數(shù)表達(dá) ) : 時(shí)間是連續(xù)的 , 如 $1.221457?$ 秒

計(jì)算復(fù)雜性的表達(dá)使用的是 離散時(shí)間 , 自然數(shù)表達(dá) ;

五、算法有效性 數(shù)學(xué)定義需求

---

有效性 與 無效性 區(qū)分時(shí) , 將 貪心算法 分到有效性算法中 , 將蠻力窮舉的算法 分到無效性算法中 ;

需要定一個(gè)區(qū)分原則 , 區(qū)分算法的有效性 , 將一個(gè)算法分為 有效算法 或 無效算法 ;

為 算法有效性 提供一個(gè) 嚴(yán)格的數(shù)學(xué)定義 ;

六、輸入表示

---

輸入字符串大小 , 輸入字符串越長 , 所花的時(shí)間越長 , 計(jì)算所花的時(shí)間與輸入字符串時(shí)單調(diào)遞增的 ;

有效性 進(jìn)行定義時(shí) , 通過輸入字符串大小進(jìn)行度量 ;

計(jì)算機(jī)計(jì)算輸入有很多形式 , 數(shù)字 , 圖形 , 字符串 , 二進(jìn)制數(shù)據(jù) 等 ;

數(shù)字的表示 , 假如輸入數(shù)字是 $17$ , 要將對應(yīng)的時(shí)間復(fù)雜度理解成 $2$ , 這個(gè)數(shù)字由 $2$ 位數(shù)字組成的 ;

如果將上述 $17$ 數(shù)字 , 使用二進(jìn)制表示 , 是 $10001$ , 輸入位數(shù)是 $5$ , 對應(yīng)的時(shí)間復(fù)雜度理解成 $5$ ;

算法復(fù)雜性 只與輸入的數(shù)據(jù)大小有關(guān) , 輸入的大小必須是合理的 ;

輸入數(shù)字時(shí) , 可以輸入 十六進(jìn)制 , 十進(jìn)制 , 八進(jìn)制 , 二進(jìn)制 , 但是不能輸入 一進(jìn)制數(shù)字 , 一進(jìn)制輸入是不合理的 ;

七、時(shí)間復(fù)雜度

---

假設(shè) $\mathrm{M}$ 是 確定性圖靈機(jī) , 該圖靈機(jī)在所有的輸入上都會 停機(jī) ;

因?yàn)樵搱D靈機(jī)會停機(jī) , 其結(jié)果不是接受 , 就是拒絕 , 不會出現(xiàn) Loop 不停機(jī)的狀態(tài) , 因此該 圖靈機(jī) $\mathrm{M}$ 是判定機(jī) ;

圖靈機(jī) $\mathrm{M}$ 的運(yùn)行時(shí)間 或 時(shí)間復(fù)雜度 是一個(gè)函數(shù) $\mathrm{f}$ , 該函數(shù)是 從 自然數(shù)集 到 自然數(shù)集上的映射 , $\mathrm{N}\to \mathrm{N}$ ;

前面的自然數(shù)集 $\mathrm{N}$ 主要是度量的 輸入字符串大小 , 后面的自然數(shù)集 $\mathrm{N}$ 是計(jì)算的步數(shù) ;

$\mathrm{f}(\mathrm{n})$ 的含義是度量 長度為 $\mathrm{n}$ 的所有字符串 , 計(jì)算時(shí)所花費(fèi)的步數(shù)的 最大值 ;

證明 $\mathrm{M}$ 為什么必須是判定機(jī) :

假設(shè) $\mathrm{M}$ 是圖靈機(jī) , 在某些輸入上是不停機(jī)的 , 如輸入字符串為 $\mathrm{a}\mathrm{a}\mathrm{b}$ ;

圖靈機(jī) $\mathrm{M}$ 在 $\mathrm{a}\mathrm{a}\mathrm{b}$ 字符串上進(jìn)行計(jì)算時(shí) , 進(jìn)入 Loop 狀態(tài) , 不停機(jī) , 此時(shí)定義 $\mathrm{f}(3)$ 的值只能是無窮大 ;

此時(shí)該函數(shù) $\mathrm{f}(\mathrm{n})$ 就沒有意義了 ;

函數(shù)在數(shù)字上進(jìn)行取值時(shí) , 必須是一個(gè)具體的數(shù)字 ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( 计算理论内容概览 | 计算问题的有效性 | 时间复杂性度量 | 输入表示 | 时间复杂度 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。