알고리즘 스터디 준비 - 기본적으로 알아야 할 것들 1. 복잡도

알고리즘 스터디를 제대로 시작하기 전에, 알아야 할 것 같은 몇가지 개념들을 정리 해 보려고 한다.

 

1. 복잡도 : 알고리즘의 성능을 나타내는 척도. 시간 복잡도와 공간 복잡도 두 종류로 나누어지며 복잡도가 낮을수록 좋은 알고리즘임.

                 대체로 '복잡도'라고만 언급된다면 시간복잡도를 뜻함.

     가. 시간복잡도 : 알고리즘 수행을 위해 필요한 시간(연산의 횟수)

빅오 표기법	명  칭	N이 1,000일 때, 연산 횟수
O(1)	상수 시간	1
O(logN)	로그 시간	3
O(N)	선형 시간	1,000
O(NlogN)	로그 선형 시간	10,000
O(N²)	이차 시간	1,000,000
O(N³)	삼차 시간	1,000,000,000
O(2^n)	지수 시간	약 10^301

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

# 기타 프로그램 코드

end_time = time.time() # 측정 종료시간
print('time: ', end_time - start_time) # 소요시간 출력

< 대략적인 시간복잡도 측정방법 >

 

 

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

                              일반적으로 128~512MB정도로, 데이터의 개수가 1,000만 단위가 넘지 않도록 설계 할 것.