빅 오 표기법(Big O Notation)

📒 오늘의 공부

빅 오 표기법(Big O Notation)

1. 빅 오 표기법(Big O Notation)이란?

• 알고리즘의 효율성을 평가하고, 프로그램의 성능을 예측하는 데 사용되는 개념이자 알고리즘이 입력 크기에 따라 어떻게 증가하는지를 간결하게 표현하는 방법

• O(f(n))으로 표기

  • O는 빅 오(O) 기호를 의미
  • f(n)은 알고리즘의 입력 크기 n에 따라 실행 시간 또는 메모리 공간 사용량이 어떻게 변하는지를 설명하는 함수
    ex. O(n)은 입력 크기 n에 비례하여 증가하는 시간 복잡도를 의미

• 빅 오 표기법을 쓰는 이유

  • 빅 오 표기법은 코드의 성능을 비교하고 분석하는 강력한 도구
  • 시간 측정을 사용하여 코드 실행 시간을 측정할 수는 있지만, 코드의 실행 시간은 매우 다양한 요인에 영향을 받을 수 있다.
    또한 1번 코드가 1시간 걸리고 2번 코드가 4시간 걸린다면 시간 측정은 코드의 성능을 비교하는 최고의 방법이 아니다.

2. 빅 오 표기법 종류

• O(1)-상수 시간 복잡도: 입력 크기에 관계없이 실행 시간이 일정
  • 배열의 첫 번째 요소를 변경하는 함수
    => 배열의 크기가 1개인지 1,000개인지와 상관없이 첫 번째 요소를 변경하는 데 항상 동일한 시간이 걸림

function changeFirstElement(arr, newValue) {
  arr[0] = newValue; // 배열의 첫 번째 요소에 새로운 값을 할당
}

• O(log n)-로그 시간 복잡도: 입력 크기의 로그에 비례하는 실행 시간
  • 이진 검색(Binary Search) 알고리즘: 배열에서 원하는 값을 찾는 알고리즘으로, 입력 배열을 반으로 나누고 원하는 값과 중간 값을 비교하여 검색 범위를 반으로 줄이는 방식
    => 입력 크기가 두 배로 늘어날 때, 이진 검색은 비교 횟수를 한 번 줄이므로 로그에 비례한 시간이 소요

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 원하는 값 찾음
    } else if (arr[mid] < target) {
      left = mid + 1; // 중간보다 오른쪽 부분 배열 검색
    } else {
      right = mid - 1; // 중간보다 왼쪽 부분 배열 검색
    }
  }

  return -1; // 원하는 값이 배열에 없음
}

---

💡log n 개념 정리

• 주어진 수를 몇 번 나누어야 1 이하의 값이 되는지를 나타내는 로그 함수
  • n은 입력 값이며, 로그의 밑은 일반적으로 2 또는 10이 사용됨
    ex. log₂(n): 주어진 수 "n"을 2로 나누어야 1 이하의 값이 되는 횟수를 의미

---

• O(n)-선형 시간 복잡도: 입력 크기에 직접 비례하는 실행 시간
  • 배열에서 최댓값을 찾는 함수: 입력 배열을 순회하면서 각 요소를 확인하고, 현재까지 발견한 최댓값을 추적
    => 입력 배열의 크기 n에 대해 n번의 비교를 수행하므로 입력 크기가 증가함에 따라 비교 횟수도 비례적으로 증가

function findMax(arr) {
  let max = arr[0]; // 배열의 첫 번째 요소를 최댓값으로 초기화

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]; // 더 큰 값이 나타나면 최댓값을 갱신
    }
  }

  return max; // 최댓값 반환
}

• O(n log n)-선형로그 시간 복잡도: 입력 크기와 입력 크기의 로그 곱에 비례하는 실행 시간
  • 병합 정렬(Merge Sort) 알고리즘: 입력 배열을 반으로 나누고, 각 반쪽을 정렬한 다음 병합하여 정렬된 배열을 생성
    => 입력 크기 n에 대해 n log n 번의 비교와 병합 작업이 수행
    = 입력 배열을 분할할 때 log₂(n)번의 비교 작업 + 각 배열을 정렬하고 병합할 때 n번의 비교 작업

// 병합 정렬 함수
function mergeSort(arr) {
  // 입력 배열이 이미 정렬되어 있거나 길이가 1 이하인 경우, 그대로 반환
  if (arr.length <= 1) {
    return arr;
  }

  // 입력 배열을 반으로 나누기 위한 중간 인덱스 계산
  const middle = Math.floor(arr.length / 2);

  // 배열을 반으로 나누어 좌측과 우측 부분 배열로 분리
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // 좌측과 우측 부분 배열을 재귀적으로 정렬하고 병합
  return merge(mergeSort(left), mergeSort(right));
}

// 두 부분 배열을 병합하는 함수
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 좌측과 우측 부분 배열을 비교하며 병합
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 남은 요소들을 병합
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

• O(n^2)-이차 시간 복잡도: 입력 크기의 제곱에 비례하는 실행 시간
  • 버블 정렬(Bubble Sort) 알고리즘: 입력 배열을 순회하면서 인접한 두 요소를 비교하고, 만약 순서가 잘못되어 있다면 두 요소를 교환하는 과정을 반복하여 배열을 정렬
    => 입력 크기가 커질수록 정렬 작업에 더 많은 비교와 교환 작업이 필요하므로 실행 시간이 크게 증가

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 요소를 교환
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

• 시간 복잡도 크기 순서
  O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

3. 빅 오 표기법 적용

• 프로그래머스 'Lv0. 문자 반복 출력하기' 정답 코드를 빅 오 표기법으로 표현하기

function solution(my_string, n) {
    return my_string.split('').map((str)=> str.repeat(n)).join('')
}

• split(''): 주어진 문자열을 배열로 분할
  => O(n) n은 입력 문자열 my_string의 길이

• map((str) => str.repeat(n)): 배열의 각 문자를 n번 반복하여 새로운 배열을 생성
  => O(n) n은 입력 문자열 my_string의 길이

• join(''): 배열의 모든 요소를 하나의 문자열로 결합
  => O(n) n은 결과 문자열의 길이

• 이 함수의 전체 복잡도

  • O(n) + O(n) + O(n) = O(3n)
    => 상수를 제외하면 O(n)

---

💡빅 오 표기법에서 상수를 제외하는 이유

• 입력 크기가 충분히 커지면 상수항은 큰 영향을 미치지 않는다.

  • ex. 입력크기 n이 커질수록 O(3n)과 O(n)의 차이는 무시 된다.
    => 3이나 다른 상수는 성능을 비교하는 데 핵심적인 역할을 하지 않으므로 빅 오 표기법에서는 일반적으로 제외한다.

• 상수항을 포함하면 복잡한 수식으로 표현되어 알고리즘의 성능을 비교하기 어렵다.

  • ex. 알고리즘 A: 실행 시간이 5n^2 + 3n + 2
    알고리즘 B: 실행 시간이 1000n + 5000
    => 입력 크기 n이 증가함에 따라 알고리즘 A의 실행 시간은 n^2에 비례하여 빠르게 증가하고 알고리즘 B의 실행 시간은 n에 비례하여 증가하는데 상수항이 포함된 수식으로 비교하게 되면 알고리즘 A와 알고리즘 B의 상대적인 효율성을 파악하기 어렵다.

=> 주로 주요한 영향을 미치는 부분인 입력 크기에 대한 가장 큰 항만을 고려하고, 상수나 낮은 차수의 항은 무시하여 단순하게 표현한다.

---