알고리즘) 시간복잡도와 공간복잡도

시간복잡도와 공간복잡도

 

시간복잡도

(Time Complexity)

 

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.(시간이 아니다.)

일반적으로는 1억 번의 연산을 1초로 예측한다고 한다. (CPU)

 

시간복잡도는 3가지 유형이 존재한다.

 

1. 빅-오메가(Ω(n))

 

최선일 때(best case)의 연산 횟수를 나타낸 표기법

 

 

2. 빅-세타(Θ(n))

 

보통일 때(average case)의 연산 횟수를 나타낸 표기법

 

 

3. 빅-오(O(n))

 

최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

 

 

일반적으로 최악의 경우를 염두에 두는 것이 안정적일 것이다.

 또한 광범위한 데이터의 집합에 대하여

알고리즘을 적용시켜 평균값을 계산하는 것은 매우 어려울 수도 있다.

 

따라서 시간복잡도의 척도를 계산할때는 최악의 경우를 주로 사용한다.

 

O(1) : 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸림

O(long n) : 로그시간. 입력의 크기에 따라 로그의 형태로 증가

O(n) : 선형시간. 입력의 크기에 비례하여 선형적으로 증가

O(n log n) : 선형로그 시간. 일부 정렬 알고리즘 등에서 나타남

O(n²) : 이차 시간. 입력의 크기의 제곱에 비례하여 증가.

O(2ⁿ): 지수 시간. 입력의 크기에 따라 지수적으로 증가.

 

---

공간복잡도

(Space Compexity)

 

프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간(메모리)의 양을 말한다.

 

공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념이다.

 

보조공간(Auciliary Space) : 알고리즘이 실행되는 동안 사용하는 임시 공간

 

 

예시

INPUT : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

============================================

def filter_even_numbers(arr):
    even_numbers = []
    for num in arr:
        if num % 2 == 0:
            even_numbers.append(num)
    return even_numbers

 

파이썬으로 짝수를 필터링하는 코드를 간단하게 짜보았다.

 

함수는 입력리스트인 arr이라는 배열의 크기에 따라 비례하여 even_numbers에 추가한다.

 

따라서 입력크기가 n이라면, 이 함수의 공간복잡도는 O(n)이 된다.

 

메모리공간은 입력 리스트의 크기에 비례하므로, 공간 복잡도가 선형적으로 증가한다.

 

이미지 참고 - [자료구조] 자료구조 & 최대 부분 배열 합

내용 참고 - MadPaly! -

내용 참고 - yoongrammer -