编译器降低程序时间复杂度是否合法？这被认为是可观察行为吗？

Question

_{（注：这是一个语言律师问题，我不是在指任何特定的编译器。）}

编译器在什么情况下可以降低程序的时间复杂度？
在什么情况下（如果有的话）被认为是“可观察的行为”，为什么？
（例如，编译器是否可以将多项式时间程序合法地“降级”为指数时间程序？）

如果C和C ++中的答案不同，或者在它们的不同版本中不同，请解释其差异。

- user541686

---

“degrade”指的是它会变得更糟吗？我很难看出编译器如何做到这一点，因为与O有关的几乎所有内容都基于整体算法，我不明白编译器如何使其更糟（在某些罕见情况下，它可能会识别您想要做什么并使其更好，但那不是同一件事）。 - Mats Petersson

至少有一个简单的答案：当发生未定义行为时！标准是否对用户空间复杂性有任何说明？ - user657267

@MatsPetersson说：“我不知道，我可以想出很多例子。例如，编译器是否可以用线性查找替换二进制查找，可能是因为它认为这对于较小的数组可能更快？” - user541686

时间复杂度的好处（或者说毒瘤之处）在于它与你运行程序的机器速度无关。 - user541686

所以，你提到了一个还未写成的编译器，它会尽可能地消耗更多的时钟周期，并由一些邪恶公司支付使用费用，以迫使我们购买新的、更快的处理器？像已经写过的答案一样，没有法律限制编译器可以做什么。但是，如果把所有精力都花在识别搜索或排序（等等）上，并“使其变得更糟”，那将是非常愚蠢的。请注意，也没有规定编译器不能为每个“真实”指令引入100个额外指令... ;) - Mats Petersson

Answer 1

C标准实际上没有时间复杂度模型，无论是其原始操作还是库函数。因此编译器可以做几乎任何能保留程序语义(可观察行为)的事情。

C++标准仅对其某些库函数给出复杂性保证，并表示(17.5.1.4[structure.specifications]):

库子句中指定的复杂性要求是上限，提供更好复杂性保证的实现满足这些要求。

编译器应该保持这些边界(由于许多函数是模板化/可能被内联，所以编译器参与其中)，但这些边界是基于容器中元素的数量并限制对比较运算符等的调用次数。否则，编译器再次可以自由地发挥作用。

- Fred Foo

---

这是一个非常好的评论(+1)，但至少对于C++而言，这并不是一个答案，因为它并不涉及库函数，而是用户代码。 - user541686

@ Mehrdad，这个回答实际上是说标准中没有任何禁止编译器降低性能的条款。由于C++标准中提到的该条款是一个例外情况，因此应在答案中提及。因此，上述答案应被理解为：C和C ++标准都不禁止编译器降低用户代码的时间复杂度。 - Klas Lindbäck

@Mehrdad 很多（也许全部）带有时间限制的函数都是模板函数，这将由编译器展开。 - Fred Foo

如果您想了解用户代码的时间复杂度，那么您需要知道用户代码调用库函数的时间复杂度，因此这个答案是正确的。 - gnasher729

复杂度要求仅指定“X 操作的数量”，例如 X = “调用用户的 operator <” 或 X = “调用 std::swap”。 - o11c

Answer 2

代码的性能不被视为可观察行为，因此编译器在性能方面可能会向任何方向进行修改。实际上，出于实现质量（QoI）的原因，编译器不会降低程序的质量，但在某些情况下，QoI与性能无关。

编译器可以根据给定的标志为正在构建的程序添加调试工具（例如，在库实现中使用带检查的迭代器时通常会这样做）。

请注意，编译器会降低程序质量的简单答案有两个方面：当客户要求时，或者实现者不想让用户使用编译器时。

- David Rodríguez - dribeas

Answer 3

C标准中的5.1.2.3节表示:

本国际标准中的语义描述描述了一个抽象机器的行为，其中优化问题不相关。

在C ++标准的1.9 [intro.execution]中有类似的措辞。

两个标准都有相同的可观察行为定义：

符合规范的实现的最小要求是：
— 对易失性对象的访问严格按照抽象机器的规则评估。
— 在程序终止时，写入文件的所有数据都应与根据抽象语义执行程序的结果相同。
— 交互设备的输入和输出动态应按照7.21.3中指定的进行。这些要求的目的是使未缓冲或行缓冲的输出尽快出现，以确保提示消息实际上出现在程序等待输入之前。
这是程序的可观察行为。

因此，其他任何内容（例如for循环的性能或对非易失性变量执行的读取/写入次数）都不被认为是可观察的，因此编译器没有相应的性能要求。

如果编译器想重新评估一个代码块100次（假设它没有可观察的副作用，只改变非易失性变量的状态），并检查每次获得相同的结果（不受宇宙射线或故障硬件影响），则标准允许这样做。

- Jonathan Wakely

---

但是，即使执行所有代码100次（减去副作用），也不会改变时间复杂度。要实现这一点，编译器应该像在循环中构建越来越长的延迟一样做些事情，或者用完全不同的东西（但具有相同的可观察行为）替换编写的代码。无论哪种方式，程序都必须花费越来越多的时间，而没有任何可观察的行为。 - Marc van Leeuwen

无论哪种方式，编译器都可以这样做，因为它具有相同的可观察行为。 - Jonathan Wakely

Answer 4

有人指出，标准并不限制C运行时的工作方式，只限制其可观察行为。例如，你完全可以拥有解释型或JIT编译的C。

考虑一个C实现，其中所有内存单元都存储在底层系统的链表中。指针是该链表中的索引。所有指针操作将像往常一样运行，但运行时必须在每次内存访问时迭代遍历该链表。所有常见算法都会突然增加一个额外的N因子，例如常见的空结束字符串操作。

- pjc50