Wolfram 언어

점근 관계를 사용한 알고리즘 비교

계산상의 복잡성에서 알고리즘은 대규모 입력(보통 무한대로 간주)에 대한 동작에 따라 분류됩니다. 두 알고리즘은 하나의 런타임이 AsymptoticLessEqual (big ), AsymptoticLess (little ), AsymptoticGreaterEqual (big ) 혹은 AsymptoticGreater (little ) 중 어느 하나에 의해 비교됩니다.

외판원 문제(TSP)는 개의 도시를 잇는 최단 거리를 구하는 것입니다. 간단한 알고리즘은 가지 경로를 모두 시험해 보는 것입니다. HeldKarp 알고리즘은 이를 향상시켜 약 단계로 한 것입니다. 을 나타내는 HeldKarp 알고리즘이 더 빠른 것을 알 수 있습니다

두 알고리즘 모두 외판원 문제의 복잡도 클래스가 시간 로 풀 수 있는 문제의 EXPTIME 만큼 나쁘지 않다는 것을 나타냅니다. 예를 들어 임의의 에서 이므로, HeldKarp 알고리즘은 지수적 런타임을 가집니다.

계승 함수의 경우 이므로 선형 지수는 불충분합니다.

그러나 이므로 계승 함수는 여전히 지수적 런타임을 가집니다.

근사해는 의 시간에서 발견되기 때문에 비슷한 외판원 문제는 다항식 시간에서 풀 수 있는 문제인 복잡도 종류 P입니다. 어떤 다항식 알고리즘도 지수 알고리즘 보다 빠릅니다.

관련 예제

de en es fr ja pt-br zh