Big O notation 정의

<aside> 📖 알고리즘의 연산 횟수를 대략적으로 표기한 것 (알고리즘의 상한으로 표기)

ex) 두개의 함수 f(n)과 g(n)이 있을 때, 모든 $n > n_0$ 에 대하여 $|f(n)| <= c|g(n)|$ 을 만족하는 2개의 상수 $c$와 $n_0$이 존재하면 $f(n) = O(g(n))$이다.

</aside>

<aside> 📖 함수의 상한을 표시한다.

ex) $f(n) = 2n + 1$ 일 때 $n >= 5$ 면 $2n+1 < 10n$ 이므로 $2n+1 = O(n)$

</aside>

<aside> ❓ 빅오표기법의 빠른 정도 (O(1)이 가장 빠름)

$O(1) → O(logN) → O(N) → O(NlogN) → O(n^k) → O(k^n) → O(N!)$

</aside>

<aside> ✅ $f(n) = 2n^2+3n+1$ → $O(n^2)$

$f(n) = 3n^2 + 5nlogn$ → $O(n^2)$

$f(n) = n^(1000) + 3^n$ → $O(3n)$

$f(n) = 2n! + 5^n$ → $O(n!)$

정리하자면 빅 오 표기법은

  1. 상수항(c) 을 무시한다
  2. 영향력 없는 항을 무시한다.

</aside>

대표적인 시간복잡도

$O(1)$