계산 복잡도 이론

계산 복잡도 이론

- 주어진 문제를 풀기 위해 계산 과정에 필요한 자원을 다루는 계산 이론의 일부

 

자원의 종류

- 시간 : 문제를 풀기 위해 얼마나 많은 단계를 거치는가

- 공간 : 문제를 풀기 위해 얼마나 많은 메모리가 필요한가

- 이외 : 얼마나 많은 병렬 프로세서가 필요한가 등

 

 

 

하나의 문제

- 관련 질문들의 전체 집합. 질문은 유한 길이의 문자열

 

계산 이론의 인스턴스

- 인스턴스 : 어느 특별한 질문

 

인스턴스의 예시

- "15의 인수를 해라"

 

 

 

 

 

시간 복잡도 time complexity

- 가장 효율적인(bit로 측정) 알고리즘으로 한 문제의 인스턴스를 푸는데 걸리는 단계 수

 

 

시간 복잡도의 예시

- n 비트 길이의 인스턴스가 n^2 단계 내에 풀린다면 n^2의 시간복잡도를 가짐

 -> 빅오 표기법 : 최악의 경우 시간 복잡도 -> O(n^2)

- 잡초 깍기는 두배의 면적을 깍는데 두배의 시간이 걸린다 -> 선형 복잡도

- 사전에 어떤것을 찾을때 두배 크기의 사전을 한번더 열어봐야한다. -> 지수 복잡도

 

 

 

 

 

P 문제와 NP 문제

- P 문제 (polynomial, 다항식) : 알고리즘의 속도가 다항식으로 표현되는 문제

- NP 문제 (nondeterministic polynomial, 비결정 다항식) : 다항식으로 표현될수 있는지 알려지지 않은 문제

=> P 문제는 컴퓨터로 적당한 시간내 해결가능한 쉬운 문제, NP는 어려운 문제

 

 

NP hard와 NP 완전 문제(NP complete)

- NP-hard : 모든 경우의 수를 확인해보는 방법 이외에는 정확한 답을 구할수 있는 방법이 없는 문제

- NP-complete : NP-hard 이면서 다항식 시간으로 표현될수 있는지 알려지지않은 문제