시간복잡도 & 공간복잡도

Time complexity & Space complexity

블로그에 알고리즘 배울 때 가장 먼저 배우는 빅-오 표기법과 시간 복잡도, 공간 복잡도를 안 적어놨길래 지금이라도 정리해서 올립니다.
자세한 정보는 웬만하면 위키피디아을 찾아보시는 걸 추천드려요.

시간 복잡도

알고리즘 수행 시간을 측정한 계산 복잡도(시간)

공간 복잡도

메모리 차지하는 양(메모리)

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

빅-오 표기법은 주로 시간 복잡도를 나타내는데 이 알고리즘이 '어느 정도 걸리겠다'는 것을 알 수 있습니다.

빅-오 표기법은 O(내용)으로 표기합니다. 알고리즘의 복잡도에서는 주로(항상이 아닙니다) 반복문이 좌지우지하기 때문에 반복문이 몇 번 도는지 확인해서 표기할 수도 있습니다.

복잡도가 N + 12여도 상수를 제외하고 O(N)으로 표기합니다. 그 이유는 크기가 커지면 정말 상수가 어마어마하게 크지 않은 이상 변수가 더 커질 것이기 때문입니다.

몇 가지를 살펴보도록 하겠습니다.(오류 수정 부탁드립니다.)

상수 시간

상수 시간은 O(1)로 표기합니다. 어떠한 입력의 크기에도 한정된 T(n)이 걸리면 O(1)이라고 할 수 있습니다.
상수 시간이 걸리는 것들:

1. 해쉬(이론적으로 O(1)인 것 같습니다. 왜냐하면 해쉬 테이블은 하나의 key값에서 리스트로 이어지는 해쉬들도 있거든요. 이때는 O(n)입니다.)
2. 대입 연산
3. 반복문에서 범위가 상수(예, 1 to 100)일 때
4. 인덱스 계산
5. 조건문

선형 시간

선형 시간은 주로 O(n)으로 표기합니다. 반복문에서 1 to n을 도는 것이 O(n)으로 표기할 수 있겠죠.

입력에 따라서 수행시간이 비례해서 증가하는 알고리즘이 선형 시간이 걸린다고 합니다.

로그 시간

로그 시간은 O(log n)으로 표기합니다. 대부분 log의 밑은 2이고요. 이진 탐색이 대표적인 로그 시간이 걸리는 알고리즘입니다.

지수 시간

지수 시간은 O(2^n)같이 입력의 크기에 따라 급격하게 올라가는 알고리즘을 표현할 때 사용합니다. 

 [출처: 위키피디아]

그래프를 보시면 O(1)는 어느 입력에나 같은 시간이 걸리고요. O(n)은 직선으로 n의 크기에 따라 같이 커지는 것을 확인 할 수 있습니다.

O(log n)도 입력의 크기가 커져도 거의 일정하게 유지하는 것을 확인 할 수 있습니다. 

나머지들은 지수 시간(n^2), O(n log n)등이 있는데 입력 크기가 커질 수록 복잡도로 급격하게 올라가는 것을 확인 할 수 있습니다!