밍의 기록들😉

합병 정렬 개념배열을 절반으로 나누어 각각을 정렬한 후, 합친다. 합병 정렬의 시간복잡도재귀적으로 구해야 한다.1. 왼쪽 합병정렬 = T(n/2)2. 오른쪽 합병정렬 = T(n/2)3. 합친다 = O(n) * T(n) = n개의 숫자를 합병정렬할 때의 시간복잡도* T(n) = 2 x T(n/2) + O(n) // 점화식 = 2(2T(n/4) + O(n/2)) + O(n) = 4T(n/4) + 2O(n) // 1번 대입 = 4(2T(n/8) + O(n/4)) + 2O(n) = 8T(n/8) + 3O(n) // 2번 대입 ...... // k번 대입 k+1 = log n = n x T(1) + log n x O(n) = n x O(1) + O(n log n) = O(n) + O(n log n) * 합병 정렬..