Complexity Analysis

Coddy의 버블 정렬 코스 레슨 — 11개 중 5번째.

버블 정렬의 복잡도 분석.

시간 복잡도는 수행된 비교 및 교환 횟수에 따라 달라집니다.

우리는 n번의 패스(pass)를 수행해야 하며, 각 패스마다 (n-1)번의 비교를 수행합니다. 여기서 n은 리스트의 요소 수입니다.

총 비교 횟수=(n-1)+(n-1)+(n-1)....n번

=n*(n-1)

=n²-n

버블 정렬 알고리즘의 시간 복잡도는 O(n²)입니다.

만약 공간 복잡도에 대해 이야기하자면, 알고리즘에서 추가적인 공간은 사용되지 않으며, 제자리(in-place) 정렬이 수행되어 요소들이 원래 리스트 자체에서 정렬됩니다.

버블 정렬 알고리즘의 공간 복잡도는 O(1) (상수)입니다.

챌린지

쉬움

배열과 배열의 크기를 전달받는 count_swaps라는 이름의 함수를 생성하세요. 배열에 대해 버블 정렬 알고리즘을 수행하고 교환이 수행된 횟수를 계산하세요.

직접 해보기

#include <stdio.h>
#include <stdlib.h>

int count_swaps(int* arr, int arr_size, int n) {
    // 여기에 코드를 작성하세요
    return 0;
}

버블 정렬의 모든 레슨

1Basics of Bubble Sort

2Analysis

Complexity AnalysisAdaptivity Stability

3Practice Challenges