使用全局变量和返回值的两种解析实现之间的时间复杂度差异

Question

我正试图解决以下问题：

只包含小写字母的字符串可以编码为num[encoded string]格式。例如，AAA可以被编码为3[a]。给定一个编码的字符串，根据下面的语法找到它的原始字符串。

S -> {E}
E -> NUM[S] | STR  # NUM[S] means encoded, while STR means not.
NUM -> 1 | 2 | ... | 9
STR -> {LETTER}
LETTER -> a | b | ... | z

注意：在上述语法中，{}表示“串联0次或更多次”。

null

我想知道这两种方法是否共享相同的时间复杂度。假设结果字符串的长度为T。那么对于方法II，我认为它的时间复杂度应该是O(t)，因为我们正好读写结果字符串中的每个字符一次。但是，对于方法i，我的直觉是它可能会慢一些，因为相同的子字符串可以被复制多次，这取决于递归的深度。但我无法计算出确切的时间复杂度来证明我的直觉是正确的。谁能给个提示吗？

Answer 1

我的第一个建议是，无论您选择编写递归下降解析器、基于状态的解析器还是使用解析器生成器，您的解析器都应该产生一个抽象语法树，而不是直接解释字符串。这极大地增强了可维护性,并允许您更容易地执行验证、分析和转换。

如果我没理解错的话，在方法I中，每个语法构造都有函数返回一个不可变的字符串，然后这些函数被递归地重复和串联。例如,对于顶级级联规则

S ::= E*

您将有一个解释函数如下所示：

string interpretS(NodeS sNode) {
    string result = "";
    for (int i = 0; i < sNode.Expressions.Length; i++) {
        result = result + interpretE(sNode.Expressions[i]);
    }
    return result;
}

请注意，要使其工作，不需要全局变量！一个更干净的解决方案只需通过对结果结构的引用传递（这个模式称为累加器参数）。现在，我们将具有如下功能：

void interpretS2(NodeS sNode, StringBuilder accumulator) {
   for (int i = 0; i < sNode.Expressions.Length; i++) {
      interpretE2(sNode.Expressions[i], accumulator);
   }
}

void interpretE2(NodeE eNode, StringBuilder accumulator) {
   if (eNode is NodeNum numNode) {
       for (int i = 0; i < numNode.Repetitions; i++) {
          interpretS2(numNode.Expression, accumulator);
       }
   }
   else if (eNode is NodeStr strNode) {
      for (int i = 0; i < strNode.Letters.Length; i++) {
         interpretLetter2(strNode.Letters[i], accumulator);
      }
   }
}

void interpretLetter2(NodeLetter letterNode, StringBuilder accumulator) {
    accumulator.Append(letterNode.Letter);
}
...

正如您所说的那样，这里的时间复杂度是O(n)，因为在每一步，输出的一个字符都被添加到累加器中，并且没有任何字符串被复制（只有在最后，当可变结构被转换为输出字符串时）。

因此，至少对于这种语法，方法II显然是更可取的。

但是，这不会改变最坏情况下的复杂性O(N²):考虑以下示例

1[a1[b[1[c[1[d[1[e[1[f]]]]]]]]]]

即使是不那么简单的方法I也会先将f追加到e（1步），然后将ef追加到d（+2步），再将def追加到c（+3步），依此类推，总共是1+2+3+4+5步。

方法I具有二次时间复杂度的根本原因是复制子表达式的结果以创建要返回的新子结果。