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

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次或多次”。

例如，给定编码字符串 3[a2[c]]，结果（原始字符串）为 accaccacc。

我觉得这个可以通过递归下降解析来解析，有两种实现方式：

方法一：让解析方法直接return结果字符串
方法二：使用全局变量，每个解析方法只需要追加字符即可。

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

Answer 1

时间复杂度是通过计算算法执行的基本操作的数量来估算的，假设每个基本操作都需要固定的时间来执行，请参阅 here。然而，有趣的是，当输入数据集的大小增加时，操作数量的增加速度有多快。
在您的情况下，输入数据的大小表示要解析的字符串的长度。

我假设你的第一种方法是指当遇到 NUM 时，它的参数被解析器完全处理 NUM 次。在您的示例中，当从输入字符串中读取“3”时，“a2[c]”将被完整处理 3 次。这里的处理意味着将语法树横向到一个叶子，并将叶子值附加到输出字符串，这里是“c”。

我还假设你的第二种方法是指当遇到 NUM 时，它的参数只被评估一次，所有中间结果都被存储和重新使用。在您的示例中，当从输入字符串中读取“3”并存储时，从输入字符串中读取“a”并存储，处理“2[c]”，即从输入字符串中读取“2”并存储，最后处理“c”。 “c”是由于存储的“2”组合为“cc”，并且由于存储的“a”组合为“acc”。这是由于存储的“3”组合为“accaccacc”，输出“accaccacc”。

现在的问题是，与时间复杂度相关的初等运算是什么？我的感觉是，在第一种情况下，语法树遍历过程中的堆栈操作很重要，而在第二种情况下，字符串复制操作很重要。
严格来说，因此无法比较两种算法的时间复杂度。
但是，如果您对运行次而不是时间复杂度感兴趣，我的猜测是堆栈操作比字符串复制花费更多时间，那么方法 2 更可取。

Answer 2

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

方法一

如果我理解正确的话，在方法 I 中，每个语法结构都有函数，return 一个不可变的字符串，然后递归地重复和连接。例如，对于顶级连接规则

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;
}

... 其他规则也类似。很容易看出，方法一的时间复杂度是O(n²)，其中n是输出的长度。（注意：根据输出而不是输入来衡量时间复杂度是有意义的，因为输出长度是输入长度的指数，因此任何解释方法必须至少具有时间复杂度输入中的指数，这不是很有趣。）例如，解释输入 abcdef 需要连接 a 和 b，然后将结果与 c，然后将该结果与 d 等连接起来，得到 1+2+3+4+5 步。（请参阅 here 以更详细地讨论为什么重复的字符串与不可变字符串的连接具有二次复杂性。）

方法二

我这样解释您对方法 II 的描述：您不必 returning 必须组合的单个字符串，而是保留对表示支持追加的字符串的可变结构的引用。这可能是 Java 或 .NET 中的 StringBuilder 之类的数据结构，或者只是一个动态长度的字符列表。重要的一点是，将长度为 b 的字符串附加到长度为 a 的字符串可以在 O(b) 中完成（而不是 O(a+b)）。

请注意，要使其正常工作，您不需要全局变量！更简洁的解决方案只是将引用传递给生成的结构（此模式称为 累加器参数 ）。所以现在我们会有这样的功能：

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 显然更可取。

根据评论更新

当然，我对上述方法一的解释是极其幼稚的。 interpretS 函数的更现实的实现将在内部使用 StringBuilder 来连接子表达式的结果，从而导致上面给出的示例 abcdef.

的线性复杂度

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

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

即使是较简单的方法版本，我也会先将 f 追加到 e（1 步），然后将 ef 追加到 d（+ 2 步） , 然后将 def 附加到 c （+ 3 步）等等，总共 1+2+3+4+5 步。

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

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

Time Complexity Difference between Two Parsing Implementations Using Global Variables and Return Values

parsing

time-complexity

方法一

方法二

根据评论更新