점근적 표기

알고리즘 점근적 표기

https://ko.wikipedia.org/wiki/%EC%9C%84%ED%82%A4%EB%B0%B1%EA%B3%BC:TeX_%EB%AC%B8%EB%B2%95

https://blog.naver.com/aureagenus/120113285536

https://jjycjnmath.tistory.com/117

---

O - 표기법

O(f(n))은

최고차항의 차수*가 f(n)과 *일치하거나 더 작은 함수의 집합

상한의 개념 포함

• $$
  f(n) \in , O(g(n))을 , f(n) = O(g(n))
  $$

• $$
  f(n) = O(g(n)) => f는 , g보다 , 빠르게 , 증가하지 , 않는다.
  $$

• $$
  ex);5n^2 , + , 4n , = O(n^2) , or , 7n , = O(n^2)
  $$

표기

• $$
  O(g(n)) = {f(n) ; | ; \exists c > 0, , n_0 > 0 ; s.t., \forall n \ge n_0, , f(n) \le cg(n)}
  $$

• $$
  O(g(n)) = {f(n) ; | ;모든 , n \ge n_0 , 에, 대하여 , f(n) \le cg(n) , 인 , 양의 , 상수 , c , 와 , n_0 ,가 , 존재한다., }
  $$

---

오메가 표기법

오메가(f(n))은

최고차항의 차수*가 f(n)과 *일치하거나 더 큰 함수의 집합

하한의 개념 포함

• $$
  적어도 , f(n)의 , 비율로 , 증가하는 , 함수
  $$

• $$
  O(g(n))과 , 대칭적
  $$

• $$
  f(n) , = \Omega(g(n)) , => f는 , g보다 , 느리게, 증가하지 , 않는다.
  $$

• $$
  ex) , 5n^2 , + 4n , = \Omega(n^2) , or , 7n^3 , = , \Omega(n^2)
  $$

표기

• $$
  \Omega(g(n)) = {f(n) ; | ; \exists c > 0, , n_0 > 0 ; s.t., \forall n \ge n_0, , cg(n)\le , f(n),}
  $$

• $$
  \Omega(g(n)) = {f(n) ; | ;모든 , n \ge n_0 , 에, 대하여 , cg(n)\le , f(n), 인 , 양의 , 상수 , c , 와 , n_0 ,가 , 존재한다., }
  $$

---

세타 표기법

세타(f(n))은

최고차항의 차수*가 f(n)과 *일치하는 함수의 집합

상한의 개념 + 하한의 개념 포함

• g(n)의 비율로 증가하는 함수

• 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합

• $$
  f(n) , = \theta(g(n)) , => , f는 , g와 , 같은 , 정도로 , 증가
  $$

• $$
  ex) ; True: , n^2 , + 3 , \in , \theta(n^2) , or , n^2 , + 3, = , \theta(n^2)
  $$

• $$
  ex) ;False: \theta(n^2) , \in , 5n^2 , or , \theta(n^2) , = , 5(n^2)
  $$

표기

$$ \theta(g(n)) \, = \, O(g(n)) \, \cap \, \Omega(g(n)) $$