빠 른 정렬 과 병합 정렬 의 시간 복잡 도 분석 - 알 기 쉽다.

머리말
    오늘 면접 에서 서열 을 정리 하 는 시간 이 복잡 하 다 는 질문 을 받 았 습 니 다. 이것 은 모두 가 O（nlogn） 이라는 것 을 알 고 있 지만 면접 관 은 계속 물 었 습 니 다. 어떻게 유도 하 느 냐 고 물 었 습 니 다.이 시간 복잡 도가 어떻게 나 왔 는 지 제대로 이해 하지 못 했 기 때문에 대충 대답 했다.
    병합 정렬 과 빠 른 정렬 은 알고리즘 에서 매우 중요 한 두 가지 지식 점 이자 면접 에서 매우 자주 묻 는 내용 입 니 다. 저 는 이 럴 줄 알 면서 도 철저하게 이해 하지 못 했 습 니 다. 정말 해 서 는 안 됩 니 다.그래서 오늘 이 블 로 그 는 이 두 가지 정렬 알고리즘 의 시간 복잡 도가 어떻게 나 왔 는 지 분석 해 보 자.저 는 많은 블 로 그 를 찾 아 봤 습 니 다. 많은 것 이 공식 을 통 해 분석 되 었 고 이해 하기 어 려 웠 습 니 다. 다음은 제 이해 와 결합 하여 통속 적 이 고 알 기 쉬 운 방식 으로 설명 하 겠 습 니 다.
본문
2.1 병합 정렬 의 시간 복잡 도 분석
* 8195 ° 8195 ° 귀 합 된 순 서 를 아 는 사람 은 모두 알 아야 한다. 귀 합 된 순서 의 시간 복잡 도 는 O（nlogn） 이 고 이 시간 복잡 도 는 안정 적 이 며 정렬 이 필요 한 순서 에 따라 변동 이 생기 지 않 는 다.그럼 이 시간의 복잡 도 는 어떻게 얻 은 것 일 까?우 리 는 이렇게 분석 할 수 있다. 만약 에 우리 가 n 개의 수 를 포함 하 는 서열 에 대해 병합 순 서 를 사용 하고 재 귀적 인 실현 방식 을 사용 해 야 한다 고 가정 하면 과정 은 다음 과 같다.

재 귀 1 층 은 n 개 수 를 2 개 구간 으로 나 누고 각 하위 구간 의 숫자 개 수 는 n/2 이다.

재 귀 하 는 2 층 은 n 개 수 를 4 개 구간 으로 나 누고 각 하위 구간 의 숫자 개 수 는 n/4 이다.

재 귀적 인 3 층 은 n 개 수 를 8 개 구간 으로 나 누고 각 하위 구간 의 숫자 개 수 는 n/8 이다.

  ......

재 귀 된 logn 층 은 n 개 수 를 n 개 구간 으로 나 누고 각 하위 구간 의 숫자 개 수 는 1 이다.

* 8195: 8195: 우 리 는 정리 하고 정렬 하 는 과정 에서 현재 구간 을 반 으로 나 누 어 구간 의 길이 가 1 이 될 때 까지 해 야 한 다 는 것 을 알 고 있다.각 층 의 하위 구간 은 길이 가 윗 층 의 1/2 인 셈 이다.이 는 로그 n 층 으로 나 눌 때 하위 구간 의 길이 가 1 이라는 뜻 이다.한편, 정렬 된 merge 작업 은 최 하층 부터 (자 구간 은 1 의 층) 인접 한 두 자 구간 을 합병 하 는 과정 은 다음 과 같다.

은 logn 층 (최 하층) 에서 각 자 구간 의 길 이 는 1 으로 총 n 개 구간 을 인접 한 두 자 구간 마다 합병 하여 총 n/2 회 합병 했다.n 개의 숫자 가 한 번 씩 옮 겨 다 니 는데 이 층 의 전체 시간 복잡 도 는 O（n） 이다.

  ......

은 2 층 에서 각 자 구간 의 길 이 는 n/4 으로 모두 4 자 구간 이 있 으 며, 인접 한 두 자 구간 마다 합병 하여 총 2 회 를 합병 하 였 다.n 개의 숫자 가 한 번 씩 옮 겨 다 니 기 때문에 이 층 의 총 시간 복잡 도 는 O（n） 이다.

