[알고리즘] 복잡도(코딩테스트 Tip)

복잡도란?

• 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟 - 빅오(Big-O) 표기법 사용

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

 

시간복잡도

---

O(1) - 상수 시간 / O(N) - 선형 시간

-> N의 값이 작을 때는 상수 값이 크다면, 상수 값이 미치는 영향력이 커진다. 

    따라서 빅오 표기법이 항상 절대적인 것은 아니다.

 

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

예시(시간 제한이 1초라고 가정)

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

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

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

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

 

공간복잡도

---

일반적으로 메모리 사용량 기준은 MB단위로 제시되며, 코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 

 

 

시간과 메모리 측정 with 파이썬

---