시간복잡도와 공간복잡도

계기 및 목표

• 알고리즘 문제를 풀다보면 효율성 테스트에서 막히는 경우가 꽤 된다.
• 알고리즘의 효율성을 높이기 위해 어떤 부분에 집중해야하는지에 대해서 알기위함
• 알고리즘의 효율성 = 시간복잡도를 낮춘다 && 공간복잡도를 낮춘다
  • 시간복잡도란?
  • 공간복잡도란?

---

복잡도(Complexity)란?

• 알고리즙의 성능, 효율성을 나타내는 척도
• 크게 시간 복잡도(time complexity) 와 공간 복잡도(space Complexity)로 나눌 수 있다.
• 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시
• 복잡도를 나타내는 방법으로는 최악의 경우를 대비할 수 있는 Big-O 표기법을 주로 사용한다.
• 수행시간 = 시간복잡도
• 메모리사용량 = 공간복잡도

시간복잡도 (Time Complexity)

• 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수
• 주로 빅오(Big-O) 표기법으로 표현한다.

공간복잡도 (Space Complexity)

• 프로그램의 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지
• 주로 빅오(Big-O) 표기법으로 표현한다.  
  • 고정공간
    • 알고리즘과 무관한 공간
    • 예시 : 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
  • 가변 공간
    • 문제를 해결하기 위해 알고리즘이 필요로 하는 공간
    • 예시 : 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등
• 고정 공간은 상수이므로 공간복잡도는 가변공간에 좌우된다.

---

빅오 표기법 (Big-O notation)

• 알고리즘의 효율성을 평가
• 점근 표기법 
  • Big-O(빅-오) : 상한 점근
  • Big-Ω(빅-오메가) : 하한 점근
  • Big-θ(빅-세타) : 위 둘의 평균 

위 3가지 점근 표기법 중 가장 최악의 경우를 상정하는 Big-O(빅-오) 점근법을 자주 사용한다.

• Big-O 표기법의 종류
  • O(1)
  • O(N)
  • O(log n)
  • O(n2)
  • O(2n)

 [효율성]

O(1)>O(log n)>O(n)>O(n log n)>O(n^2)>O(2^n)

 

 

• 빅오 표기법 예제
  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^2) : 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
  6. O(2^n) : 피보나치 수

---

복잡도 계산 예시(Big-O)

1. 간단한 for문

result = 0
for i in range(1, 100):
	result+=1

• 반복문이 N번 반복해도 for 문 안에서의 지역변수이므로 공간복잡도는 O(1)
• for 문 한바퀴를 돌아야하므로 시간복잡도는 O(n)

2. 재귀함수

def factorial(n):
	if n==1:  # n이 1일 때
    	return 1 # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n-1)  # n 과 factorial 함수에 n-1을 넣어서 반환된 값을 곱함

위의 경우 함수의 매개변수 n의 값에 따라 공간 복잡도가 달라지는 경우

• 함수 내부에서 n이 1일때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간복잡도는 O(n) 이 된다
• n=3 일경우 3번(n번) 계산되므로( 3*f(2), 2*f(1), 1*f(1) ) 시간 복잡도는 O(n)이 된다.

---

앞으로의 목표

• 이론적인 내용만으로는 복잡도 계산이 완벽하기 이해되지 않으므로 좀 더 많은 예시를 찾아보고 연구해봐야할 듯 하다.
• 정렬의 종류와 방식에 대한 이해 필요

 

---

참고

빅오 표기법 : https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란

시간복잡도 예시 : https://yoongrammer.tistory.com/79

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

복잡도 계산 : https://it-sunny-333.tistory.com/171

[재귀호출] 팩토리얼 /피보나치 수열 /순열 시간복잡도