编译器降低程序的时间复杂性是否合法？ 这是否被认为是可观察的行为？
（ 注：这是一个语言律师的问题;我不是指任何特定的现有编译器。 ）
如果有的话，是否允许编译器降低程序的时间复杂度？
在什么情况下（如果有的话），这被认为是“可观察到的行为”，为什么呢？
（例如，编译器能否合法地将多项式时间程序“缩减”到指数时间程序？）
如果答案在C和C ++中或在不同的版本中有所不同，请解释它们之间的差异。
C标准实际上并没有时间复杂度模型，既不是基本的操作，也不是它的库函数，所以编译器可以做任何保留程序语义（可观察行为）的东西。
C ++标准只给出一些库函数的复杂性保证，并且说（17.5.1.4 [structure.specifications]）：
库子句中指定的复杂性要求是上限，而提供更好复杂性保证的实现满足要求。
编译器可以更好地保留这些边界（因为许多函数都是模板化的/可以被内联，编译器也会涉及到），但是边界是根据容器中元素的数量和限制比较运算符的调用次数以及喜欢。 否则，编译器可以随心所欲地执行。
代码的性能不被视为可观察的行为，并可能被编译器在任一方向上修改。 实际上，对于实施质量 （QoI）原因，编译器不会降低您的程序，但有些情况下QoI不是性能。
一个编译器，给定适当的标志，可以添加检测程序，为了debugging的目的（在库实现中通常是这种情况，例如使用检查迭代器）。
请注意，编译器降级程序的简单答案是双重的：客户端请求时，或者实现者不希望编译器有用户时。
5.1.2.3在C标准中说
本国际标准中的语义描述描述了优化问题无关的抽象机器的行为。
C ++标准在1.9 [intro.execution]
两个标准都具有相同的可观察行为的定义：
符合实现的最低要求是：
– 对易失性对象的访问严格按照抽象机器的规则进行评估。
– 程序终止时，写入文件的所有数据应与根据抽象语义执行程序所产生的结果相同。
– 交互设备的input和输出dynamic应按照7.21.3的规定进行。 这些要求的意图是尽可能快地出现无缓冲或线路缓冲输出，以确保提示消息实际上出现在等待input的程序之前。
这是该程序的可观察行为 。
因此，其他任何事情，例如for循环的执行，或者对非易失性variables所做的读/写次数都不被认为是可观察的，所以在编译器上没有相应的性能要求。
如果编译器想要重新评估一个代码块100次（假设它没有可观察的副作用，只改变非易失性variables的状态），并检查每次获得相同的结果（并且不受宇宙的影响射线或错误的硬件），这是标准允许的。
其他人指出，这个标准并没有限制C运行时的工作方式，只是它的可观察行为。 例如，没有理由不解释或JIT编译C语言。
考虑一个C实现，其中所有内存单元存储在某个底层系统的链表中。 指针是这个链表的索引。 所有的指针操作都可以正常工作，除非运行时需要遍历每个内存访问上的链表。 各种常见algorithm会突然获得复杂度为N的额外因子，例如常见的以null结尾的string操作。
