점근법 최적 알고리즘
Asymptotically optimal algorithm | 이 글은 검증을 위해 인용구가 추가로 필요하다.– · · 책· · (2008년 10월)(이 |
컴퓨터 과학에서 알고리즘은, 대략적으로 말하면, 큰 입력의 경우, 가능한 최선의 알고리즘보다 더 나쁜 상수 인자(입력 크기에 관계 없이)를 최악의 경우, 점증적으로 최적이라고 한다.빅O 표기법을 널리 사용한 결과 컴퓨터 과학 연구에서 흔히 접하게 되는 용어다.
보다 공식적으로, 특정 자원의 Ω(f(n)이 필요한 것으로 문제가 입증되고, 알고리즘이 O(f)만 사용하는 것으로 입증된 경우, 알고리즘은 특정 자원에 대해 점증적으로 최적이다.
이러한 증명에는 특정 연산 모델의 가정, 즉 입력 데이터로 허용 가능한 작동에 대한 특정 제약이 필요하다.
간단한 예로, 모든 비교 분류는 평균과 최악의 경우 최소 Ω(n log n)의 비교가 필요한 것으로 알려져 있다.Mergesort와 Hapsort는 O(n log n) 비교를 수행하는 비교 분류기 때문에 이러한 의미에서 점증적으로 최적이다.
입력 데이터에 비교 외에도 알고리즘 구성 시 악용될 수 있는 priori 속성이 있는 경우, 점증적으로 더 빠른 알고리즘이 가능할 수 있다.예를 들어, N 개체가 [1, N] 범위의 정수라고 알려진 경우, 버킷 정렬 등에 의해 O(N) 시간을 정렬할 수 있다.
알고리즘이 점증적으로 최적화된 결과, 충분한 입력의 경우 어떤 알고리즘도 이를 상수 인자 이상으로 능가할 수 없다.이러한 이유로, 무증상적으로 최적의 알고리즘은 종종 연구에서의 "선 끝"으로 보여지는데, 이는 극적으로 개선할 수 없는 결과의 달성이다.반대로 알고리즘이 무증상 최적 상태가 아닌 경우, 이는 입력 크기가 커질수록 알고리즘은 가능한 최고의 알고리즘보다 점점 더 나쁜 성능을 발휘한다는 것을 의미한다.
실제로, 그들이 어떠한 점증적 이점을 누리지 않더라도, 더 나은 성과를 내는 알고리즘을 찾는 것이 유용하다.또한 새로운 알고리즘은 특정 입력에 대한 성능 향상, 자원 사용 감소 또는 기술 및 구현이 더 간단해지는 등의 이점을 제공할 수 있다.따라서 무증상 최적 알고리즘이 항상 "선의 끝"은 아니다.
무증상 최적 알고리즘은 중요한 이론적 결과지만, 무증상 최적 알고리즘은 여러 실제 상황에서 사용되지 않을 수 있다.
- 그것은 어떤 컴퓨터 저장 시스템에 들어갈 수 있는 것보다 더 많은 비트를 가진 입력과 같이 실제 입력 크기의 범위를 넘어서서 n에 대해 더 흔히 사용되는 방법만을 능가한다.
- 그것은 너무 복잡하기 때문에 그것을 정확히 이해하고 구현하는 것이 고려 중인 입력 크기 범위에서 그것의 잠재적인 이익을 능가한다.
- 실무에서 접하는 입력은 보다 효율적인 알고리즘을 가지거나 최악의 경우로 인한 경험적 접근 알고리즘이 효율적으로 해결할 수 있는 특수한 경우에 해당된다.
- 현대의 컴퓨터에서 메모리 캐시 및 병렬 처리와 같은 하드웨어 최적화는 점증적으로 최적의 알고리즘에 의해 "파손"될 수 있다(해석이 이러한 하드웨어 최적화를 고려하지 않았다고 가정).이 경우 이러한 기능을 더 잘 활용하고 실제 데이터에 대한 최적의 알고리즘을 능가하는 차선의 알고리즘이 있을 수 있다.
실제에 사용되지 않은 점증상 최적 알고리즘의 예로는 간단한 다각형의 삼각 측정에 대한 베르나르 샤젤의 선형 시간 알고리즘이 있다.또 다른 것은 "최적 시간과 공간의 크기 조정 가능한 배열"[1]에 게재된 배열 데이터 구조로 일정 시간 인덱싱이 가능하지만 많은 기계에서 일반적인 배열 인덱싱에 비해 실질적인 패널티가 많이 발생한다.
형식 정의
공식적으로, 문제가 n 크기의 인스턴스(입력)에 대해 해결하는데 Ω(f(n) 시간이 필요하다는 것을 보여주는 하한 정리가 있다고 가정한다(Ω의 정의는 big-O 표기법 참조).그러면 O(f(n) 시간 내에 문제를 해결하는 알고리즘이 점증적으로 최적이라고 한다.이것은 또한 한계치를 사용하여 표현할 수 있다: b(n)가 실행 시간의 하한이며, 주어진 알고리즘은 t(n) 시간이 걸린다고 가정한다.그 후 알고리즘은 다음과 같은 경우에 점증적으로 최적이다.
이 한계는 존재하는 경우 t(n) ≥ b(n)로 항상 1 이상이다.
일반적으로 시간 효율성에 적용되지만 알고리즘은 점증적으로 최적의 공간, 랜덤 비트, 프로세서 수 또는 일반적으로 빅-O 표기법을 사용하여 측정한 다른 리소스를 사용한다고 말할 수 있다.
때때로 모호하거나 암묵적인 가정은 알고리즘이 무증상 최적인지 불분명하게 만들 수 있다.예를 들어, 하한정리는 비교 분류의 경우처럼 특정한 추상적인 기계 모델이나 특정한 기억의 조직을 가정할 수 있다.이러한 가정을 위반함으로써, 새로운 알고리즘은 잠재적으로 하한과 "비법적으로 최적" 알고리즘을 능가할 수 있다.
스피드업
무증상 최적 알고리즘의 비증상성을 스피드업이라고 한다.블럼의 스피드 업 정리는 스피드 업에 인위적으로 구성된 문제가 존재한다는 것을 보여준다.그러나 오늘날 가장 잘 알려진 많은 알고리즘이 무증상 최적인지 아닌지는 공공연한 문제다.예를 들어 최소 스패닝 트리를 찾기 위한 O(nα) 알고리즘이 있는데 여기서 α(n)는 아커만 함수의 매우 느리게 성장하는 역이지만 가장 잘 알려진 하한은 사소한 Ω(n)이다.이 알고리즘이 무증상 최적인지는 알 수 없으며, 어느 쪽으로든 해결된다면 중요한 결과로 환영받을 수 있을 것이다.코퍼스미스와 위노그라드(1982)는 제한된 알고리즘 클래스(람다컴퓨팅이 있는 스트라센형 이선형 아이덴티티) 사이에서 매트릭스 곱셈이 약한 형태의 스피드 업을 가지고 있다는 것을 증명했다.
참고 항목
참조
- ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo
