지수 시간 알고리즘

1. 조심해야 할 징후가 있지만이 질문에 대한 쉬운 답은 없습니다. . 예를 들어, 집합의 가능한 모든 하위 집합을 검사하는 것은 기하 급수적입니다. 따라서 정수 집합이 $ \ {x_1, …, x_n \} $이고 이들의 모든 하위 집합을 확인하여 합계가 있는지 확인하려면 $ 0 $까지 정확히 $ 2 ^ n $ 서브 세트를 고려해야하므로이 방법은 지수 시간이됩니다. 여러 가지 다른 트랩이 알고리즘을 지수 시간으로 만들 수 있으므로 광범위한 범주를 찾는 것보다 사례별로 알고리즘을 분석하십시오.

2. 알고리즘이 완료하는 데 $ n ^ 2 $ 단계가 걸리면 다항식입니다. $ 2 ^ n $ 단계가 필요하면 지수입니다. 차이점은 $ n $의 위치입니다. $ n > 1 $, $ m > 0 $에 대해 $ O (n ^ m) $이면 고정 $ m $의 경우 $ n $의 다항식이지만 고정 $ n $의 경우 $ m $의 지수입니다.

댓글

• 주의하십시오. $ n ^ m $ 함수는 ' $ m $가 상수가 아닌 경우 $ n $에서 다항식이 아닙니다. 그리고 $ m $ 가 상수이지만 ' 함수가 해당 상수에서 지수 적이라고 말하는 것은 의미가 없습니다.
• 예, 당신은 ' 맞습니다. ' 명확하게 설명하겠습니다.

문제를 고려하고 전체 검색 공간을 열거 할 때 기하 급수적 인 시간 무차별 대입 알고리즘을받는 경우가 많습니다. 일반적으로 하위 집합 문제를 생각합니다 (SAT에서는 다음 중 하위 집합을 선택합니다. true로 설정된 변수), 순열 문제 (TSP에서 모든 여행은 도시의 순열) 및 파티션 문제 (그래프 색상에서는 p 정점을 색상 클래스로 아티 션). 또는 정렬을 고려하십시오 : $ n $ 정수의 $ n! $ 순열이 있습니다. 모든 순열을 살펴보고 정렬되었는지 확인하십시오. 어리 석고 느리지 만 작동합니다.

댓글

• $ O (n!) $가 $ O ( k ^ n) $. ' 여전히 시간 복잡성에 대해 배우고 자하는 경우,이를 증명하는 데 유용한 정보가 될 수 있습니다.