SEB Section 3 Time Complexity

알고리즘을 풀다 보면 시간이 초과 됐다는 에러를 만날 수 있다. 이 에러는 너무나 많은 동작을 하여 런타임이 초과 되었다는 에러이다. 결국 효율적이지 못하다 라는 말과 같다. 이 에러를 해결하기 위해선 시간복잡도와 Big-O 표기법을 알아야 한다.

시간 복잡도

시간 복잡도의 말만 보면 시간이 얼마나 복잡하게 걸리는가 에 대한 것이다. 이는 입력값이 커짐에 따라 증가하는 시간의 비율을 의미한다. 그렇다면 알고리즘에서의 시간복잡도란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성 해야 한다는 것이다.

Big-O 표기법

시간복잡도를 표기하는 방법은 다음과 같은 표기법이 있다.

• Big-O
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

각각 최악, 최선, 평균의 경우에 대해 나타내는 방법이다. 하지만 우리는 최악만 고려하는데, 그 이유는 최악의 경우의 수 까지 갈 경우 얼마나 시간이 걸리는지가 중요하기 때문이다. 결국 최악의 경우도 고려하여 대비하는 것이다.

우리가 Big-O 표기법으로 시간복잡도를 그래프를 그려 알아볼 수 있는데, n의 값이 커지면 커질수록 그래프는 점점 기울기가 완만해진다. 따라서 상수, 지수, 계수등이 시간복잡도에 영향력이 퇴색하기 때문에 생략할 수 있다.

O(1)

O(1)은 한 번에 출력값을 얻어 낼 수 있는 시간복잡도를 의미한다. 즉 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

O(n)

O(n)은 n번에 출력값을 얻어 낼 수 있는 시간복잡도를 의미한다. 즉 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

O(log n)

O(log n)은 log n번에 출력값을 얻어 낼 수 있는 시간 복잡도 이다. 이는 경우의 수가 절반으로 줄어든다.

O(n^2)

O(n^2)는 입력값이 증가하메 따라 시간이 n의 제곱수의 비율로 증가 하는것을 의미한다.

O(2^n)

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.