[자료구조] 빅오 표기법(big-O notation)

알고리즘의 복잡도를 판단하는 척도는 시간 복잡도와 공간 복잡도가 있음

그 중 시간 복잡도는 알고리즘 내 연산의 횟수와 밀접한 관계가 있음

시간 복잡도 표기법

• Big-O(빅 오) 표기법
  • 알고리즘 최악의 실행 시간을 표기함
  • 가장 많이 사용하는 표기법
  • 최소한 보장되는 성능을 표기
• Big-Ω(빅 오메가) 표기법
  • 알고리즘 최상의 실행 시간을 표기
• Big-θ(빅 세타) 표기법
  • 알고리즘 평균 실행 시간을 표기

x축 → 자료 입력 개수, y축 → 시간

실행 속도

O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(2^N)

빅오 표기법의 특징

• 상수항(영향력 없는 항) 무시 : O(N + 1) → O(N)으로 표기
• 계수 무시 : O(2N) → O(N)으로 표기
• 최고차항만 표기 : O(3N^3+2N^2+N+5) → O(N^3)으로 표기

O(1)

• 입력값(N)이 증가해도 실행 시간은 동일한 알고리즘
• 데이터 수와 상관 없이 연산 횟수가 고정된 경우
• index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도 → 기본 연산 수라고 생각하면 됨
• ex) stack의 push, pop

⇒ 수행 횟수 : 1 , 최고차항의 차수 : 0

function example(n) { # 연산 1번 동작
  return n[0] * 2;
}

function example(n) { #  연산이 2번 이루어지지만 상수항을 무시함
  return n[0] * 2 + n[1];
}

O(log N)

• 연산이 한 번 실행될 때마다 데이터의 크기가 절반 감소하는 알고리즘(log의 지수는 항상 2)
• 탐색 단계마다 필요한 연산이 줄어드는 경우
• ex) binary search 알고리즘, tree 형태 자료구조 탐색

public static int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

O(N)

• 입력 값(N)이 증가함에 따라 실행 시간도 선형적으로 증가하는 알고리즘
• 데이터 수에 비례해 연산 횟수가 증가하는 경우
• ex) 1중 for문, shift(), unshift(), splice()

⇒ 수행 횟수 : n , 최고차항의 차수 : 1

function example(n) {
  for (let i = 0; i < n.length; i += 1) {
    console.log(n[i]);
  }
}

O(N log N)

• O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
• 입력 데이터가 많아지면 처리 시간이 늘어나는 경우
• ex) 퀵 / 병합 / 힙 정렬

public static void mergeSort(int[] nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

O(N^2)

• O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
• 데이터의 수가 증가하면 점점 많이 증가하는 경우
• ex) 2중 For 문, 삽입/거품/선택 정렬

⇒ 2중 for문 → 수행 횟수 : n*n , 최고차항의 차수 : 2

⇒ i는 [1, n-1], j는 [i+1, n]번 → 수행 횟수 : n*(n-1)/2 , 최고차항의 차수 : 2

function example(n) {
  for (let i = 0; i < n.length; i += 1) {
    for (let j = 0; j < n.length; j += 1) {
      console.log(i * j);
    }
  }
}

O(2^N)

• 빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당
• ex) fibonacci 수열

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}