T(Divide) = 0 이다.
진짜야. Divide에 시간이 안 걸린다는 뜻이다. 지난번 탐색알고리즘에서는 탐색하는 과정에서 비교연산을 해야하기때문에
그냥 직접적으로 S[0] 부터 S[n/2] 까지, S[n/2+ 1]부터 S[n]까지 식으로 해당 인덱스만 기억하면 되는 것이다.
물론 코드로 이렇게 인덱스를 바로 기억하도록 짜려면 상당히 어려울 것이지만...
엄밀히는 Copy는 반드시 필요한 과정은 아니기 때문에 시간복잡도 분석에서 제외된다.
T(Solve) = 2 * T(n/2) 이 맞다. 왼쪽, 오른쪽 자른 놈들을 다시 해결하는데 걸리는 시간을 계산하면 되기때문에 각각
T(n/2)(왼쪽) + T(n/2)(오른쪽) 을 더하면 2 * T(n/2)이 되는 것이다.
T(Combine) = n - 1 이다. 왼쪽 오른쪽을 갈라놓고, 하나하나 비교하는 연산을 하면, 최악의 경우 n/2 + (n/2 -1)이 된다.
-1이 되는 이유는 맨 마지막 한 놈은 그냥 내려오기 때문이다. 따라서 정리하면 T(Combine) = n - 1 이다.
n이 매우 큰 수라고 가정한다. n = 2^k or 2^k + 1 (짝수, 홀수 둘 다 될 수 있으므로, 하지만 1이 거의 의미가 없다. 따라서 그냥 편의상 n = 2^k라고 가정하자)
그리고 식을 정리하면,
= n*T(1) + nlogn이 된다. 마지막으로 큰 실수를 하면 안되는게, 지난번 탐색알고리즘 처럼 생각하고 T(1) = 1 이라고 하면 안된다!
지금은 '탐색'이 아닌 '정렬'을 하고있고, 1개의 데이터를 정렬하는 시간은 0초이다. 1개를 탐색할때는 비교를 1번 해야하니까 1이고.
따라서 T(1)이 0이므로, 최종적으로 식을 정리하면
'Algorithm > Etc' 카테고리의 다른 글
Quick sort(퀵 정렬) (0) | 2020.09.11 |
---|---|
에라토스테니스의 체 (0) | 2020.09.06 |
[관계기반] 숫자 뒤집기(p.18) (0) | 2020.09.01 |
관계 기반 알고리즘 설계 (0) | 2020.09.01 |
[DFS] 돌다리 건너기(p.239) (0) | 2020.08.31 |