분할정복 (1) 썸네일형 리스트형 Devide and Conquer(mergeSort) 재귀 알고리즘 설계를 기반으로 한다. 따라서 1. 탈출조건 2. 각 하위문제는 본문제보다 작은 문제여야한다. 위 두조건을 만족해야한다. 3단계로 간단히 말하면 1. 분할 : n크기의 배열을 n/2크기의 하위배열 2개로 나눔 2. 정복 : 배열의 크기 1이 될때까지 반복해 재귀적으로 정렬함. 3. 결합 : 하위배열을 합해서 정렬함. 시간 복잡도 1. 분할 : 중간값을 구함, (상수시간) O(1) 2. 정복 : 재귀 횟수는 트리의 level인 log2n임. 3. 결합 : 정렬된 하위배열 요소들을 한번씩 비교후 정렬함 O(n) 각 트리 계층마다 O(n)번의 연산을 하므로 시간복잡도는 트리의 level(재귀횟수) * O(n) 이다. O(nlogn) 이전 1 다음