231229 동계 모각코 2차

시간복잡도를 이어서 공부해보자. 여러가지 유형의 시간복잡도를 생각해볼 수 있다. 

전 시간에 for문과 while문의 시간복잡도를 생각해보았다. 이번에는 재귀함수의 시간복잡도다. 

사실, 재귀함수도 base case 가 있는 반복문이기 때문에, 크게 다른점은 없다. 

위 코드의 시간복잡도를 생각해보자. 재귀함수긴 하지만 결국 n번 함수가 실행되기 때문에, 시간복잡도는 O(N) 이다.

 

위 함수의 시간복잡도도 크게 다르지 않다. 첫번째 함수는 n이 음수가 됬을 때 0을 리턴한다. 5보다 작은 경우, 3, 1 을 각각 리턴하는데 

이는 O((N-5)+3) 으로 표현할 수 있다. 작은 상수는 무시되므로 결국 시간복잡도는 O(N) 이다.

두번째 함수의 시간복잡도 또한 마찬가지로, 특정 상수의 조건에 걸렸을 경우 추가적인 연산을 한다. 이를 계산해보면, O(N-120 + log60) = O(N) 이다. 이렇게 나오는 이유는, n이 120보다 작은 경우 절반씩 줄어들기 때문이다. 그래서 120을 뺐다.

 

 

 

다음 내용은 공간복잡도다. 쉽게 말하여 메모리에 차지하는 공간을 의미한다고 보면 될 것 같다. 시간복잡도와 동일하게 점근적 표기법을 사용한다. 

간단한 배열 예시를 통하여, 공간복잡도를 알아보자. 

 

위의 2차원 배열에서 공간복잡도는 O(N^2) 이라는 것을 어렵지 않게 알 수 있다. 보통 메모리를 계산하는 기준으로 C++ 언어를 사용하는데, int 가 4byte 라는 것으로 미루어 보아 다음과 같이 쉽게 계산이 가능하다. 

아래의 코드를 봤을때, 그렇다면 3차원 배열의 공간복잡도는 O(N^3) 이라는 것을 어렵지 않게 알 수 있다.

 

또한 공간복잡도를 추론할 때 중요한 점으로, 함수가 실행되는 stack 구조에 의하여 함수 내 정의한 값이 함수가 종료되어 사라졌다면 공간 복잡도를 계산할 때 단숞히 모든 것을 더하는 것이 아니라, 특정한 시점의 메모리를 차지하고 있는 그 시점에서의 메모리 사용량을 공간복잡도로 계산해야 한다. 따라서 아래와 같은 코드에서 공간복잡도는 O(N^2) 된다는 것을 어렵지 않게 알 수 있다. 

 

 

 

이제 가장 기본적인 자료구조인 배열에 관하여 학습 한 후 2회차를 마무리하려고 한다.

컴퓨터공학도라면 가장 먼저 배우는 자료구조이다. 지금껏 어러 번 배열에 관해 학습해봤지만, 시간복잡도와 공간복잡도를 고려하여 다시 한번 배워보도록 하자. 

 

크게 삽입과 삭제, 탐색 연산이 있다. 

 

삽입을 하게 되는 경우, 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들이 한칸씩 이동해야 한다. 따라서 일반적으로 삽입의 시간복잡도는 O(N) 이 된다. 최선의 경우에는 맨 뒤에 새로운 값을 삽입할것임으로 이때의 시간복잡도는 O(1) 이다. 다만 시간복잡도는 항상 최악의 경우로 결정하므로, 삽입의 시간복잡도는 O(N)으로 표기한다. 

 

삭제의 경우, 삽입과 마찬가지다. 맨 뒤의 값을 제거하는 경우 O(1) 이지만 , 삽입과 같이 삭제한 자리를 매꾸기 위하여 N-1 개의 값들이 모두 이동하게 된다. 즉 시간복잡도는 O(N) 이다. 

 

탐색의 경우, 가장 기본적인 알고리즘의 탐색은 당연히 맨 앞에서부터 훑는 방법이 가장 기본적인 알고리즘이다. 이 경우 당연히 시간복잡도는 O(N)이다. 하지만 k번째의 값을 구할때는 바로 그 인덱스를 찾아가면 되므로, 시간복잡도는 O(1) 이 된다.