시간 복잡도

특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간

시간 복잡도란?

사용자에 따라 중요하시는 게 다르기 때문에 속도를 중요시 할 수 있고 메모리 사용량을 중요시 할 수 있다. 일반적으로는 알고리즘의 속도를 성능의 척도로 사용한다. 이를 시간 복잡도라고 부른다.

시간 복잡도는 PC의 성능에 따라 달라지기 때문에 해당 알고리즘의 반복문을 보고 성능을 평가한다.

성능 평가의 기준

• Big-Ω : 최선의 경우, 한 번에 찾는 경우
• Big-O : 최악의 경우, 배열의 길이만큼 시간이 걸리는 경우
• Big-Θ : 평균의 경우, 배열의 길이 절반 만큼 시간이 걸리는 경우

⇒ Big-O와 Big-Θ를 주로 사용하는데 Big-O가 가장 많이 사용된다.

Big-O 표기법

알고리즘의 성능을 평가할 때 쓰이는 것

Big-O 표기법을 사용할 때 3n^2 + 2n + 100 의 성능을 보이는 알고리즘이 있다면 가장 큰 영향을 주는 항인 3n^2 을 표기하는데, 상수는 의미가 없으므로 상수를 제거한 채 n^2 으로 표기한다. 따라서 O(n^2) 이 되는 것이다.

• O(n)알고리즘은 데이터가 많아지면 계산량도 비례해서 많아지므로 선형시간 알고리즘이라고 부른다.
• O(1)알고리즘은 어떤 입력이든 항상 같은 계산량을 보이기 때문에 상수시간 알고리즘이라고 부른다.

P-NP

어떤 문제에 대해 쉬운 문제인지 어려운 문제인지, 해결이 가능하다고 알려졌는지 아닌지를 판단하는 척도

결정 문제

어떤 문제에 대해 Yes 또는 No 로 대답할 수 있는 문제

최적화 문제

어떤 상황에서 최적의 해를 구하는 문제

• Yes 또는 No 로 대답할 수 없고 여러 가지 경로 중 최적의 경로를 추천하는 것 등을 말한다.
• 대부분의 최적화 문제는 결정 문제로 바꿀 수 있다.

결정론적 튜링 머신

현재 상태에서 다음 상태로 이동할 때 다음 상태가 유일하게 결정되는 머신

다음 상태가 유일하게 결정되기 때문에 문제를 일방향으로 해결한다.

if - else 문도 이에 해당한다고 보면 된다. (if 와 else 두 가지로 나뉜다고 생각하지만 사실 한 쪽이 수행되면 한 쪽은 넘어가기 때문이다.)

비 결정론적 튜링 머신

현재 상태에서 다음 상태로 이동할 때 다음 상태가 여러개인 머신

무한한 컴퓨팅 능력이 있다고 가정한 상상의 기계이다.

마치 분신술을 사용해 여러 갈래 길이 나온다면 갔다 돌아오지 않고 자신을 갈래 만큼 더 만들어 이동시킨다.

다항 시간

문제를 해결하는 데 걸리는 시간이 다항식으로 표현할 수 있는 것

다항 시간 내에 문제를 해결할 수 있다는 것은 상수 시간, 로그 시간, 다항 시간 모두를 말하는 것이다.

ex) n^2 + n + 1 ⇒ O(n^2)

상수 시간

문제를 해결하는 데 걸리는 시간이 상수로 표현할 수 있는 것

ex) O(1)

로그 시간

문제를 해결하는 데 걸리는 시간이 로그로 표현할 수 있는 것

ex) O(logn)

지수 시간

문제를 해결하는 데 걸리는 시간이 지수로 표현할 수 있는 것

ex) O(2^n)

지수 시간은 입력이 조금만 커져도 해결하는 시간이 매우 오래 걸린다.

P 문제

결정문제가 주어졌을 때 결정론적 튜링 머신을 사용해 다항 시간 내에 답을 구할 수 있는 문제

NP 문제

결정 문제가 주어졌을 때 비 결정론적 튜링 머신을 사용해 다항 시간 내에 답을 구할 수 있는 문제

다음 상태의 갯수가 유일하지 않다.

결정론적 튜링 머신으로 다항 시간 내에 답을 구할 수 없는 문제이다. ⇒ 지수 시간으로 답을 구할 수 있고 운의 요소가 강하다.

힌트가 주어졌을 때 정답인지 확인하는 것은 다항 시간 내에 가능하다.

모든 P 문제는 NP 문제이다. 모든 P 문제는 비 결정론적 튜링 머신을 사용해 다항 시간 내에 답을 구할 수 있기 때문이다.

🤔 NP-hard 문제

어떤 NP 문제들이 있을 때 이 모든 NP 문제들을 다항 시간 내에 어떤 문제 A로 환원시킬 수 있다면 그 문제 A를 NP-hard 라 칭한다.

• 문제가 해결 가능한지, 불가능한지 알려지지 않은 문제를 말한다. (가장 어려운 문제)

여기서 환원이란 다른 모든 NP 문제를 하나의 문제로 바꿔서 해결할 수 있다면 다른 모든 문제가 해결되는 문제를 말한다. ⇒ 여러 문제가 있는데, 이 중에 하나의 문제가 해결되면 다른 문제들도 쉽게 해결할 수 있는 것이 바로 NP-hard 문제이다.

🤔 NP-complete 문제

NP-hard에 포함되면서 NP 에도 포함되는 문제이다.

• 문제를 해결 할 수 있다고 알려진 문제를 말한다. (해결 가능한 문제 중에서 가장 어려운 문제)

+) 🤔 해밀턴 경로 문제

어떤 연결된 그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 찾는 문제

외판원 최적 버전을 해결하면 자연스럽게 해결할 수 있으므로 외판원 최적 버전으로 환원될 수 있다.