하자
이 될 크기의 입력에 문제시 실행되는 최악의 경우
. 우리는이 문제 고정함으로써 조금 이상한합시다
에 대한
이지만
에 대한
.
-
그렇다면 문제의 하한은 무엇입니까? 내가 이해 한 방식은 하한입니다
. 그러나 우리는
가 상수
, 이 존재
하여 모든
, 가 존재 함을 의미하며
, 이는 사실이 아닙니다. 따라서 우리는 오직 f ( n ) = Ω ( n ) 이라고 말할 수있는 것 같습니다
. 그러나 일반적으로 문제의 하한이
.
-
라고 가정
, 정수가 있는지 수단
,
이되도록 모든
,
. 또한 문제가 실행 시간 이라고 가정하자
. 우리는 모든 소수를 위해이 문제를 줄일 수있는 경우
(동일한 입력 크기) 또 다른 문제로, 우리는 다른 문제의 실행 시간이 낮기의 결합 말할 수
?
답변
의 올바른 정의는 이 존재 하여 무한히 많은 , 입니다. 하한에 대한 무한 정의는 문제를 처리하고 실제로 사용하는 방식입니다.k > 0 n f ( n ) ≥ k n 2
나는 2005 년에이 글 을 올렸습니다.
일부 교과서는이 정의를 올바르게 얻지 만 일부는 그렇지 않습니다.
답변
로 크 누스 의 정의 만 주장 할 수 . 알다시피, 이것은 직관적이지 않으며 Vitányi 및 Meertens 함수 “wild”에 대해 발생합니다 . 그들은 정의를 제안합니다
(이것은 Lance의 정의와 동일합니다.)이 정의로 .
답변
나는 가장 널리 사용되는 것을 알지 못하지만 (가장 컴퓨터 과학을위한) 가장 오래된 사용법을 알고 있다고 생각합니다.
Hartmanis & Stearns의 “1965 년 계산 알고리즘의 복잡성”에서 Corollary 2.1은 다음과 같습니다.
경우 및 T는 시간 기능이되도록 INF N → ∞ T ( N )
,SU⊆ST
여기서 에서 계산 가능한 모든 문제의 복잡도 종류 인 O ( K ( n은 ) ) . T (n)은 일부 정수 k 와 모든 n 및 T ( n ) ≤ T ( n + 1 )에 대해 T ( n ) ≥ n / k 를 준수해야 하지만 시간을 구성 할 필요는 없습니다.
함수는 대한 첫 번째 규칙을 따르지만 두 번째 규칙을 따르지 않습니다.
Corollary 2.2는 위의 역수이며 한계 최고를 사용하지만 여전히 이러한 요구 사항이 있습니다. 알고리즘이 수년에 걸쳐 복잡 해짐에 따라 요구 사항이 완화되었을 수 있습니다.
답변
두 가지를 구별해야한다고 생각합니다.
- 함수의 하한
- 문제에 대한 하한 (알고리즘)
함수의 경우, 순서를 고칠 때 하한 / 상한 의 정의가 뒤 따릅니다. 순서 관계가 점근 적 전공 인 경우 (상수 요인 무시)
정의는 와 Ω 의 일반적인 정의입니다 . 둘 다 조합과 같은 다른 영역에서 광범위하게 사용됩니다.
그러나 문제 (알고리즘)에 대한 하한에 대해 이야기 할 때, 실제로 말하고 싶은 것은 문제를 해결하기 위해 알고리즘을 실행하기 위해 특정 양의 자원이 필요하다는 것입니다. 복잡성 클래스는 종종 와 같은 함수에 의해 매개 변수화되며 , 우리는 문제가 함수에 의해 하 한계라고 간단하게 말하지만 이는 멋진 함수에 대해서만 작동합니다 (예 : 알고리즘의 실행 시간은 모노톤 등). 우리가 이러한 경우에 말하고 싶은 것은 우리가 필요로하는 것입니다 n은 2 보다, 즉 적은 문제를 해결하기 위해 시간을 실행 N 2
실행 시간이 충분하지 않아 알고리즘의 실행 시간이 이 아니라는 Lance의 정의가됩니다 .