Big-O

Big-O 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 표현하는 수학적 표기법으로, 알고리즘이 입력크기에 따라 얼마나 빠르게 실행되는지(시간 복잡도) 및 얼마나 많은 메모리를 사용하는지(공간 복잡도)를 나타낸다!

-> 이를 통해 여러 알고리즘의 효율성 분석하고 비교할 수 있다!

Big-O의 주 개념

  1. 시간 복잡도(Time Complexity):
    알고리즘이 실행되는 데 걸리는 시간을 입력 크기의 함수로 표현
    예: O(n), O(n²), O(log n) 등.

  2. 공간 복잡도(Space Complexity):
    알고리즘이 실행되는 데 필요한 메모리 공간을 입력 크기의 함수로 표현
    예: O(1), O(n), O(n²) 등.

  3. 최악의 경우(Worst Case):
    Big-O는 알고리즘의 최악의 경우를 가정하여 성능을 평가
    예: 배열에서 특정 값을 찾는 알고리즘의 최악의 경우는 배열의 끝까지 탐색하는 것

여러 표기법

  1. O(1) - 상수 시간(Constant Time): 입력 크기와 상관없이 항상 일정한 시간이 걸림

  2. O(n) - 선형 시간(Linear Time): 입력 크기에 비례하여 시간이 증가

  3. O(log n) - 로그 시간(Logarithmic Time): 입력 크기가 커질수록 시간이 로그적으로 증가

  4. O(n log n) - 선형 로그 시간(Linearithmic Time): 입력 크기와 로그 시간의 곱에 비례하여 시간이 증가

  5. O(n²) - 제곱 시간(Quadratic Time): 입력 크기의 제곱에 비례하여 시간이 증가

  6. O(2^n) - 지수 시간(Exponential Time): 입력 크기에 대해 지수적으로 시간이 증가

  7. O(n!) - 팩토리얼 시간(Factorial Time): 입력 크기의 팩토리얼에 비례하여 시간이 증가

정렬

버블 정렬(Bubble Sort)

  • 인접한 두 요소를 비교하며 큰 값을 오른쪽으로 이동시키며, 이 과정을 반복하여 정렬하는 방식

  • 시간 복잡도: O(n²) (Big-O 표기법에서는 최고차항만 고려하고 상수는 무시하므로 최악, 평균, 최선 모두 동일).

  • 공간 복잡도: O(1) (제자리 정렬).

function bubbleSort(arr) {
  for (let i = 0; i < arr.length;i++) {
    // 진행될 수록 맨 오른쪽 값은 확정이 됨
    for (let j = 0; j < arr.length - i - 1;j++) {
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
  return arr;
}

선택 정렬(Selection Sort)

  • 가장 작은 값을 찾아 맨 앞으로 이동시키며, 이 과정을 반복하여 정렬하는 방식

  • 시간 복잡도: O(n²) (최악, 평균, 최선 모두 동일)

  • 공간 복잡도: O(1) (제자리 정렬)

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

삽입 정렬(Insertion Sort)

  • 요소를 하나씩 선택해 적절한 위치에 삽입하는 과정을 반복하는 방식

  • 시간 복잡도: O(n²) (최악, 평균) O(n)( 최선: 정렬된 배열)

  • 공간 복잡도: O(1) (제자리 정렬)

function insertionSort(arr) {
  for (let i = 1;i < arr.length;i++) {
    const current = arr[i];
    let j = i-1;
    while(j >= 0 && arr[j] > current) {
      // j+1(이전값) 에 j(현재값)을 삽입
      // 한칸씩 앞으로 미는 효과
      arr[j+1] = arr[j];
      j--;
    }
    // current 값이 arr[j] 보다 크면 arr[j+1]에 삽입
    // current(비교가 되는 값)보다 작은 수의 앞에 두는 효과
    arr[j+1] = current;
  }
  return arr 
}

병합 정렬(Merge Sort)

  • 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후 병합하는 방식

  • 시간 복잡도: O(n log n) (최악, 평균, 최선 모두 동일)

  • 공간 복잡도: O(n) (추가 메모리 필요)

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    // 왼쪽, 오른쪽을 비교하여 숫자를 정렬하며 삽입
    if (left[0] < right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return result.concat(left, right);
}

function mergeSort(arr) {
  // 배열의 길이가 1이하인 경우 재귀의 마무리 시점
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length /2);
  // 재귀적 분할 
  const left = mergeSort(arr.slice(0,mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left,right);
}

퀵 정렬(Quick Sort)

  • 피벗을 선택하고, 피벗보다 작은 값과 큰 값으로 배열을 나눈 후 재귀적으로 정렬하는 방식

  • 시간 복잡도: O(n log n) (평균), O(n²) (최악: 피벗 선택이 나쁜 경우)

  • 공간 복잡도: O(log n) (재귀 호출 스택)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i =1; i < arr.length;i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  // 재귀로 Pivot을 기준으로 왼쪽과 오른쪽으로 계속해서 정렬
  return [...quickSort(left), pivot, ...quickSort(right)];
}

힙 정렬(Heap Sort)

  • 배열을 힙으로 변환한 후, 힙에서 최대값/최솟값 을 추출하여 정렬하는 방식

Image

  • 시간 복잡도: O(n log n) (최악, 평균, 최선 모두 동일)

  • 공간 복잡도: O(1) (제자리 정렬)

// 재귀 Heap 정렬
function heapify(arr, i, size) {  
  let largest = i;  
  // 하위 heap의 index 주소
  const left = 2 * i + 1;  
  const right = 2 * i + 2;  
  // 하위 heap이 더 클 경우 상위 heap과 교체 + 재정렬
  if (left < size && arr[left] > arr[largest]) largest = left;  
  if (right < size && arr[right] > arr[largest]) largest = right;  
  if (largest !== i) {  
    [arr[i], arr[largest]] = [arr[largest], arr[i]];  
    heapify(arr, largest, size);  
  }  
}  

function buildMaxHeap(arr) {  
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {  
    heapify(arr, i, arr.length);  
  }  
}  

function heapSort(arr) {  
  buildMaxHeap(arr);  
  // 최댓값 arr[0] 과 하위 heap들을 비교하며 정렬
  for (let i = arr.length - 1; i > 0; i--) {  
    [arr[0], arr[i]] = [arr[i], arr[0]];  
    heapify(arr, 0, i);  
  }  
  return arr;  
}

DFS 와 BFS

그래프 탐색 알고리즘 중 대표적인 DFS(Depth-First Search)와 BFS(Breadth-First Search)은 각각 다른 방식으로 그래프를 탐색한다!

DFS(깊이 우선 탐색)

  • 그래프의 깊이를 우선으로 탐색하는 방식으로 일종의 미로를 한쪽벽면을 따라 이동하는 것과 비슷한 방식입니다!

  • 여러 길을 탐색하는 것보단, 하나의 목표지점을 구할 때 사용합니다.

  • 그래프의 깊이가 매우 깊을 경우, 오버플로우가 발생할 수 있습니다.

BFS(너비 우선 탐색)

  • 그래프의 너비를 우선으로 탐색하는 방식으로 물이 퍼지듯 여러 갈래 길들을 탐색하는 방식입니다.

  • 시작지점부터 여러 길을 탐색해가며, 최단경로를 구하는데 주로 사용합니다.

  • 그래프가 넓어질 수록 대기열에 저장되는 노드의 수가 많아져, 메모리 사용량이 증가합니다.