시간복잡도

시간복잡도(time complexity)

가장 널리 사용되는 알고리즘의 수행시간 기준

알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것.

 

기본적인 연산 : 더 작게 쪼갤 수 없는 최소 크기의 연산

 

ex)

• 두 부호 있는 32비트 정수의 사칙연산
• 두 실수형 변수의 대소 비교
• 한 변수에 다른 변수 대입하기

중첩된 반복문의 수행 횟수를 계산 (상수는 대개 무시)

 

시간 복잡도가 높다 = 입력의 크기가 증가할 때 알고리즘 수행시간이 더 빠르게 증가한다
입력 크기가 충분히 작을 때 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다.
= 시간 복잡도는 완전한 속도의 기준은 아니다.

 

입력의 종류에 따라 수행시간이 달라지는 경우 고려하기 위해 최선/최악/평균적인 경우에 대한 수행 시간을 각각 따로 계산한다. 대개는 최악의 수행시간 혹은 수행시간의 기대치를 사용한다

 

O 표기법(Big-O Notation)

주어진 함수에서 가장 빨리 증가하는 항만 남긴 채 나머지를 다 버리는 표기법. 대략적으로 함수의 상한을 나타낸다. 

 

계산복잡도 클래스 : N, NP, NP-완비

계산 복잡도 이론 : 각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는 지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문

 

ex) 

• 정렬문제 : 주어진 N개의 정수를 정렬한 결과는 무엇인가?
• 부분 집합 합(subset sum) 문제 : N개의 수가 있을 때 이 중 몇 개를 골라내서 그들의 합이 S가 되도록 할 수 있는가?

 

계산 복잡도 이론에서 문제의 난이도 : 해당 문제를 해결하는 빠른 알고리즘이 있느냐 ex)다항 시간 알고리즘 이상

 

P(Polynomial) 문제 : 다항 시간 알고리즘이 존재하는 문제들의 집합 ex) 정렬문제

계산 복잡도 클래스(complexity class) : P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합

NP(non-Polynomial) 문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제 ex) 집합 합 문제

NP(non-Polynomial)은 다항 시간 알고리즘이 존재하지 않는 문제들의 집합이 아님. 계산 복잡도 이론에서 두 문제의 난이도를 비교하기 위해 환산(reduction) 기법을 사용함 

환산(reduction) 기법 : 한 문제를 다른 문제로 바꿔서 푸는 기법 

SAT 문제(Satisfiability Problem) : 어려운 문제의 기준이 되는 문제. NP문제 이상으로 어렵다

NP-난해(NP-Hard) 문제 : SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다. 즉, 아주 어려워서 아무도 다항 시간에 푸는 방법을 발견하지 못한 문제

NP-완비(NP-Complete) 문제 : NP-난해 문제이면서 NP인 문제들 ex) 부분 집합 합 문제