[자료구조] 0. 시간 복잡도와 공간 복잡도, 빅-오 표기법 (Time Complexity, Space Complexity, Big - O notation)

좋은 알고리즘이란 무엇일까?

 

실행 속도가 빠르고, 컴퓨터의 메모리를 적게 사용하는 것이 좋은 알고리즘이 될 것이다.

 

알고리즘이 얼마나 빠른지와, 얼마나 메모리를 적게 쓰는지를 평가할 때는

 

알고리즘의 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)라는 척도를 이용한다.

 

시간 복잡도

시간 복잡도는 알고리즘의 속도에 대한 척도이다.

 

시간복잡도를 측정하는데는 연산이 이뤄지는 횟수를 센다.

 

연산은 데이터 입출력, 산술, 반복문, 조건문과 같은 제어문이 있다.

 

입력 데이터의 수 n에 따른 연산횟수의 함수 T(n)을 구성하고,

 

데이터의 수 n의 변화와 그 연산횟수 T(n)의 변화를 분석하여 알고리즘의 시간 복잡도를 평가한다.

 

선형 탐색(순차 탐색) 알고리즘을 예로 들어보면:

def linearSearch(n, target, array)
    for i in range(n):
        if array[i] == target:
            return i+1
    return -1
 
arr = [1,3,5,7,9]

종류		설명	n=1	n=10	n=100
O(1)	상수형	데이터 수에 상관없이 연산횟수가 고정임. 연산의 횟수가 3이여도 O(3)이라고 표기하지않고, O(1)로 표기함.	1	1	1
O(log n)	로그형	(데이터 수의 증가율) < (연산횟수의 증가율)임을 의미. 일반적으로 빅-오 표기법에서의 로그의 밑은 2이다. (컴퓨터가 2진수를 사용하기때문)	0	log(10)	log(100)
O(n)	선형	데이터 수와 연산횟수가 비례함을 뜻한다.	1	10	100
O(nlog n)	선형 로그형	데이터의 수가 m배 늘 때, 연산횟수는 m배 이상으로 늘어남을 의미.	0	10log(10)	100log(100)
O(n^2)	평방형	데이터 수의 제곱이 되는 연산횟수를 가진다. 중첩 반복문에서 볼 수 있다. 여기서부터 매우 느린 시간복잡도를 가지고있다고 볼 수 있다.	1	100	10000
O(c^n)	지수형	연산횟수가 기하급수적으로 증가한다.	2	1024	1.2676506 * 10^30
O(n!)	계승형	연산횟수가 팩토리얼의 형태로 증가한다	1	3628800	9.332622 * 10^157

표와 그래프를 보면, 빅 오의 속도는

O(1) > O(log n) > O(n) > O(n log n) > O(n^2) > O(c^n) > O(n!) 임을 알 수 있다.

 

 

빅-오 표기법 이외에도, 최선의 경우를 생각하는 빅-오메가, 평균의 경우를 따지는 빅-세타 표기법들이 있다.

 

공간 복잡도

공간복잡도는 프로그램이 얼마나 많은 메모리를 차지하는지를 나타낸다.

컴퓨터의 성능 향상으로 중요도가 낮아졌다. 빅오 표기법을 사용한다.

 

총 저장 공간 = 고정 공간 + 가변 공간

S(P) = c + SP(n)

 

고정 공간은 선언된 단순한 상수, 변수들이 차지하는 공간이다.

 

가변 공간은 프로그램 실행 중에 동적으로 쓰이는 공간을 말한다.

 

공간 복잡도를 낮추려면, 고정 공간은 상수이니, 가변 공간에서 낮추어야 한다.

 

다음 두 프로그램을 비교해보자. n!의 값을 반환하는 프로그램들이다.

def factorial_recursion(n)
    if n = 0 or 1:
        return 1
    else:
        return factorial_recursion(n-1) * n

def factorial_repeat(n):
    fac = 1
    for i in range(1, n+1):
        fac = i * fac
    return fac