[알고리즘] 복잡도

이것이 취업을 위한 코딩 테스트다. with 파이썬 책을 참고하여 정리한 내용입니다.

복잡도

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

보통 시간 복잡도와 공간 복잡도는 TradeOff가 성립

시간 복잡도

• 코딩 테스트에서의 복잡도는 보통 시간 복잡도를 이야기함.
• 시간제한 : 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는데 까지 걸리는 시간을 의미.
• 빅오(Big-O) 표기법 사용.

빅오(Big-O) 표기법

• 가장 빠르게 증가하는 항만을 고려하는 표기법. 고등학생 수학 극한 보낼 때 느낌?
• ex) 반복문으로 합계를 더하는 경우 : $O(N)$, 2중 반복문 : $O(N^2)$ (물론, 내부적으로 반복문 안에 다른 함수를 호출한다면 달라짐)
• 시간 복잡도 표. 위쪽에 있을 수록 더 빠르다.

빅오 표기법	명칭
$O(1)$	상수 시간(Constant time)
$O(logN)$	로그 시간(Log time)
$O(N)$	선형 시간
$O(NlogN)$	로그 선형 시간
$O(N^2)$	이차 시간
$O(N^3)$	삼차 시간
$O(2^n)$	지수 시간

제한 시간이 1초일 때 예시

• 시간 복잡도 분석은 문제 풀이의 핵심.
• 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있기 때문에 조건을 먼저 보기도 한다.
• 모두 제한 시간이 1초인 문제에 대한 예시
  • N의 범위가 500인 경우 : 시간 복잡도가 $O(N^3)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 2,000인 경우 : 시간 복잡도가 $O(N^2)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 100,000인 경우 : 시간 복잡도가 $O(NlogN)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 10,000,000인 경우 : 시간 복잡도가 $O(N)$인 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도

• 마찬가지로 빅오(Big-O) 표기법 사용.
• 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 설계.
• (리스트의 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 아닌지 고민해봐야 한다..)

시간 측정 방법

import time

# 측정 시작
start_time = time.time() 

# 프로그램 소스코드 ~~

# 측정 종료
end_time = time.time()

# 수행 시간 출력
print("time :", end_time - start_time)