빅오(Big-O)표기법

What is Big-O?

• Mathematical notation that describes algorithm efficiency.
  알고리즘의 성능을 수학적으로 표기해주는 표기법.
• Time & Space complexity.
  시간과 공간복잡도 표현

Purpose of the Big-O

• Describes the growth rate of algorithms.
  데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는것.

O(1)알고리즘 constant time

입력데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.

O(n) 알고리즘 linear time

입력데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘.

O(n²) 알고리즘 quadratic time

O(nm) 알고리즘

O(n³) 알고리즘

O(2ⁿ) 알고리즘 exponential time

Fibonacci Numbers 재귀함수 구현

O(mⁿ) 알고리즘 exponential time

O(log n)

binary search

O(Sqrt(n))

square root

빅오는 알고리즘의 실제 러닝타임을 측정하는 것이 아니다.

2020.01.15