Skip to content

Big O notation

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리듬의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

대표적으로 다음의 다섯 가지 표기법이 있다.

  • 대문자 O 표기법
  • 소문자 o 표기법
  • 대문자 오메가(Ω) 표기법
  • 소문자 오메가(ω) 표기법
  • 대문자 세타(Θ) 표기법

이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법('빅-오 표기법' 아닌가?)이라고도 한다.

표기법

알고리즘 수행시간에 따른 분석으로 주로, 빅O 표기법(Big-O Notation)을 사용한다.

  • O(1): 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘.
  • O(log N): 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
  • O(N): 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
  • O(N log N): 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
  • O(N2): 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
  • O(N3): 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
  • O(2n): 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
  • O(n!): 입력 자료의 크기가 N일경우 n(n-1)(n-2)... * 1(n!) 번만큼의 수행시간을 가진다.
    ex) 외판원 문제(TSP)의 기본적인 해법.

실행시간 순서로 정렬하면 아래와 같다. (오른쪽으로 갈 수록 느리다)

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

BigO-graph.png

Big-O Cheat Sheet

Common Data Structure Operations

Data Structure

Time Complexity

Space Complexity

Average

Worst

Worst

Access

Search

Insertion

Deletion

Access

Search

Insertion

Deletion

Array

Θ(1)

Θ(n)

Θ(n)

Θ(n)

O(1)

O(n)

O(n)

O(n)

O(n)

Stack

Θ(n)

Θ(n)

Θ(1)

Θ(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Queue

Θ(n)

Θ(n)

Θ(1)

Θ(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Singly-Linked List

Θ(n)

Θ(n)

Θ(1)

Θ(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Doubly-Linked List

Θ(n)

Θ(n)

Θ(1)

Θ(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Skip List

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(n)

O(n)

O(n)

O(n)

O(n log(n))

Hash Table

N/A

Θ(1)

Θ(1)

Θ(1)

N/A

O(n)

O(n)

O(n)

O(n)

Binary Search Tree

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(n)

O(n)

O(n)

O(n)

O(n)

Cartesian Tree

N/A

Θ(log(n))

Θ(log(n))

Θ(log(n))

N/A

O(n)

O(n)

O(n)

O(n)

B-Tree

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

Red-Black Tree

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

Splay Tree

N/A

Θ(log(n))

Θ(log(n))

Θ(log(n))

N/A

O(log(n))

O(log(n))

O(log(n))

O(n)

AVL Tree

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(n)

KD Tree

Θ(log(n))

Θ(log(n))

Θ(log(n))

Θ(log(n))

O(n)

O(n)

O(n)

O(n)

O(n)

Array Sorting Algorithms

Algorithm

Time Complexity

Space Complexity

Best

Average

Worst

Worst

Quicksort

Ω(n log(n))

Θ(n log(n))

O(n^2)

O(log(n))

Mergesort

Ω(n log(n))

Θ(n log(n))

O(n log(n))

O(n)

Timsort

Ω(n)

Θ(n log(n))

O(n log(n))

O(n)

Heapsort

Ω(n log(n))

Θ(n log(n))

O(n log(n))

O(1)

Bubble Sort

Ω(n)

Θ(n^2)

O(n^2)

O(1)

Insertion Sort

Ω(n)

Θ(n^2)

O(n^2)

O(1)

Selection Sort

Ω(n^2)

Θ(n^2)

O(n^2)

O(1)

Tree Sort

Ω(n log(n))

Θ(n log(n))

O(n^2)

O(n)

Shell Sort

Ω(n log(n))

Θ(n(log(n))^2)

O(n(log(n))^2)

O(1)

Bucket Sort

Ω(n+k)

Θ(n+k)

O(n^2)

O(n)

Radix Sort

Ω(nk)

Θ(nk)

O(nk)

O(n+k)

Counting Sort

Ω(n+k)

Θ(n+k)

O(n+k)

O(k)

Cubesort

Ω(n)

Θ(n log(n))

O(n log(n))

O(n)

Big-O Cheat Sheet Poster

Big-o-cheat-sheet-poster.png

Time complexity

(Time complexity로 들어올 수 있다)
시간 복잡도(Time complexity)는 알고리즘의 수행시간 분석결과.

Space complexity

(Space complexity로 들어올 수 있다)
공간 복잡도(Space complexity)는 알고리즘의 메모리 사용량에 대한 분석결과.

See also

Favorite site