[알고리즘] 성능 평가

복잡도 ( Complexity )

• 복잡도는 알고리즘의 성능을 나타내는 척도이다.
  • 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
• 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘

빅오표기법 ( Big-O Notation )

• 가장 빠르게 증가
  • 함수의 상한만을 나타냄
• 예를 들어 연산 횟수가 $3N^3$ + $5N^3$ + $1, 000, 000$인 알고리즘이 있을 때 가장 큰 차수만 나타내므로 O($N^3$)으로 표현한다.

순위	명칭
$O(1)$	상수 시간(Constant time)	좋음
$O(logN)$	로그 시간(Constant time)
$O(N)$	선형 시간(Constant time)
$O(NlogN)$	로그 선형 시간(Constant time)	⬆
$O(N^2)$	이차 시간(Constant time)
$O(N^3)$	삼차 시간(Constant time)
$O(2^n)$	지수 시간(Constant time)	나쁨

위로 갈 수록 성능이 좋은 것

시간 복잡도 계산해보기 1)

• N개의 데이터의 합을 계산하는 프로그램 예제

array = [ 3, 5, 1, 2, 4]
summary = 0

for x in array;
		summary += x

print(summary)

• 수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있다.
  • 시간 복잡도 : $O(N)$시

시간 복잡도 계산해보기 2)

• 2중 반복문을 이용하는 프로그램 예제

array = [3, 5, 1, 2, 4]

for i in array:
	for j in array:
			temp = i * j
			print(temp)

• 시간 복잡도: $O(N^2)$
• 2중 배열이라고 무조건 $O(N^2)$는 아님

알고리즘 설계 Tip

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:
  • C언어를 기준으로 통상 1 ~ 3초 가량의 시간이 소요
  • Python을 기준으로 통상 5 ~ 15 초 가량의 시간이 소요
    • PyPy의 경우 때때로 C언어보다도 빠르게 동작함.
    • 테스트 환경에서 PyPy 지원해주는 경우 Py와 Py 둘 다 제출해보기
• $O(N^3)$의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요?
  • 5,000의 세제곱이므로 1,250억 연산횟수
  • 파이썬이 1초당 약 5,000만번 연산하는 경우 약 2,500초 정도 걸림
  • 이런식으로 연산횟수와 소요시간을 예상하면서 알고리즘을 짜야함
• 코딩테스트 문제에서 시간제한은 통상 1 ~ 5초가량
  • 파이썬의 경우 1초에 약 2,000만번 정도의 연산만 처리할 수 있다고 가정하기
  • 혹여 시간제한이 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제 풀기
• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)
• 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같음
  • N의 범위가 500인 경우 : 시간 복잡도가 $O(N^3)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 2,000인 경우 : 시간 복잡도가 $O(N^2)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 100,000인 경우 : 시간 복잡도가 $O(NlogN)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 10,000,000인 경우 : 시간 복잡도가 $O(N)$인 알고리즘을 설계하면 문제를 풀 수 있음
• 문제 많이 풀면서 스스로 복잡도 감 잡기!

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항 ( 복잡도 ) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

• 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면 간결하게 소스코드를 작성할 수 있는 형태도 문제를 출제함

수행시간 측정 소스코드 예제

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

end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력