编译器降低程序的时间复杂度合法吗?是否认为这是可观察到的行为? [英] Is it legal for the compiler to degrade the time complexity of a program? Is this considered observable behavior?

问题描述

_{(注意:这旨在成为语言律师问题；我不是指任何现有的特定编译器.)}

_{(Note: This is intended to be a language-lawyer question; I'm not referring to any particular existing compilers.)}

何时允许编译器降低程序的时间复杂度?
在什么情况下(如果有)被视为可观察到的行为"，为什么?
(例如，编译器可以合法地将多项式时间程序简化"为指数时间程序吗?)

When, if ever, is the compiler allowed to degrade the time complexity of a program?
Under what circumstances (if any) is this considered "observable behavior", and why?
(For example, can the compiler legally "reduce" a polynomial-time program to an exponential-time one?)

如果答案在C和C ++或两者的不同版本中有所不同，请说明不同之处.

If the answer differs in C and C++, or in different versions of either, then please explain the differences.

推荐答案

C标准实际上没有时间复杂度模型，无论是其原始操作还是库函数都没有，因此允许编译器执行几乎所有操作保留程序语义(可观察到的行为).

The C standard doesn't actually have a time complexity model, neither for its primitive operations, nor its library functions, so compilers are allowed to do pretty much anything that preserves program semantics (observable behavior).

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

The C++ standard only gives complexity guarantees only for some its library functions, and says (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.

编译器可以更好地保留这些界限(并且由于许多函数是模板化的/可以被内联，因此涉及到编译器)，但是界限取决于容器中元素的数量，并限制了进行比较的调用的数量运营商之类的.否则，编译器可以再次自由进行操作.

A compiler better preserve these bounds (and since many of the functions are templated/may be inlined, the compiler is involved), but the bounds are in terms of the number of elements in containers and restrict the number of calls to comparison operators and the like. Otherwise, the compiler is again free to do as it pleases.

这篇关于编译器降低程序的时间复杂度合法吗?是否认为这是可观察到的行为?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！