복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다.

복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다.

복잡도를 측정함으로써 다음의 2가지를 계산할 수 있다.

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

---

시간 복잡도

시간복잡도를 표현할 때는 빅오 표기법을 사용한다.

빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

다시 말해 함수의 상한만을 나타낸다.

O(1) : 상수 시간

O(log N) : 로그 시간

O(N) : 선형 시간

O(N log N) : 로그 선형 시간

O(N^2) : 이차 시간

O(N^3) : 삼차 시간

O(2^n) : 지수 시간

상수를 고려해야하는 경우는 적지만, 빅오 표기법이 항상 절대적인 것은 아니다.

---

N이 1,000일 때의 연산 횟수

O(N) : 1,000

O(N log N) : 10,000

O(N^2) : 1,000,000

O(N^3) : 1,000,000,000

시간 복잡도 분석은 문제 풀이의 핵심이다.

문제의 조건을 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 알 수 있다.

예를 들어 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있다.

N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 100,000인 경우 : 시간 복잡도가 O(N log N)인 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

---

공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다.

일반적으로 메모리 사용량 기준은 MB단위로 제시된다.

int a[1000] : 4KB

int a[1000000] : 4MB

int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다.

다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다는 의미이다.

---

복잡도란 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것이다.

동일하 기능을 수행하는 알고리즘이 2개 있을 때 만약 A 알고리즘이 B보다 시간 복잡도가 더 높다면, A 알고리즘이 실행 시간 측면에서 성능이 더 낮다는 의미이다.