시간복잡도와 공간복잡도

시간 복잡도와 공간 복잡도는 알고리즘을 평가할 때 쓰는 지표라는 공통점이 있습니다.

 

1. 시간 복잡도

시간 복잡도는 해당 알고리즘을 수행하는 데 걸리는 시간을 의미합니다.

시간 복잡도가 낮을수록 실행 속도가 빠르고 효율적인 알고리즘입니다.

시간 복잡도를  대표적인 방법으로는 Big-O 표기법이 있습니다.

Big-O 표기법은 최악의 상황에서의 시간 복잡도를 나타냅니다.

 

다음은 여러 시간 복잡도입니다.

1-1. O(1)

입력한 데이터의 크기에 상관없이 항상 일정한 시간이 걸리는 알고리즘입니다.

스택의 push, pop 연산을 예로 들 수 있습니다.

1-2. O(log n)

입력한 데이터의 크기가 커질수록 log 만큼 시간이 짧아지는 알고리즘입니다.

대표적인 알고리즘으로는 이진 탐색 알고리즘을 예로 들 수 있습니다.

1-3. O(n)

입력한 데이터의 크기에 비례해서 시간이 늘어나는 알고리즘입니다.

데이터의 크기가 10배로 늘어나면 처리 시간도 10배로 증가합니다.

for 문을 예로 들 수 있습니다.

1-4. O(n log n)

입력한 데이터의 크기가 커질수록 시간이 log 만큼 늘어나는 알고리즘입니다.

데이터의 크기가 10배로 늘어나면 처리 시간은 20배로 증가합니다.

병합 정렬, 퀵 정렬, 힙 정렬 등을 예로 들 수 있습니다.

1-5. O(n*n)

입력한 데이터의 크기가 커질수록 시간이 n 만큼 증가하는 알고리즘입니다.

데이터의 크기가 10배로 늘어나면 처리 시간은 100배로 증가합니다.

이중 for 문을 예로 들 수 있습니다.

1-6. O(2*(n*n))

입력한 데이터의 크기가 커질수록 시간이 기하급수적으로 커지는 알고리즘입니다.

대표적으로 피보나치 수열이 있습니다.

 

 

2. 공간 복잡도

공간 복잡도는 해당 알고리즘을 수행하기 위해 필요한 메모리의 크기를 의미합니다.

공간 복잡도가 낮을수록 자원을 적게 사용하는 효율적인 알고리즘입니다.

공간 복잡도 또한 Big-O 표기법으로 나타내는 것이 일반적입니다.

 

3. 시간 복잡도와 공간 복잡도의 중요성

알고리즘에 있어서 시간 복잡도와 공간 복잡도 모두 중요한 개념이지만

과거에 비해 H/W 성능(메모리 용량)이 향상되었기 때문에

시간 복잡도를 먼저 고려하는 것이 일반적입니다.

 

참고

https://khys.tistory.com/m/95

시간 복잡도와 공간 복잡도 (Time complexity and space complexity)

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Algorithm] 시간 복잡도, 공간 복잡도