[알고리즘 공부] 1. 시간, 공간 복잡도

1) 시간, 공간 복잡도

공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는가.
시간적 효율성: 연산량 대비 얼마나 적은 시간을 요하는가.

효율성을 뒤집어 표현하면 복잡도가 되며, 이 복잡도가 높을수록 효율성은 낮아진다.

---

복잡도의 점근적 표기

이전에 재귀식에선 T(n)으로 표시했으나, 주로 Big-Oh 표기법 사용(예: O(n))

1) 빅 오 표기
빅 오 표기는 복잡도의 점근적 상환이다. 가령 2a² + 2a + 2 라고 수식이 나올 경우, 상수를 빼고 O(n²)로 표기.
f(n) = n²+n이고 g(n) = n³일때 f(n) = O(g(n))으로 나타낼 수 있음. f(n)의 차수가 g(n)의 차수보다 같거나 작다는 뜻.

예시) n^100 = O(2^n)은 참임. n이 충분히 크다고 가정했을 때, n^100보다 2^n의 차수가 훨씬 커지게 되므로 2^n의 차수보다 같거나 작다가 성립함. 이 때문에 만일 O(2^n + n^100) 일 경우 O(2^n)으로 더 큰 차항의 값만 남게 됨.

2) 빅 오메가 표기
복잡도의 점근적 하한. 빅오처럼 최고차항만 계수없이 취한다.
'최소한 이만한 시간은 걸린다'는 걸 의미. f(n) =n^3 이고 g(n) =n^2+n 일때 f(n) = Ω(g(n))으로 나타낼 수 있음. f(n)의 차수가 g(n)의 차수보다 같거나 크다는 뜻이다.

3) 세타 표기
빅오와 빅 오메가 표기 값이 같을 경우, f(n)은 n이 증가함에 따라 n제곱과 동일한 증가율을 가진다는 의미.
쉽게 말해 최고차항(가장 높은 차수)를 의미한다.

 

재귀함수의 T(n)

#1. 단순 반복
def func(N):
   ret = 1   # 1번 수행
   for i in range(N):
       ret += i   # N번 수행
얘의 시간 복잡도는 T(n) = n + 1 = O(n)이렇게 표기 가능

#2. 중첩 반복
def func(N) :
  for i in range(1, N+1<= 1....N):  # N번 반복
    for j in range(1, i+1 <= 1...i):  # i가 1이면 1번, 2면 2번.. N이면 N번 반복
                                      # 즉 1부터 N까지의 합과 같음
         sum = sum + i + j
     return sum
이 경우 시간 복잡도는 T(n) = n(n+1)/2 = O(n^2)로 표기 가능.

#3. 이런 것도 있음
arr = [1,2, ... n]
def func(arr):
  for i in range(1,n+1): # i가 1이면 1번, 2면 2번.. n이면 n번 반복
     k = max([1..i])  # 이거 자체가 1부터 i까지 한번 반복
즉 위와 같이 T(n) = n(n+1)/2 = O(n^2)로 표기 가능.

#4. 2개 이상 반복 연속될 경우 차수가 더 높은 반복의 차수가 전체 차수가 됨.
arr = [1,2, ... n]
def func(arr):
  sum1 = 0
  for i in range(1, n+1 <= 1...n):  #O(n)
     sum1 += i

 sum2 = 0
 for i in range(1, n+1) :
     for j in range(i, n+1):  # i가 1이면 n회, i가 2면 n-1... i가 n이면 1회 시행
         sum2 = sum2 + i + j  # 이것도 뒤집어보면 1부터 n까지의 합=> O(n^2)
=> T(n) = O(n) + O(n^2) 이 경우에는 최고차항인 O(n^2)이 시간복잡도가 됨.

# 5. 반복횟수가 점차 줄어드는 형태일 때 차수는 로그
arr = [1,2, ... n]   # n이 2의 5제곱이라 가정하면 j= 2^5, 2^4...1 순으로 작아지며
def func(arr):       # 총 6번 while문 반복이 일어남. 
   j = n
   while j >= 1:
       j = j//2

n = 2^k (log_2n = k) 
j는 2^(k), 2^(k-1)...2^(1), 2^0(=1) 이렇게 작아지며 반복문은 k, k-1.. 0까지 총 (k+1)번 반복함.
즉 K+1 = log_2n +1인데 상수를 빼버리면 T(n) = O(logn)이라는 시간복잡도 완성!

학습에 참고한 자료 : https://whitepaek.tistory.com/21

이렇게 알아낸 사실을 바탕으로 이전에 못 풀었던 복잡도 문제를 풀었다.

이전에는 못 풀었던 SWEA 문제
1. T(n) = T(n-1) + 1/n 

T(n) = T(n-2) + 1/n-1 + 1/n
T(n) = T(n-3) + 1/n-2 + 1/n-1 + 1/n
...
T(n) = T(n-k) + 1/n-(k-1) + 1/n-(k-2) .. 1/n
T(0) = 0, T(1) = 1이라 할 때
k = n-1
T(n) = T(1) + 1/2 + 1/3 ... 1/n
자연수의 역수(1부터 1/n 까지)의 합은 오일러-마스케로니 상수에 의해 logn과 같다.
따라서 T(n) = O(logn)이 된다.

참고:
https://ghebook.blogspot.com/2010/11/harmonic-series-euler-mascheroni.html
https://math.stackexchange.com/questions/267564/recurrence-relation-tn-tn-1-1-n

 

시간복잡도 활용(시간 제한이 1초(= 대략 for문이 1억번 도는 시간)일 때)

N <= 10이라면 O(N!), O(2ⁿ), O(3ⁿ)까지 OK
N <= 20이라면 O(2ⁿ)까지 OK
N<=100이라면 O(N⁴)까지 OK
N<=500이라면 O(N³)까지 OK
N<=1000이라면 O(N²), O(N2logN)까지 OK
N<=100,000이라면 O(N), O(NlogN), O(logN), O(1)까지 OK

cf) 선택정렬 : 최솟값을 찾아 가장 앞으로 보내는 작업을 N번만큼 진행 => O(N²)

---

공간 복잡도:

int arr[2천만] = 대략 80mb(C++ 기준)
int a[2천만] : 80MB
int a[2백만] : 80 / 10 = 8MB
char a[2천만] : 80 / 4 = 20MB
double a[2천만] : 80 * 2 = 160MB

공간 복잡도 계산시 값이 생성됐다 없어질 수 있기 때문에, 특정 시점에 메모리를 차지하는 값이 가장 많을 때(최악의 상황 가정) 그 시점의 메모리 사용량을 공간 복잡도 계산에 고려.

---

참고: 코드트리(https://www.codetree.ai/)

코드트리