op06072   3년 전

예를 들어 10개의 데이터가 든 배열을 분할 시 

10

5, 5

3, 2, 5 -> 3, 2, 3, 2

2, 1, 2, 3, 2 -> 2, 1, 1, 1, 3, 2 -> 2, 1, 1, 1, 2, 1, 2 -> 2, 1, 1, 1, 2, 1, 1, 1

1, 1, 1, 1, 1, 2, 1, 1, 1 -> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

해서 9번이고 다른경우도 n개를 분할 시 n-1번 분할되고 분할깊이라 해야할까요? log2n이고 각 단계마다 깊이가 k일때 정렬된 두 배열을 합칠때 예를 들어

3, 4 / 1, 2에서 3과 1을 비교, 3과 2를 비교하여 2번이고 2, 4 / 1, 3에서와 같이 2, 1을 비교, 2, 3을 비교, 3, 4를 비교해도 아무리 많아도 n/(2k) -1이 되고 그것을 2k회 시행하니 n-2k가 되기에 울프람알파식으로 적자면 (sum (n-2^k), from 1 to log2(n)) + n - 1이 되므로 nlog2n - n + 1이 되어야한다고 생각하는데 실제로 해보면 길이가 4인 배열에서도 답이 맞지 않습니다. 제가 무엇을 잘못 생각한 것일까요?

op06072   3년 전

(sum (n-2^k), from 0 to log2(n)) + n - 1을 해야되네요. 더 자세하게 생각해보면 알 수 있던거였네요.

댓글을 작성하려면 로그인해야 합니다.