[알고리즘/파이썬] 시간 복잡도, 공간 복잡도 이해하기

알고리즘은 무엇인가?

 

• 알고리즘은 어떤 목적을 달성하거나 결과물을 만들어 내기 위해 거쳐야 하는 일련의 과정들을 의미한다.
• 시간 복잡도를 분석하는 것은 input n에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는지 분석하는 것입니다.

---

빅오 표기법이란?

 

2       ==>  O(1)
2n+3    ==>  O(n)
3n^2    ==>  O(n^2)

 

 

◆ 대표적인 시간 복잡도들을 정의해봅시다.

 

1. O(1) - 상수 시간 : 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한단계만 거칩니다.
2. O(log n) - 로그 시간 : 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
4. O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
5. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.

위 정의를 가지고 예를 들어봅시다. 

 

var n = 12  	 //입력값이 12일 때
O(1) = 1  	 //시간복잡도 = 1
O(log n) = 3.xxx //시간복잡도 = 3
O(n) = 12	 //시간복잡도 = 12
O(n^2) = 144	 //시간복잡도 = 144
O(2^12) = 4096	 //시간복잡도 = 4096

 

 

 

---

시간복잡도 계산법

 

※시간 복잡도가 적은 알고리즘이 좋은 알고리즘입니다. 평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워집니다. 그러므로 최악의 경우로 알고리즘의 성능을 파악합니다.

---

공간복잡도 계산법

 

공간 복잡도 계산은 간단합니다. 메모리를 얼마나 사용하는지 계산하면 됩니다.

예를 들어 크기가 n인 배열을 입력했는데 알고리즘이 내부에서 n x n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 $n^2$이 됩니다.

공간 복잡도는 보통 시간 복잡도에 밀려 중요하게 생각하지 않는 경우가 많은데 빅데이터 처리를 할 경우 공간 복잡도가 위와 같이 제곱으로 뛰게 되면 프로그램이 메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생합니다.

그래서 빅데이터 처리시 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 됩니다.

알고리즘 작성시 공간 복잡도를 아예 생각하지 않게 되면 문제가 발생할 수도 있으므로 공간 복잡도도 신경 써서 작성하는 게 좋습니다.

 

 

 

---

출처

https://ledgku.tistory.com/33

 

https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/