다항 시간 (polynomial time)

다항 시간 (polynomial time)

• 다항 시간(polynomial time) 은 계산 복잡도 이론에서 문제를 해결하는 데 필요한 계산 시간이 입력 크기(n)의 다항식 함수로 표현될 수 있는 경우 를 의미합니다.

1. 정의

• 다항 시간이란, 알고리즘이 입력 크기 에 대해 최대 의 시간이 걸리는 경우를 말합니다.
  • 여기서 는 상수입니다.
  • 예를 들어 와 같은 시간 복잡도를 가진 알고리즘은 다항 시간입니다.

2. 표현 방식

• 빅오 표기법(Big-O notation) 으로 시간 복잡도를 나타냅니다.

• 다항 시간의 예:

  • : 상수 시간
  • : 로그 시간
  • : 선형 시간
  • : 이차 시간
  • : 삼차 시간

• 다항 시간이 아닌 예:

  • : 지수 시간 (exponential time)
  • : 팩토리얼(!) 시간

---

3. 의의

• 다항 시간 알고리즘은 효율적(tractable) 이라고 간주됩니다.
• 문제를 해결하는 데 필요한 시간이 다항 시간 내에 해결 가능하다면, 현실적인 계산 자원으로 처리할 가능성이 높다고 봅니다.

---

4. 예시

다항 시간 알고리즘:

• 버블 정렬 :
• 이진 탐색 :
• 최단 경로 알고리즘(Dijkstra) : (단순 구현 시)

다항 시간이 아닌 알고리즘:

• 외판원 문제(TSP) : (브루트 포스 탐색)
• SAT 문제 (모든 경우의 수 탐색 시) :

---

5. P 클래스와의 관계

• P 클래스 는 다항 시간 안에 문제를 해결할 수 있는 모든 결정 문제의 집합을 의미합니다.
  • 즉, P 클래스의 문제들은 다항 시간 내에 풀 수 있는 문제들입니다.

---

6. 요약

• 다항 시간은 형태로 입력 크기 에 따라 증가하는 계산 시간을 의미하며, 계산 복잡도 이론에서 효율적 으로 문제를 해결할 수 있는 기준으로 사용됩니다.
• 현실에서 다룰 수 있는 문제를 구분하는 중요한 기준으로, 다항 시간 알고리즘을 갖는 문제는 일반적으로 효율적으로 풀 수 있는 문제로 간주됩니다.

view raw polynomial.time.ko.md hosted with ❤ by GitHub