은 1 층 에서 각 자 구간 의 길 이 는 n/2 으로 모두 2 자 구간 이 있 으 며 한 번 만 합병 하면 된다.n 개의 숫자 가 한 번 씩 옮 겨 다 니 기 때문에 이 층 의 총 시간 복잡 도 는 O（n） 이다.

종가시나무 는 위의 과정 을 통 해 우 리 는 각 층 에 있어 모든 하위 구간 을 합병 하 는 과정 에서 n 개의 요소 가 한 번 씩 조작 되 기 때문에 각 층 의 시간 복잡 도 는 O（n） 이라는 것 을 알 수 있다.앞서 우 리 는 분자 구간 을 정리 하고 정렬 하 며 자 구간 을 1 개의 요소 로 나 누 려 면 logn 번 을 나 누 어야 한다 고 말 했다.각 층 의 시간 복잡 도 는 O (n) 이 고 모두 logn 층 이 있 기 때문에 정렬 하 는 시간 복잡 도 는 O (nlogn) 이다.
    위의 묘 사 는 매우 상세 한 셈 이 니 이해 하기 어렵 지 않 을 것 이다.위의 과정 이 이해 되 지 않 는 다 면 우 리 는 다른 직관 적 인 방식 으로 분석 할 것 이다.위 에서 묘사 한 것 은 재 귀적 인 과정 이다. 아래 에서 우 리 는 비 재 귀적 (교체) 방식 으로 이 루어 진 병합 순 서 를 통 해 다시 한 번 분석 한 다음 에 이런 방식 이 더욱 직관 적 이다 (왜 직접 비 재 귀적 인 방식 으로 묘사 하지 않 고 먼저 재 귀적 인 방식 으로 분석 하 는 것 은 위의 과정 도 빠 른 순 서 를 분석 할 수 있 기 때문이다).다음은 비 재 귀 방식 으로 이 루어 진 병합 정렬 코드 입 니 다. 그 중에서 시간 복잡 도 를 분석 하 는 두 가지 관건 이 있 습 니 다. 저 는 표 시 했 습 니 다 (주석 에 중점 을 두 었 습 니 다).

/**
 *             ，      1->2->4->8 ... ->n/2
 *           logn 
 */
