분명 손 쉽게 하던 것들인데, 빠른 시간내에 풀자니 기억나지 않았다.
관련하여 내용을 정리할까 한다.
시간 복잡도라하면, 알고리즘이나 코드에서 얼마나 시간을 많이 먹느냐 하는 것이며, 알고리즘을 잘 짜야 하는 가장 중요한 이유로 꼽힌다. (공간 복잡도도 같이!)
아마 소프트웨어 학도라면 알고리즘 강의에서 누구나 배웠을 것이며, 아니라해도 중요성 정도는 알고 있을 것이다.
시작한다.
일반적으로 시간복잡도의 표기는 Big-O notation을 사용한다.
정의는 위와 같다고 보면된다.
예시를 들자면, n = O(3n+2), n^2 = O(9n^2 + 8n) 과 같이 들 수 있다.
g(n)이 증가함에 따라, f(n)이 같거나 작아야 하는 것이고, 나머지도 비슷하게 이해할 수 있을 것이다.
big-O로 표기되는 대표적인 경우들은 다음과 같다.
O(1)
- 입력 값이나, 사용되는 데이터에 관계 없는 경우. g(n)= k 와 같이 상수인 경우, n을 입력해도 처리되는 경우의 수가 같은 경우다. 일반적으로 반복문이 없는 경우라고 보면 쉽다.O(log n)
- 입력 값 n에 비해 시간이 조금씩 증가하는 경우. binary search 와 같이 문제를 해결하는 과정에서 경우의 수를 나누어 풀거나 하는 방식등으로 경우의 수를 줄여 나가는 경우들이라고 볼 수 있다.O(n)
- 입력 값 n과 동등한 시간 관계를 갖는 경우. g(n)= n 와 같은 경우, 반복문을 중첩하여 사용하지 않는 경우라고 보면 된다. for(int i=0; i<n; i++)와 같은 반복문은 g(n) = n이라고 볼 수 있으므로..O(n^2)
- 입력 값 n에 제곱의 시간을 필요로 하는 경우. 위와 같은 반복문을 이중 사용하는 경우, n개의 처리를 필요로 하는 반복문에서 n개의 반복을 요구하므로 g(n) =n^2가 된다.O(k^n)
- 입력 값 n에 따라 기하급수적 시간을 필요로 하는 경우. 쓰레기를 만들었다고 보면 된다. 절대적으로 개선을 해야한다. 예를들어 k=2이고, n=20이라 가정하면, 위의 20^n에서는 400에 불과하지만, 2^20의 경우엔 1,000,000이 넘는 연산을 요구로 하기 때문에, 절대 사용되선 안된다고 볼 수 있다.O(n!) , O(n^n)
- 더 큰 쓰레기들을 깜빡 했다. factorial과, 그보다 더 쓰레기 n의 n승이다.위의 대표적 사례에서 사실 O(n)과 O(n^2) 같은 경우는 이해하기 쉽다. 반복문의 개수라고 보면 쉽기 때문이다. 다른 경우는 어떻게 시간 복잡도를 구할지 알아보자.
Master Theorem
logn이나 nlogn과 같은 시간 복잡도 계산을 위해서 master theorem을 사용한다. 이는 모든 경우에서 사용되는 것은 아니지만, 대부분 계산 가능하다.
위의 내용이 master theorem의 수식인데, 보자하니 살짝 어렵다. 설명 간다.
master theorem은 우선 재귀함수(recursive function)에서 사용된다.
T(n)은 재귀함수가 어떻게 사용되는가 하는 것이다.
a는 재귀함수 내에서 몇개의 재귀함수를 호출하는가 하는 것이고, b는 몇개로 나누어 푸는가 하는 것이다.
d는 재귀함수 내에서 나머지 코드들의 시간복잡도를 의미한다. 여기서 반복문이 하나 사용되면 n^1이니까, d는 1이 되겠지.
참. 쉽다.
예를 들어 보자. // binarysearch로 간다.
binarysearch는 아시지요?
전체에서 중간 잡고 비교해서 작으면 작은쪽 절반, 크면 큰쪽 절반을 잡고, 다시 그 중 중간 잡고 큰쪽 작은쪽.. 쭉쭉...
그렇다. binarysearch는 재귀함수로 하면, recall이 1개, n개의 데이터는 n/2로 나뉘고, 별도의 코드 시간복잡도는 n^0이다. 따라서 a=1, b=2, d=0.
위에서 넣으면, a=b^d(1=2^0)이니까, n^d*log n이고, d=0이므로 log n.
EmoticonEmoticon