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

Question

_{(注意:这是一个 language-lawyer 问题；我不是指任何特定的现有编译器。)}

何时允许编译器降低程序的时间复杂度？
在什么情况下(如果有的话)这被认为是“可观察的行为”，为什么？
(例如，编译器可以合法地将多项式时间程序“减少”为指数时间程序吗？)

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

Answer 1

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

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

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

编译器更好地保留这些界限(并且由于许多函数是模板化的/可能是内联的，因此涉及编译器)，但界限是根据容器中元素的数量并限制比较调用的数量运营商之类的。否则，编译器又可以为所欲为。