CS_알고리즘 공부 : 시간 복잡도 & 공간 복잡도.

◇ 시간 복잡도 & 공간 복잡도.

목  차

1. 시간 복잡도

2. 공간 복잡도

※ 알고리즘 성능을 평가하기 위해 '복잡도(Complecity)'의 척도를 사용합니다.

그 중 '시간 복잡도' 와 '공간 복잡도'의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때,
'복잡도가 낮을 수록' 좋은 알고리즘이라고 말합니다.

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석.
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석.

Ⅰ. 시간 복잡도.

"시간 복잡도"는 "특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간"을 의미합니다.

같은 결과를 가지는 프로그래밍 소스코드로 작성 방법에 따라서 걸리는 시간이 달라지며,
같은 결과물을 만드는 같은 소스라면 '소요 시간'이 적게 걸리는 것이 좋은 소스입니다.

🩻. 빅-오 표기법.

'시간 복잡도'에서는 '빅-오 표기법'이라는 개념이 나옵니다.

많은 경우의 수들 중 "최악의 경우를 계산하는 방식"을 "빅-오(Big-O)표기법"이라고 부릅니다.

★ 여기서 'n'이란, 입력되는 데이터를 의미합니다.

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다.
데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

O(log₂ n) (Logarithmic)

입력 데이터의 크기가 커질수록
처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다.

예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다.

이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.

O(n log₂ n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다.
예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다.

정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다.

예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다.

이중 루프(n² matrix)가 대표적이며
단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다.
대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.

그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같습니다.

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

우측(slower) 쪽으로 갈수록, 알고리즘의 효율성이 떨어집니다.

🩻. 빅-오 표기법 EX.

1. O(1) : 스택의 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(n²)
: 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort),
선택정렬(selection sort)

6. O(2ⁿ) : 피보나치 수열

🩻. Python 기준, 소스 코드 시간 측정 방법.

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

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

Ⅱ. 공간 복잡도.

'공간 복잡도'는 "작성한 프로그램이 얼마나 많은 공간(메모리 공간)을 차지하느냐를 분석하는 방법" 입니다.

but, 과거에 비해 하드웨어 메모리 공간이 넘쳐나다 보니 이전보다 중요도는 낮아진 편.

'시간 복잡도'의 경우, 알고리즘을 잘못 구성하면 결과값이 나오지 않거나,
너무 느린 속도로 나오기에, 최근에는 '시간 복잡도'를 더 우선시합니다.

• '시간'과 '공간'은 반비례적인 경향이 있습니다.

• 알고리즘은 '시간 복잡도'가 중심!!

🩻. 공간 복잡도를 줄이는 방법.

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지,
몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼칩니다.

프로그램에 필요한 공간은 크게

고정 공간
가변 공간
이 있는데,

시간적인 측면을 무시하고 공간 복잡도만 고려한다면
고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다.

함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.

특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를
저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고,

반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라 봅니다.