시간 복잡도(Time Complexity) & 공간 복잡도(Space Complexity)

1. 시간 복잡도(Time Complexity)

-> 알고리즘 실행 속도

-> 가장 영향을 많이 미치는 요소는 반복문

-> 상수는 큰 영향을 주지 못함

 

(Big O 표기법)

• 가장 일반적으로 사용
• 알고리즘의 최악의 실행 시간을 나타냄
• 입력 n에 따라 몇 번 실행되는지를 계산

O(1): 데이터가 증가함에 따라 성능에 변화가 없을 때 ex) 조건문

O(n): n에 따라 n번, n+50번 등 실행 ex) 반복문 1개

O(n^2): n에 따라 n^2번, n^2+3n+1번 등 실행 ex) 반복문 2개

O(logn): 한번 처리가 진행될 때마다 검색해야 하는 데이터 양이 절반씩 줄어듦 ex) binary search

O(nlogn): 여러 작은 부분으로 쪼개서 각각 해결한 후 마지막에 각각의 부분들을 모으는 경우 ex) merge sort

 

 

---

2. 공간 복잡도(Space Complexity)

-> 알고리즘이 사용하는 메모리 사이즈

-> 시간 복잡도가 우선되긴 하지만 대략적인 파악은 필요할 때가 있음

 

몇 가지 예시를 들어가며 내용을 정리해보자...

---

def func(N):
    for i in range(N):
        print(i)

N값에 상관없이 변수 N의 공간만 필요하다 -> O(1)

 

---

def func(N):
    arr = [0]*N
    return arr

N값만큼의 리스트 공간이 필요하다 -> O(N)

 

---

def func(N):
    if n>1:
        return n*func(n-1)
    else:
        return 1

N값만큼 변수 N이 생성된다 -> O(N)