[알고리즘] 빅오표기법(big-O notation)

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

 

시간 복잡도 표기법

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

 

실행 속도
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 
• 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 형태 자료구조 탐색

O(N)

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

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) 퀵 / 병합 / 힙 정렬

O(N^2)

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

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

O(2^N)

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