计算复杂度 v/s 乔姆斯基层次结构
原文:https://www . geesforgeks . org/computational-complex-v-s-Chomsky-hierarchy/
1。计算复杂度: 计算复杂度，衡量特定算法运行时消耗的计算资源(时间和空间)数量。
图灵机的时间复杂度由函数 T(n)给出，其中
T(n)= TM 处理长度为 n 的字符串的最大移动次数
图灵机的空间复杂度由函数 S(n)给出，其中
S(n) =对于长度为 n 的输入，TM 使用的最大磁带方块数
简单图灵机的 时间复杂度 考虑一下语言，
L = {ωcωR |ω∈(0+1)*}
要识别形式为ωcω R 的字符串，TM 需要:
比较第一个和最后一个字符= 2n + 1 次移动
比较两端的第二个字符= 2(n -1) + 1 次移动
找到中心字符 c = 1 移动
总移动次数 T(n)，
= (2n + 1) + (2 (n - 1) +1)+.......(2(n -(n -1)) + 1) + 1
= 2(1+2+.........+n)+n = 2 X (n)(n+1) / 2 + n = n2 + 2n
= n2+2n
= O(n<sup>2</sup>)
采用双带机器可以降低时间复杂度。
- 机器将 c 左边的输入字符串复制到第二盘磁带上。
- 当在输入磁带上找到 c 时，TM 将其第二个磁带头向左移动。
- 输入磁头继续向右移动，第二个磁头继续向左移动。
- 随着头部的移动，两个头部下的符号会进行比较。
- 如果所有的符号都匹配，并且中心字符是 c，那么该字符串被接受。
TM 最多进行 n+1 次移动。
T(n) = n+1 = O(n)
TM 的空间复杂度由S(n)= n+1【n-字符串长度和一个空白符号】给出
非确定性时间和空间复杂度: 如果没有选择序列导致机器移动超过 T(n)，则非确定性 TM 的时间复杂度为 T(n)。如果没有一个选择序列需要更多的磁带单元，那么空间复杂度就是 S(n)。
【乔姆斯基层次结构】 : 一个语法可以根据产生式规则进行分类。乔姆斯基将语法分为以下几种类型:
A ⇢ ε A ⇢ a
A ⇢ aB A ⇢ Ba
版权属于：月萌API www.moonapi.com，转载请注明出处
