表达式评估的大O
Big O of Expression Evaluation
我是一名老师，我告诉我的学生，像 y=15x+8 这样的表达式的大 O 是 O(1)，但是当我们学习前缀和后缀时，我们讨论了评估这些表达式是 O (N) 因为你必须遍历等式的每个字符（假设给你一个字符串）。
一位学生问，如果在幕后必须进行中缀、后缀或前缀评估，我们怎么说计算表达式的复杂度为 O(1)。
我不知道该回答什么。
表达式本身没有任何时间复杂度。解决 问题 的 算法 可能具有时间复杂度。因此，这完全取决于您将什么定义为问题以及将什么定义为复杂性的相关参数。如果你有一个固定的分配，例如
y := 15 * x + 8;
问题可以定义为“使用输入参数x计算15 * x + 8的值”。所以在这里你想将时间复杂度表示为依赖于 x 的函数。时间复杂度为 O(1)，假设我们讨论的是标准 32/64 位算术计算，否则 O(log x)，如果这是任意精度算术。
但是，如果将表达式的大小视为变量，问题就变成了“计算具有k个节点的算术表达式树的值，其中k是一个输入参数”。正如您正确指出的那样，这是一个 不同的 问题，并且具有不同的复杂性。
我是一名老师，我告诉我的学生，像 y=15x+8 这样的表达式的大 O 是 O(1)，但是当我们学习前缀和后缀时，我们讨论了评估这些表达式是 O (N) 因为你必须遍历等式的每个字符（假设给你一个字符串）。
一位学生问，如果在幕后必须进行中缀、后缀或前缀评估，我们怎么说计算表达式的复杂度为 O(1)。
我不知道该回答什么。
表达式本身没有任何时间复杂度。解决 问题 的 算法 可能具有时间复杂度。因此，这完全取决于您将什么定义为问题以及将什么定义为复杂性的相关参数。如果你有一个固定的分配，例如
y := 15 * x + 8;
问题可以定义为“使用输入参数x计算15 * x + 8的值”。所以在这里你想将时间复杂度表示为依赖于 x 的函数。时间复杂度为 O(1)，假设我们讨论的是标准 32/64 位算术计算，否则 O(log x)，如果这是任意精度算术。
但是，如果将表达式的大小视为变量，问题就变成了“计算具有k个节点的算术表达式树的值，其中k是一个输入参数”。正如您正确指出的那样，这是一个 不同的 问题，并且具有不同的复杂性。