[💻알고리즘] Time Complexity(시간 복잡도)

취업을 위해 코딩테스트를 본격적으로 준비하기 전, "효율적인 알고리즘"이란 무엇인가에 대한 고민을 해보았다. 아래 글은 여러 블로그와 인프런의 'Do it! 알고리즘 코딩테스트 with JAVA' 강의를 보고 내린 답이다.

 

주어진 문제를 풀기 위한 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말이다.

 

🌈시간복잡도

"문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것"은 무슨 의미일까?

 

입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 고려한다는 의미라고 필자는 생각한다. 효율적인 알고리즘을 구현하였다는 것은 다시 말해 입력 값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하였다는 이야기이다.

 

🌈Big-O 표기법

시간 복잡도를 표기하는 방법에는 Big-O, Big-Ω, Big-θ가 있다.

- Big-O(빅-오) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
- Big-Ω(빅-오메가) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
- Big-θ(빅-세타) : 최선과 최악의 평균(average case)

이 중 Big-O 표기법이 가장 자주 사용되는데(코딩 테스트에서도 역시 Big-O 표기법 사용), 이는 최악의 경우를 고려하여 프로그램이 실행되는 과정에서 소요되는 "최대 시간"을 구해야하기 때문이다. 

Big-O Complexity Chart

(1) O(1)

일정한 복잡도(constant complexity)라고 하며, 입력 값이 증가하더라도 Time이 늘어나지 않는다. 다시 말해, input의 크기와 관계 없이, 즉시 output을 얻는다는 의미이다.

(2) O(log n)

로그 복잡도(logarithmic complexity)라고 하며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

(3) O(n)

선형 복잡도(linear complexity)라고 하며, 입력 값이 증가함에 따라 시간 또한 "같은 비율"로 증가한다.

(4) O(n^2)

2차 복잡도(quadratic complexity)라고 하며, 입력 값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다.

(5) O(2^n)

기하급수적 복잡도(exponential complexity)라고 하며, Big-O 표기법 중 가장 느린 시간복잡도를 가진다.

 

🌈알고리즘 선택의 기준으로 활용하기

코드의 시간 복잡도를 도출하고, 이후 전체 연산 횟수를 계산한다.

연산 횟수 = 알고리즘의 시간 복잡도 X 데이터의 크기

데이터의 크기와 알고리즘 종류에 따라 코드가 최종적으로 적합한지, 아닌지가 결정된다. 실제 코딩 테스트에서 테스트 케이스는 모두 통과하였으나 시간 초과가 나는 경우, 이 원리를 바탕으로 문제가 되는 코드 부분(주로 반복문)을 도출할 수 있다.