[알고리즘] 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

안녕하세요 감자코딩에 감자개발자입니다. 

이번시간에 알아볼 개념은 점근적 표기법과 시간복잡도와 공간복잡도 입니다.

1. 알고리즘 성능분석 

- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과

- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과

* 점근적 표기법(Asymptotic notations)

   

1) 빅오 표기법(O notation) - 내가 생각하는함수가 다른 기준이되는 함수보다 아래쪽에 있다. 아무리 느려진다고해도 기준함수보다는 빠르다.

빅오표기법에 대한 간략한 내용입니다. 이제 빅오표기법에대한 예를 한번 확인해보겠습니다.

예)

3n+1 = O(n^2)

n>=n0에 대해 3n+1 <= cn^2을 만족하는 c와 n0가 있는지 확인예제

양변을 n^2으로 나누어보면 , (3/n) + (1/n^2) <= c 가 된다.

따라서, n과  c의 범위는 n >=1 , c>=4을 만족하면 위의 식은 항상 성립한다.

요약하자면, f(n) 빅오표기법에서 있어서, cg(n)보다 아래에 있으므로 기준이 되는 함수보다 아무리 느려진다고해도 성능적으로 우수하다는 말입니다.

2) 오메가 표기법(Θ notation) - 재 함수가 기준함수보다 위쪽에 있다. 항상 더빠를순 없다. 항상 최선의 경우를 생각한다. 

요약하자면, Θ notation을 보면 cg(n)위에는 항상 f(n)이 존재하므로, 아무리 빨라진다고 하더라도 cg(n)보다는 빨라질수 없다는말이다.

예) 

3n^2 - 4n +1 = Θ(n)

n >= n0에 대해 3n^2-4n+1 >= cn을 만족하는 c와 n0가 있는지 확인한다.

양변을  n으로 나누면 (3n) -4 + (1/n)  >= c 이다.

따라서,  n>=2 , c=2 을 만족하면 위의 식을 만족하게 된다.

단, n0는 2차방정식에서 gc(n)을 보았을때 기울기가 gc(n) 보다 높아지는 그 지점을 n0라고 생각을 한다고 가정한다. 

3) 쎄타 표기법(Ω/ω notation) - 빅오와 오메가 사이에 있는것이 쎄타 표기법

이것에 대해서 설명드리면, f(n)이라는 함수가 c2g(n) 아무리 느려도 c1g(n)보다는 빠르다.

 c2g(n) = 2n^2 , f(n) = n^2 , c1g(n) = 1/2n^2이라고 생각을 하면 된다.

예) 

2n^2 -3n = Ω(n2) 

n >= n0인 모든 n에 대하여  c1n^2 <= (1/2n^2) - 3n< c2n 을 만족하는 c1,c2,n0 만족하는지 보기.

양변을 n^2으로 나누게되면 c1 <= (1/2)-(3/n) <= c2가 된다.

c1 <= (1/2)-(3/n) <= c2

일경우

- n >=1 , c2 >=(1/2)성립 

- n >= 7일때 c1 <= (1/14)이면 성립

- c1 = 1/14, c2 = 1/2, n0 = 7이면 

1/2n^2 - 3n = Ω(n^2)이 성립하게 된다.

2. 복잡도(Complexity)

종류: 시간복잡도(Time Complexity) , 공간복잡도(Memory Complexity)

보통 빅오 표기법을 사용하는데, 이 그래프를 보면 시간복잡도 Big-O표기법에 대한 전반적인 사항을 확인할 수 있다.

1) O(1) 시간복잡도

이번에는 빅오표기법에 O(1)을 확인해볼 수 있을 것이다. 하나의 배열에 인덱스 하나씩 접근하게 되므로, O(1)만큼의 시간복잡도가 나오는것을 확인 할 수 있다. 시간복잡도에서 가장중요한 개념은 arrayItem[1]에 접근하는것을 추가한다고 생각을 해보자. 그럴경우에는 결국 O(1)의 복잡도를 가진다 왜? 시간복잡도의 개념에서는  O(N*1)에서 N은 무시하고 생각을 하게 된다. 

알고리즘 예제로 살펴보면, push pop Stack , Hash Table의 예를 들 수 있다.

2)O(n) 시간복잡도

O(n)을 살펴보도록하자. 현재 printAllItems의 메소드에서 지금 for문이 돌아가는것을 볼 수 있을것이다. Iteretor로 해서 arrayOfItems 배열에서 모든값들을 뽑아내는것을 알 수 있다. 이경우 O(n)의 복잡도를 가지는것을 알 수 있다. 

알고리즘 예에서는 이진트리, 이진 링크드리스트를 들 수 있다. 이것역시 앞에 있는 nO(n) = O(n) 을 같게 생각을 한다. 결국 앞에 n을 무시해도 상관없다는 말이다. 앞의 상수는 그저 따라오는 아이일뿐..

3)O(log n) 시간복잡도

O(log n)을 살펴보자. 보통 이진트리에서 삽입을 하는경우를 예를 들수 있을것이다. 지금 현재 위의 트리의 상황은 1이 삽입 된경우이다. 현재 총 8개의 노드를 가지고 있으며 이것들의 노드를 log로 나타내면 n = 8 , log 8 = log2^3 = 3 으로 나타낼 수 있을것이다. 보통 트리 Search, Access, Insertion , Deletion 의 경우에 쓰이는 복잡도 이다.

4) O(n^2) 시간복잡도

 O(n^2)을 살펴보자. 현재 PrintAll메소드안에 2중 for문이 함께 작성되어있는것을 확인할 수 있다. 두개의 포문둘다 Iterator로 인하여 배열에 있는 모든값들을 출력하고 있는것들을 볼 수 있을 것이다. 밖에 있는 for 문 O(N) , 안에있는 포문 O(N) 이므로, 결국 시간복잡도는 O(N^2)이 되는것을 확인 할 수 있다. 이것역시 앞에오는 상수는 2*O(n^2) = O(n^2)이라는것을 확인 할 수 있다.

5) O(nlogn)시간복잡도

O(nlogn)을 살펴보자. 보통 정렬에서 많이 보이는 복잡도이다. 양측의 트리들의 노드들을 검색하면서 정렬이 되기때문에 보통 노드들간의 비교관계로 인하여 nlogn의 시간의 복잡도가 발생한다. n은 트리들간의 비교횟수가 되고 logn은 노드들의 수로 확인할 수 있다.

* 마무리 * 

알고리즘에 있어서, 시간복잡도는 무엇보다 중요하고 성능분석에 있어서 가장 기초가 되는부분이라 한번 정리해봤습니다. 나름 잘 쉽게 얘기한다고 써보았는데, 잘못된부분있으면 피드백 주시면 감사하겠습니다.

지금까지 감자코딩에 감자개발자였습니다. 

Reference : T Academy, 상상개발자