(BigO),(정렬의 종류) 본캠프 TIL 02/19

11 번째 질문 BigO에 대해 설명해주세요

**Big-O(빅오 표기법)**는 알고리즘의 시간 복잡도 또는 공간 복잡도를 표현하는 표기법으로, 입력 크기(n)에 따른 알고리즘의 성능을 **최악의 경우(Worst Case)**를 기준으로 나타냅니다.

 

 

 

핵심 개념: 알고리즘이 얼마나 효율적으로 실행되는지 **점근적 상한(Asymptotic Upper Bound)**으로 표현합니다.


O(1): 상수 시간 (배열 인덱스 접근)

O(n): 선형 시간 (단일 반복문)

O(n²): 2차 시간 (중첩 반복문)

O(log n): 로그 시간 (이진 탐색)

O(n log n): 선형 로그 시간 (병합 정렬)

 

예상 꼬리 질문 

 

Q: 왜 최선의 경우(Best Case)가 아닌 최악의 경우를 사용하나요?
A: 최악의 경우를 통해 알고리즘의 성능을 보장받을 수 있어, 시스템의 안정성을 예측할 수 있습니다.

 

Q: O(n²) 알고리즘을 개선하는 방법은?
A: 더 효율적인 알고리즘(예: O(n log n))으로 대체하거나, 불필요한 연산을 최적화합니다.

 

 12번째 질문다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요
    - 선택 정렬(Selection Sort)
    - 버블 정렬(Bubble Sort)
    - 병합 정렬(Merge Sort)
    - 삽입 정렬(Insertion Sort)
    - 퀵 정렬(Quick Sort)
    - 힙 정렬(Heap Sort)

 

(1) 선택 정렬 (Selection Sort)

동작 방식

1. 배열에서 최솟값을 찾습니다.

2. 해당 값을 배열의 맨 앞과 교체합니다.

남은 부분에 대해 반복합니다.

시간 복잡도: O(n²) (모든 경우)

 

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

 

(2) 버블 정렬 (Bubble Sort)

인접한 두 요소를 비교하여 교체합니다.

한 번의 패스마다 가장 큰 값이 끝으로 이동합니다.

시간 복잡도: O(n²) (최적화 시 최선 O(n))

 

(3) 병합 정렬 (Merge Sort)

배열을 절반으로 분할합니다.

각 부분을 재귀적으로 정렬합니다.

정렬된 부분을 병합합니다.

시간 복잡도: O(n log n)

 

(4) 삽입 정렬 (Insertion Sort)

두 번째 요소부터 시작해 앞의 정렬된 부분에 삽입합니다.

적절한 위치를 찾아 요소를 이동시킵니다.

시간 복잡도: 최선 O(n), 평균 및 최악 O(n²)

 

(5) 퀵 정렬 (Quick Sort)

피벗을 선택합니다.

피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다.

분할된 부분을 재귀적으로 정렬합니다.

시간 복잡도: 평균 O(n log n), 최악 O(n²)

 

(6) 힙 정렬 (Heap Sort)

동작 방식

배열을 최대 힙(Max Heap)으로 변환합니다.

힙의 루트(최대값)를 배열 끝으로 이동합니다.

힙 크기를 줄이고 힙 속성을 복원합니다.

시간 복잡도: O(n log n)

 

예상 꼬리질문 

 

Q: 퀵 정렬의 최악의 경우를 피하는 방법은?
A: 피벗을 무작위로 선택하거나, 중간값을 선택합니다.

 

Q: 실무에서 어떤 정렬을 주로 사용하나요?
A: 데이터 크기가 클 경우 O(n log n)인 병합/퀵 정렬, 작을 경우 삽입 정렬을 사용합니다.