public static void merge(int[] arr) {
    //    1：     ，                ，          logn 
    for(int i = 1;i=arr.length?arr.length-1:start2+gap-1;
    while(start2=arr.length?arr.length-1:start2+gap-1;
    }
    while(start1

    위의 코드 는 merge 방법 중의 순환 은 logn 회 순환 해 야 하고 매번 순환 할 때마다 mergeSort 방법 을 한 번 호출 해 야 한다. mergeSort 방법의 시간 복잡 도 는 O（n） 이기 때문에 병합 정렬 의 시간 복잡 도 는 O（nlogn） 이다.
2.2 빠 른 정렬 시간 복잡 도
    빠 른 정렬 을 알 아야 한다. 빠 른 정렬 의 시간 복잡 도 는 O（nlogn）~ O（n^2） 사이 에 있다. 다음은 내 가 이 두 가지 상황 을 분석 하 겠 다.
(1) 빠 른 정렬 의 가장 좋 은 상황 O (nlogn)
    이런 상황 에서 사실은 위 에서 재 귀적 분석 을 통 해 분류 한 것 과 비슷 하고 분류 하 는 시간 복잡 도 분석 을 이해 했다. 그러면 여기 도 잘 이해 할 수 있 을 것 이다.빠 른 정렬 의 실현 방식 은 현재 구간 에서 하나의 축 을 선택 하 는 것 이다. 구간 의 모든 축 보다 작은 수 는 축의 왼쪽 에 놓 아야 하고 축 보다 큰 수 는 축의 오른쪽 에 놓 아야 한다.이상 적 인 상황 에서 우리 가 선택 한 축 은 바로 이 구간 의 중위 수 이다.조작 직후 마침 구간 을 숫자 개수 가 같은 좌우 두 개 구간 으로 나 눈 셈 이다.이 때 병합 정렬 과 거의 일치 합 니 다.

재 귀적 인 1 층, n 개 수 는 2 개 구간 으로 나 뉘 었 고 각 하위 구간 의 숫자 개 수 는 n/2 이다.

재 귀적 인 2 층, n 개 수 는 4 개 구간 으로 나 뉘 었 고 각 하위 구간 의 숫자 개 수 는 n/4 이다.

재 귀적 인 3 층, n 개 수 는 8 개 구간 으로 나 뉘 었 고 각 하위 구간 의 숫자 개 수 는 n/8 이다.

  ......

재 귀 된 logn 층, n 개 수 는 n 개 구간 으로 나 뉘 었 고 각 하위 구간 의 숫자 개 수 는 1 이다.

『 8195 』 이상 의 과정 과 병합 순 서 는 대체적으로 일치 하 는데 차이 점 은 병합 순 서 는 마지막 층 부터 merge 작업 을 하고 밑 에서 위로 하 는 것 이다.빠 른 정렬 은 1 층 부터 구간 의 숫자 를 교환 하 는 위치, 즉 위 에서 아래로 한다.그러나 merge 작업 과 빠 른 정렬 의 위치 변경 작업 은 시간 복잡 도 는 같 으 며 각 구간 에 대해 처리 할 때 한 번 구간 의 모든 요 소 를 옮 겨 다 녀 야 한다.이 는 빠 른 정렬 과 병합 정렬 과 마찬가지 로 각 층 의 총 시간 복잡 도 는 O（n） 이다. 모든 요 소 를 한 번 씩 옮 겨 다 녀 야 하기 때문이다.그리고 가장 좋 은 경우 에 도 logn 층 이 있 기 때문에 빠 른 정렬 의 가장 좋 은 시간 복잡 도 는 O（nlogn） 이다.
(2) 빠 른 정렬 의 최 악의 경우 O (n ^ 2)
    다음은 빠 른 정렬 의 최 악의 상황 을 다시 한 번 말씀 드 리 면 이해 하기 쉽 습 니 다.빠 른 정렬 의 최 악의 상황 은 무엇 입 니까? 그것 은 모든 구간 에 대해 우리 가 처리 할 때 선택 한 축 이 바로 이 구간 의 최대 치 나 최소 치 입 니 다.예 를 들 어 우 리 는 n 개의 수 를 정렬 해 야 하 는데 매번 처리 할 때 선택 한 축 은 구간 의 최소 값 이다.그래서 첫 번 째 조작 은 원소 의 순 서 를 바 꾸 는 조작 을 한 후에 최소 값 은 첫 번 째 위치 에 놓 였 고 나머지 n-1 개 수 는 2 n 개의 위 치 를 차지 했다.두 번 째 조작 은 남 은 n-1 개의 요 소 를 처리 하고 이 하위 구간 의 최소 치 를 현재 구간 의 1 번 째 위치 에 두 었 습 니 다. 이런 식 으로 유추 하면... 매번 조작 할 때마다 최소 치 를 첫 번 째 위치 에 만 놓 을 수 있 고 나머지 요 소 는 변화 가 없습니다.그래서 n 개의 수 에 있어 n 번 을 조작 해 야 n 개의 수 를 정렬 할 수 있다.그리고 매번 조작 할 때마다 남 은 모든 요 소 를 옮 겨 다 녀 야 한다. 이 작업 의 시간 복잡 도 는 O（n） 이기 때문에 총 시간 복잡 도 는 O（n^2） 이다.
    사실 위의 과정 을 우 리 는 다른 각도 로 이해 할 수 있다. 매번 조작 할 때마다 최소 치 를 찾 아 나머지 구간 의 첫 번 째 위치 에 놓 는 것 이 바로 정렬 의 실현 방식 을 선택 하 는 것 이 아닌가?정렬 을 선택 하 는 시간 복잡 도 는 O（n^2） 이기 때문에 위의 과정 도 O（n^2） 이다.
3. 총화
* 8195 ° 이상 의 내용 은 바로 제 가 자신의 이 해 를 바탕 으로 빠 른 정렬 과 병합 정렬 시간 복잡 도 에 대한 분석 입 니 다.더 잘 이해 하기 위해 서 나의 묘 사 는 가능 한 한 상세 하기 때문에 좀 지루 할 수 있 지만, 나 는 여전히 매우 통속 적 이 고 이해 하기 쉽다 고 생각한다.이 블 로 그 는 이전에 이 두 가지 정렬 알고리즘 에 대한 이해 가 뚜렷 하지 않 은 사람 에 게 도움 을 줄 수 있 기 를 바 랍 니 다. 또한 위의 내용 에 오류 가 있 거나 부족 하면 지적 하거나 보충 하 는 것 을 환영 합 니 다.