October 11, 2019

이 글은 배세민의 자바스크립트로 하는 자료구조와 알고리즘 책을 정리한 글입니다.

빅오 표기법 기초

빅오 표기법(big-O notation)

알고리즘의 최악의 경우 복잡도를 측정하며, 알고리즘의 효율성을 나타내는 지표다.
알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.

  • 시간 복잡도: 시간에 대한 개념으로 알고리즘의 수행 시간이 얼마인지를 나타낸다.
  • 공간 복잡도: 공간에 대한 개념으로 알고리즘이 공간(메모리)을 얼마나 필요로 하는지를 나타낸다.

일반적인 예

성능 순서(오른쪽으로 갈수록 성능이 안좋음)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

  • O(1): 입력값에 상관없이 연산횟수가 고정되어있다.
    ex)배열에 있는 항목을 인덱스를 사용해 접근하는 경우, 스택에서 push, pop

    function exampleConstant(n) {
    for (var i = 0; i < n; i++) {
      return console.log(i)
    }
    }
    
    //선형 탐색
    function LinearSearch(arr, find) {
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] === find) {
        return console.log(i)
      }
    }
    return false
    }
  • O(log n): 입력값이 증가해도 연산횟수가 조금씩 증가하며, 연산횟수가 특정 요인에 의해 줄어든다.
    ex)이진트리(binary tree), 균형탐색트리(balanced search tree)

    function exampleLogarithmic(n) {
    for (var i = 2; i <= n; i * 2) {
      console.log(i)
    }
    }
    
    //이진탐색
    function binarySearch(arr, target) {
    const midpoint = Math.floor(arr.length / 2)
    
    if (arr[midpoint] === target) {
      return arr[midpoint]
    }
    
    if (arr[midpoint] < target && arr.length > 1) {
      return binarySearch(arr.slice(midpoint), target)
    }
    if (arr[midpoint] > target && arr.length > 1) {
      return binarySearch(arr.slice(0, midpoint), target)
    }
    
    return false
    }
  • O(n): 연산횟수와 입력값은 비례한다.
    ex)최악의 경우 n번의 연산을 수행해야하는 알고리즘에 적용

    function exampleLinear(n) {
    for (var i = 0; i < n; i++) {
      console.log(i)
    }
    }
  • O(n log n): 데이터의 수가 n배로 늘 때, 연산횟수는 n배 조금 넘게 증가한다.
    ex)퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

    function exampleLoglinear() {
    for(int i = 0; i < n; i++) {
      for(int j = i; j > 0; j/=2){
        console.log(j);
      }
    }
    }
    
    //퀵정렬
    function quickSort(arr, start = 0, end = arr.length - 1) {
    if (arr.length > 1) {
      const pivot = arr[end]
      const left = []
      const right = []
      while (start < end) {
        if (arr[start] < pivot) left.push(arr[start])
        else right.push(arr[start])
        start++
      }
      return [...exampleQuickSort(left), pivot, ...exampleQuickSort(right)]
    }
    return arr
    }
  • O(n²): 연산횟수는 입력값 n에 제곱에 비례한다.
    ex)이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

    // 이중 for문
    function exampleQuadratic(n) {
    for (var i =0; i<n; i++) {
      console.log(i)
      for (var j =il j<n; j++) {
        console.log(j);
      }
    }
    }
  • O(2ⁿ): 연산횟수는 2의 입력값 n제곱에 비례한다. ex)피보나치 수열

    // 피보나치 수열
    function Fibonacci(n) {
    let result = []
    let i = 0
    let value1 = 0
    let value2 = 1
    while (i < n) {
      let newValue = value1 + value2
      result.push(newValue)
      value1 = value2
      value2 = newValue
      i++
    }
    return result.toString()
    }
  • O(n!): 입력 자료의 크기가 N일경우 n(n-1)(n-2)... * 1(n!) 번만큼의 수행시간을 가진다.

    // 팩토리얼
    function Factorial(n) {
    if (n < 0) {
      return false
    }
    if (n === 0) {
      return 1
    }
    return n * factorial(n - 1)
    }

빅오 표기법 규칙

알고리즘의 분석 목표는 시간복잡도를 계산함으로써 알고리즘의 효율성을 이해하는 것이다.

  • 계수 법칙: 상수를 제거하라

    상수 k > 0 인 경우 f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.

    시간 복잡도 O(n)의 예

    function exampleCoefficient(n) {
    var count = 0
    for (var i = 0; i < n; i++) {
      count += 1
    }
    return count
    }
  • 합의 법칙: 빅오를 더하라

    단, 합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다.

    f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 f(n)+g(n)은 O(h(n)+p(n))이다.

    시간 복잡도 O(n)=n의 예

    function exampleSum(n) {
    var dount = 0
    for (var i = 0; i < n; i++) {
      count += 1
    }
    for (var i = 0; i < 5 * n; i++) {
      count += 1
    }
    return count
    }
  • 곱의 법칙: 빅오를 곱하라

    f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 f(n)g(n)은 O(h(n)p(n))이다.

    시간 복잡도 O(n)=n²의 예

    function exampleProduct(n) {
    var count = 0
    for (var i = 0; i < n; i++) {
      count += 1
      for (var i = 0; i < 5 * n; i++) {
        count += 1
      }
    }
    return count
    }
  • 다항 법칙: 빅오의 k승

    f(n)이 k차 다항식이면 f(n)은 O(n^k)

    시간 복잡도 O(n)=n²의 예

    function examplePolynomial(n) {
    var count = 0
    for (var i = 0; i < n * n; i++) {
      count += 1
    }
    return count
    }

참고