알고리즘의 효율성을 분석하는 두 가지 방법은
- 런타임에 점근 적 상한을 설정하고
- 그것을 실행하고 실험 데이터를 수집합니다.
(1)과 (2) 사이에 상당한 간격 이있는 경우가 있는지 궁금합니다 . 이것은 (a) 실험 데이터가 더 엄격한 점근선을 제안하거나 (b) 알고리즘 X와 Y가있어 이론적 분석에서 X가 Y보다 훨씬 우수하고 실험 데이터가 Y보다 훨씬 우수하다는 것을 나타냅니다. 엑스.
실험은 일반적으로 평균 사례 행동을 나타 내기 때문에 가장 흥미로운 답변은 평균 사례 상한을 참조 할 것으로 기대합니다. 그러나 Simplex에 대한 Noam의 답변과 같이 다른 범위에 대해 흥미로운 답변을 배제하고 싶지 않습니다.
데이터 구조를 포함하십시오. 답변 당 하나의 algo / ds를 입력하십시오.
답변
가장 눈에 띄는 예는 물론 실제로는 빠르게 실행되어 다중 시간을 제안하지만 이론적으로는 지수 시간이 걸리는 Simplex 방법입니다. Dan Spielman은이 수수께끼를 설명해 준 Nevanlinna 상을 수상했습니다.
더 일반적으로, 많은 정수 프로그래밍 프로그래밍 인스턴스는 표준 IP 솔버를 사용하여 상당히 잘 해결할 수 있습니다 . /teaching/cgt/combinatorial-auctions-survey.pdf
답변
그 로브 너 기지 . 최악의 경우의 실행 시간은 변수의 수에 따라 이중 지수입니다. 그러나 실제로는 특히 체계적인 문제의 경우 F4 및 F5 알고리즘이 효과적입니다 (즉, 매우 빠르게 종료). 평균 또는 예상 실행 시간에 대한 적절한 추측이 무엇인지 알아내는 것이 여전히 활발한 연구 영역입니다. 그것은 그것이 어떻게 든 근본적인 이상의 뉴턴 폴리 토프의 부피와 관련이 있다고 추측된다.
답변
이 현상의 크고 작은 인식 된 예는 그래프 동형 입니다. 가장 잘 알려진 알고리즘은 시간과 비슷하지만 실제로 그래프 동 형사상은 매우 빠르게 풀리는 경향이 있습니다.
평균 / 부드러운 문제의 복잡성에 대한 공식적인 결과가 있는지는 모르지만, 하나가 존재한다는 것을 기억합니다. 어쩌면 다른 누군가가 공식적인 결과를 지적하는 데 차임이있을 수 있습니다. 확실히 많은 실험적 증거와 많은 빠른 솔버가 있습니다. 이 속성이 GI 완성 가족의 다른 구성원에게도 적용되는지 궁금합니다.
답변
데이비드 존슨 (David Johnson)으로부터 이론적 대 실험적 근사 비율의 차이 :
Traveling Salesman Problem : 지역 최적화 사례 연구, DS Johnson 및 LA McGeoch . 이 논문에서 그들은 이론적 인 무증상을 무시하는 무증상의 실험적 증거 (실험이 N = 10,000,000까지 실행 됨)를 제시합니다 : Jon Bentley의 “Greedy”또는 “Multi-Fragment”알고리즘 (최소 logN / loglogN)은 Nearest Insertion과 Double MST보다 뛰어납니다. 둘 다 최악의 근사치 비율이 2입니다.
답변
최근까지 잘 알려지지 않은 또 다른 예는 Lloyd의 k- 평균 알고리즘의 실행 시간입니다 (실제적인 관점에서 볼 때 50 년 이상 선택한 클러스터링 알고리즘 임). 최근에야 2009 년 Vattani 에 의해 최악의 경우 Lloyd의 알고리즘은 입력 포인트 수에 기하 급수적으로 많은 반복이 필요 하다는 것이 입증되었습니다 . 반면에, 부드럽게 분석 ( Arthur, Manthey 및 Röglin )은 반복 횟수가 다항식임을 입증하여 경험적 성능을 설명했습니다.
답변
스플레이 트리에 대한 역동적 최적 성 추측 의 순회, deque 및 split 결과 는 그러한 차이의 예입니다. 실험은 선형 시간에 대한 주장을 뒷받침하지만 알려진 증거는 없습니다.
답변
질문에 약간의 문제가 있습니다. 실제로 알고리즘 분석에는 두 가지 이상의 방법이 있으며, 무시 된 이론적 방법 중 하나는 최악의 런타임보다는 예상 런타임입니다. 실제로이 평균적인 사례 행동은 실험 수행과 관련이 있습니다. 다음은 매우 간단한 예입니다. 크기 n의 입력에 대한 알고리즘이 있다고 가정합니다. 시간 n ^ 2가 걸리는 각 길이의 특정 입력 하나를 제외하고 크기 n의 가능한 모든 입력에 대해 시간 n이 걸립니다. 최악의 경우 실행 시간이 지수라고 들리지만 평균 사례는 [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n-(n-1) / 2 ^ n입니다. n으로 제한합니다. 분명히 두 가지 유형의 분석은 매우 다른 답변을 제공하지만, 다른 수량을 계산할 때 예상됩니다.
실험을 여러 번 실행하면 샘플에 대해 가장 긴 실행 시간이 걸리더라도 가능한 입력 공간의 작은 부분 만 샘플링하므로 하드 인스턴스가 드물면 누락 될 수 있습니다. .
첫 번째 n / 2 비트가 모두 0이면 마지막 n / 2 비트로 인코딩 된 3SAT 인스턴스를 해결하는 것보다 이러한 문제를 구성하는 것이 비교적 쉽습니다. 그렇지 않으면 거절하십시오. n이 커질수록 문제는 평균 실행 시간이 매우 낮다는 3SAT의 가장 효율적인 알고리즘과 최악의 경우 런타임이 거의 같습니다.