자료구조 기초

복잡도

: 알고리즘의 성능을 나타내는 척도로 시간 복잡도와 공간 복잡도로 나눌 수 있다.

 

1. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수, 즉 얼마나 오래 걸리는지를 의미한다

 

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

 

시간 복잡도와 공간 복잡도의 경우 trade off 관계로 시간 복잡도가 낮아지면 공간 복잡도가 높아지는 또는 반대의 경우가 성립한다

 

시간 복잡도

1) Big-O(빅오 표기법) 

: 알고리즘의 표기법 중 하나로 실행 시간의 상한을 나타내는 표기법이다.  

- A : 가위바위보 게임에서 이기면 1000원 지면 100원을 받을 수 있는 경우

- B : 가위바위보 게임에서 이기면 800원 지면 300원을 받을 수 있는 경우

위의 두 가지 경우 최악의 경우 A는 100원의 수익이 발생하지만 B의 경우 300원의 수익이 발생한다. 물론 최고의 경우는 A의 수익이 더 크다. 하지만 내 선택이 항상 최고일 수 없기 때문에 알고리즘 선택의 경우 최악의 경우를 우선적으로 고려해야 한다.

<Big-O 표기법 : 시간 복잡도 표로 위쪽에 있을수록 더 빠르다>

연산 횟수가 3N³ + 5N² + 10인 알고리즘이 있다고 가정해보자. 빅오 표기법에서는 지수가 가장 큰 항만 남기기 때문에 O(N³)으로 표기된다

큰 항만 남기는 이유는 숫자가 계속 증가한다고 가정할 경우 무한대가 되기 때문에 큰 항만 남기는 것이 간단하기 때문이다.

하지만 N의 값이 작고 상수의 값이 크다면 상수의 영향력이 매우 크기 때문에 빅오 표기법이 절대적인 것은 아니다.

 

이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N²)의 시간 복잡도를 가진다

 

공간 복잡도

1) Big-O(빅오 표기법) 

: 공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다. 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 MB단위로 제시된다.

 

 

참고자료
- 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음, 한빛미디어 옮김