文章目錄

• 一、確定性模型的計算復雜性關系
• 二、證明 "多個帶子圖靈機時間復雜度是 $\mathrm{O}({\mathrm{n}}^2)$"

一、確定性模型的計算復雜性關系

---

計算的 復雜性 取決于 模型的計算 ;

給定一個函數 $\mathrm{t}(\mathrm{n})$ , 假設有一個 兩個帶子圖靈機 時間復雜度是 $\mathrm{O}(\mathrm{t}(\mathrm{n}))$ , 那么對應的有相同計算能力的 一個帶子圖靈機 時間復雜度是 $\mathrm{O}({\mathrm{t}}^2(\mathrm{n}))$ ;

示例 : 參考上一篇博客 【計算理論】計算復雜性 ( 兩個帶子的圖靈機的時間復雜度 ) , 識別語言 $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$ , 一個帶子圖靈機識別上述語言的 計算時間復雜度是 $\mathrm{O}({\mathrm{n}}^2)$ , 兩個帶子圖靈機識別上述語言的 計算時間復雜度是 $\mathrm{O}(\mathrm{n})$ ;

二、證明 "多個帶子圖靈機時間復雜度是 $\mathrm{O}({\mathrm{n}}^2)$"

---

參考 【計算理論】圖靈機 ( 多個帶子的圖靈機 | 計算能力對比 | 證明過程 | 一個帶子圖靈機 ) 博客 , 以如下三個帶子的圖靈機為例 , 加入下面的 三個帶子圖靈機的時間復雜度是 $\mathrm{t}(\mathrm{n})$ ;

使用 單個帶子圖靈機 模仿上述 三個帶子圖靈機 , 那么對應的單個帶子圖靈機的時間復雜度是 ${\mathrm{t}}^2(\mathrm{n})$ ;

計算 單個單子圖靈機 模仿 三個帶子圖靈機 一步的計算 , 需要花費的步數 ;

模仿的核心是將三個帶子的字符串放在一個帶子中 , 使用 “#” 分割 , 并使用紅色記錄三個帶子對應的位置 , 一個讀頭需要記錄三個位置 , 如下圖 :

使用 $1$ 個帶子的圖靈機 模擬 $3$ 個帶子的圖靈機 的代價是 讀寫頭必須從左向右整個遍歷一遍帶子 , 才能模擬 $3$ 個帶子的圖靈機 一步的計算 ;

最壞的情況下就是 , 三個帶子圖靈機走 $1$ 步 , 單個帶子圖靈機走 三個帶子所有字符串的內容長度 對應的步數 , 也就是 $10+4$ 步 , 多出來的 $4$ 步是 $4$ 個 “#” 分割字符 ;

三個帶子圖靈機 每個帶子的長度是 $\mathrm{t}(\mathrm{n})$ , 單個帶子圖靈機 帶子長度是 $3\mathrm{t}(\mathrm{n})$ ;

單個帶子圖靈機 模仿 三個帶子圖靈機 一步操作 , 最壞的情況下 , 需要執行的步數是 $3\mathrm{t}(\mathrm{n})$ ;

總共需要模仿 $\mathrm{t}(\mathrm{n})$ 步 , 因此總共需要模仿的步數是 $3{\mathrm{t}}^2(\mathrm{n})$ ;

如果是 四個帶子圖靈機 , 總共需要模仿的步數是 $4{\mathrm{t}}^2(\mathrm{n})$ ,

如果是 五個帶子圖靈機 , 總共需要模仿的步數是 $5{\mathrm{t}}^2(\mathrm{n})$ ,

如果是 一百個帶子圖靈機 , 總共需要模仿的步數是 $100{\mathrm{t}}^2(\mathrm{n})$ ,

其數量級還是 ${\mathrm{t}}^2(\mathrm{n})$ ,

因此增加到 $2$ 個帶子 , 與 增加到 $100$ 個帶子 , 甚至 一億個帶子 , 算法復雜度的數量級是 $\mathrm{O}({\mathrm{n}}^2)$ , 這是不變的 ;

單個帶子模仿多個帶子圖靈機 , 所花費的時間是平方增加 , 不管多個帶子的個數是多少 ;

總結

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 | 证明多个带子图灵机时间复杂度 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。