컴파일러가 프로그램의 시간 복잡성을 저하시키는 것이 합법입니까?이것이 관찰 가능한 행동으로 간주됩니까?

컴파일러가 프로그램의 시간 복잡성을 저하시키는 것이 합법입니까?이것이 관찰 가능한 행동으로 간주됩니까?

_{(참고: 이 질문은 언어 변호사의 질문입니다. 기존의 특정 컴파일러를 지칭하는 것이 아닙니다.)}

컴파일러가 프로그램의 시간 복잡성을 저하시킬 수 있는 경우는 언제입니까?
어떤 상황(있는 경우)에서 이것이 "관찰 가능한 행동"으로 간주되며, 그 이유는 무엇입니까?
(예를 들어, 컴파일러는 다항식 시간 프로그램을 지수 시간 프로그램으로 합법적으로 "줄일" 수 있습니까?)

답이 C와 C++, 또는 두 가지 버전이 다르면 차이점을 설명해주세요.

C 표준은 실제로 원시 연산이나 라이브러리 함수에 대한 시간 복잡도 모델을 가지고 있지 않으므로 컴파일러는 프로그램 의미론(관찰 가능한 동작)을 보존하는 거의 모든 작업을 수행할 수 있습니다.

C++ 표준은 일부 라이브러리 함수에 대해서만 복잡성을 보장하며 (17.5.1.4 [structure.specifications]) 다음과 같이 말합니다.

라이브러리 절에 지정된 복잡성 요구사항은 상한이며, 더 나은 복잡성 보장을 제공하는 구현은 요구사항을 충족합니다.

컴파일러는 이러한 경계를 더 잘 보존하지만(그리고 많은 함수가 템플릿화/인라인화될 수 있기 때문에 컴파일러가 관여합니다), 경계는 컨테이너의 요소 수 측면에서이며 비교 연산자 등에 대한 호출 수를 제한합니다.그렇지 않으면 컴파일러는 다시 자유롭게 원하는 대로 할 수 있습니다.

코드의 성능은 관찰 가능한 동작으로 간주되지 않으며 컴파일러가 어느 방향으로든 수정할 수 있습니다.실제적으로 컴파일러가 구현 품질(QoI)의 이유로 프로그램을 저하시키지는 않지만 QoI가 성능을 저하시키는 경우가 있습니다.

컴파일러가 적절한 플래그를 지정하면 디버깅 목적으로 빌드 중인 프로그램에 계측기를 추가할 수 있습니다(예: 체크된 반복기와 같은 라이브러리 구현에서 종종 해당됨).

컴파일러가 프로그램을 저하시킬 때에 대한 간단한 대답은 클라이언트가 프로그램을 요청할 때 또는 구현자가 컴파일러에 대한 사용자를 원하지 않을 때 두 가지입니다.

C 표준의 5.1.2.3은 다음과 같습니다.

이 국제 표준의 의미론적 설명은 최적화 문제가 무관한 추상 기계의 동작을 설명합니다.

C++ 표준은 1.9 [intro.execution]에서 유사한 문구를 사용합니다.

두 표준 모두 관찰 가능한 행동에 대한 정의가 동일합니다.

적합한 구현에 대한 최소 요구사항은 다음과 같습니다.
휘발성 개체에 대한 액세스는 추상 시스템의 규칙에 따라 엄격하게 평가됩니다.
프로그램 종료 시, 파일에 기록된 모든 데이터는 추상적 의미론에 따른 프로그램 실행 결과와 동일해야 합니다.
대화형 장치의 입력 및 출력 역학은 7.21.3에 명시된 대로 발생해야 합니다.이러한 요구 사항의 목적은 버퍼링되지 않은 출력 또는 라인 버퍼링된 출력이 가능한 한 빨리 나타나 프로그램이 입력을 대기하기 전에 실제로 메시지가 나타나도록 하는 것입니다.
이것은 프로그램의 관찰 가능한 동작입니다.

다른 를 들어 a 래서다모것든, 른들어성, 능를예그의 .for루프 또는 비휘발성 변수에 대해 수행된 읽기/쓰기 수는 관찰 가능한 것으로 간주되지 않으므로 컴파일러에 해당하는 성능 요구 사항이 없습니다.

컴파일러가 코드 블록을 100번 재평가하고(관찰 가능한 부작용이 없다고 가정하고 비휘발성 변수의 상태만 변경) 매번 동일한 결과를 얻었는지(우주선이나 결함 있는 하드웨어의 영향을 받지 않음) 확인하려면 표준에 의해 허용됩니다.

다른 사람들은 표준이 C 런타임이 작동하는 방식을 제한하지 않고 관찰 가능한 동작만 제한한다고 지적했습니다.예를 들어, 당신이 C를 해석하거나 JIT로 컴파일하지 못할 이유가 없습니다.

모든 메모리 셀이 일부 기본 시스템의 연결된 목록에 저장되는 C 구현을 생각해 보십시오.그러면 포인터가 이 연결된 목록의 인덱스가 됩니다.런타임이 모든 메모리 액세스에 대한 연결된 목록을 반복해야 하는 경우를 제외하고 모든 포인터 작업은 정상적으로 작동합니다.모든 종류의 공통 알고리즘은 일반적인 null-terminated 문자열 연산과 같이 복잡성에서 N의 추가 계수를 갑자기 얻을 수 있습니다.

언급URL : https://stackoverflow.com/questions/26230791/is-it-legal-for-the-compiler-to-degrade-the-time-complexity-of-a-program-is-thi