정렬 시간복잡도 구해보기

시간복잡도 분석

선택 정렬의 시간복잡도는 O(n²)입니다. 이는 다음과 같은 분석을 통해 도출됩니다:

외부 루프 (i): n번 반복

•

내부 루프 (j): (n-i)번 반복

따라서 전체 연산 횟수는:

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

이 수식이 나오는 과정을 살펴보면:

•

첫 번째 반복에서는 (n-1)번 비교

•

두 번째 반복에서는 (n-2)번 비교

•

세 번째 반복에서는 (n-3)번 비교

이런 식으로 계속되어 마지막에는 1번 비교하게 됩니다.

이는 등차수열의 합 공식으로 계산할 수 있습니다:

선택정렬

시간복잡도 분석

버블 정렬의 시간복잡도는 O(n²)입니다. 이는 다음과 같은 분석을 통해 도출됩니다:

•

외부 루프 (i): n-1번 반복
    • 배열을 처음부터 끝까지 순회

•

내부 루프 (j): (n-i-1)번 반복
    • 첫 번째 반복: n-1번 비교
    • 두 번째 반복: n-2번 비교
    • 마지막 반복: 1번 비교

따라서 전체 연산 횟수는:

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}

최종적으로 O(n²)가 됩니다.

공간복잡도

버블 정렬의 공간복잡도는 O(1)입니다. 추가적인 메모리 공간을 거의 사용하지 않고 주어진 배열 내에서 원소들의 위치만 교환하기 때문입니다.

특징

•

안정성: 안정 정렬 (같은 값을 가진 요소들의 상대적 순서가 유지됨)

•

제자리 정렬: 추가 메모리 공간 필요 없음

•

시간복잡도
    • 최선의 경우: O(n) - 이미 정렬된 경우
    • 평균의 경우: O(n²)
    • 최악의 경우: O(n²) - 역순으로 정렬된 경우

버블정렬

시간복잡도 분석

삽입 정렬의 시간복잡도는 다음과 같습니다:

•

최선의 경우: O(n) - 배열이 이미 정렬되어 있는 경우

•

평균의 경우: O(n²)

•

최악의 경우: O(n²) - 배열이 역순으로 정렬되어 있는 경우

시간복잡도 O(n²)가 나오는 과정:

•

외부 루프는 n-1번 실행 (i는 1부터 n-1까지)

•

내부 루프는 최악의 경우 i번 실행

•

따라서 총 비교 횟수는: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2

\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}

따라서 빅오 표기법으로 O(n²)가 됩니다.

분할 과정: 배열을 반으로 나누는 과정이 log n번 발생

•

병합 과정: 각 레벨에서 n개의 원소를 병합하는 데 O(n)의 시간이 소요

따라서 전체 시간복잡도는 O(n) × O(log n) = O(n log n)이 됩니다.

분할 과정

배열을 반으로 나누는 과정이 log n번 발생하는 이유는 다음과 같습니다:

1.

첫 번째 분할: n크기의 배열을 n/2 크기로 나눔

2.

두 번째 분할: n/2 크기의 배열들을 n/4 크기로 나눔

3.

세 번째 분할: n/4 크기의 배열들을 n/8 크기로 나눔

4.

이런 식으로 계속 진행되어 배열의 크기가 1이 될 때까지 분할

이처럼 매 단계마다 배열의 크기가 절반으로 줄어들기 때문에, n에서 1까지 도달하는데 필요한 분할 횟수는 log₂n이 됩니다. 예를 들어, 크기가 8인 배열은 8 → 4 → 2 → 1로 3번(log₂8 = 3)의 분할이 필요합니다.

병합정렬

시간복잡도 분석

퀵정렬의 시간복잡도는 다음과 같습니다:

•

최선의 경우: O(n log n) - 피벗이 항상 중간 값으로 선택되는 경우

•

평균의 경우: O(n log n) - 일반적인 상황에서의 성능

•

최악의 경우: O(n²) - 이미 정렬된 배열이나 피벗이 항상 최소/최대값인 경우

O(n²) 시간복잡도 분석

최악의 경우 O(n²)가 되는 과정을 분석해보겠습니다:

1. 분할(Partition) 과정

•

매 분할마다 전체 배열을 순회: O(n)

•

이미 정렬된 배열에서 최소/최대값이 피벗으로 선택될 경우:

2. 재귀 호출 과정

•

불균형 분할로 인해 n번의 재귀 호출 발생

퀵정렬