Chapter 3.2 함수의 증가

Orders of Growth - 개요

---

• 우리는 과연 함수가 얼마나 빨리 증가하는 지에 대해서 알 필요가 있다.
• 만약 $f(x)$가 $g(x)$보다 빨리 증가한다면, 궁극적으로 $f(x)$의 값이 $g(x)$의 값보다 커진다.

order : 거듭제곱(power), 차수

Orders of Growth - 동기

---

• 당신이 사용자의 데이터를 처리하기 위한 웹사이트를 구축하고 있다고 가정해보라.
• Suppose database:
  • 프로그램 A는 n행(records)을 처리하는데 $f_A(n)=30n+8$ microseconds의 시간이 걸리고,
  • 프로그램 B는 n행(records)을 처리하는데 $f_B(n)=n^2+1$ microseconds의 시간이 걸린다.
• 당신이 수백만명의 사용자들의 데이터가 있는 웹사이트를 구축한다면, 어느 프로그램을 사용하겠는가?
  
  

Visualizing Orders of Growth

• n이 커질 때, 더 빠른 함수(B)는 결국 함수(A)보다 더 커진다..
• 

Concept of Orders of Growth

• 우리는 $f_A(n)=30n+8$ 을 $O(n)$ 이라고 한다.( Big-O notation )
• $f_B(n)=n^2+1$ 을 $O(n^2)$라고 한다.
• 어느 $O(n^2)$이라도 $O(n)$보다 더 빠르게 성장한다.
• $O(n^2)$이 수백만명의 사용자에 대하여 시간이 더 많이 걸릴 것이다.

Definition: O(g)

• $g$를 $R→R$인 어떤 함수라고 하자.

• 그럼 $O(g)$는 다음과 같다:

  $\{f:R→R ∣ ∃c,k: ∀x>k: f(x) ≤ cg(x)\}$

  • $x>k$일 때, 항상 $∣f(x)∣ ≤ ∣cg(x)∣$를 만족하는 상수 $c, k$가 존재하면 $f$를 $O(g(x))$라 정의한다.

• "$f$의 최대차수는 $g$" or "$f$ is $O(g)$" , or "$f$=$O(g)$"는 모두 $f∈O(g)$를 뜻한다.

• 일반적으로 "오더 $g$" 라고 얘기한다.

- Points about the Definition

• $f$ is $O(g)$라 함은 정의를 만족하는 어떠한 상수 $c,k$가 존재한다는 가정하에 성립한다.
• 그러나, 조건을 만족하는 $c, k$는 여러 개 있을 수 있다.(즉, 유일하지 않다.)
• 또한, 조건을 만족하는 가장 작은 $c, k$를 찾을 필요는 없다.
• 결론적으로, 증명하기 위해서 정의를 만족하는 $c, k$를 하나는 찾아야 한다.

- "Big-O" 증명의 예

• $30n+8$이 $O(n)$임을 보여라.
  • $∃c,k: ∀n>k: 30n+8 ≤ cn$ 임을 보이면 된다.
  • $c=31, k=8$로 놓고, $n>k(=8)$ 이라 가정하자.
  • 그러면, $cn = 31n = 30n+n > 30n+8$ 이므로 $30n+8 < cn$이 성립한다.
• $n^2+1$이 $O(n^2)$임을 보여라.
  • $∃c,k: ∀n>k: n^2+1 ≤ cn^2$ 임을 보이면 된다.
  • $c=2, k=1$로 놓고, $n>k(=1)$ 이라 가정하자.
  • 그러면, $cn^2 = 2n^2 = n^2+n^2 > n^2+1$ 이므로 $n^2+1 < cn^2$이 성립한다.

- Big-O 예 (기하학적)

• 
• $n>0$에 대해 $30n+8$은 $n$보다 크다.
• 심지어 $0<n<8$에 대해 $31n$보다도 크다.
• 하지만, $n=8$ 오른편에서는 $31n$보다 작다.
• e.g., $c=31,$ $k=8$

- Big-O의 예 (수식)

- Big-O에 대한 유용한 Facts

- 함수 속도 비교

Big-Omega Notation

• Definition: $f,g$를 N→R 혹은 R→R인 집합의 함수라고 하고, $x > k$에 대하여,
  $∣f(x)∣ ≥ C∣g(x)∣$를 만족하는 상수 $C$와 $k$가 존재하면
  $f(x)$ is $Ω(g(x))$ 라고 한다.

• 읽을 때는, "$f(x)$는 $g(x)$의 빅-오메가" 라고 읽는다.

• $Big-O$는 함수의 상한을 두는 반면에, $Big-Omega$는 하한을 둔다.

• $f(x)$ is $Ω(g(x))$ ⇔ $g(x)$ is $O(f(x))$

• Example:
  $f(x)=8x^3+5x^2+7$ is $Ω(g(x))$ where $g(x)=x^3$ 임을 보여라

• Solution: 모든 양의 실수 x에 대하여 $f(x)=8x^3+5x^2+7$ ≥ $8x^3$ 이다.

Definition: Θ(g), exactly order g

• Definition: $f$와 $g$를 $N→R$ 혹은 $R→R$인 집합의 함수라고 하면,

  $f(x)$ is $Θ(g(x))$ if $f(x)$ is $O(g(x))$ and $f(x)$ is $Ω(g(x)).$

• $f(x)=O(g(x))$이고 $g(x)=O(f(x))$이면, $f(x)=Θ(g(x))$이며 $g(x)=Θ(f(x))$이다.

• $Θ(g) ≡ \{f:R→R$ | $∃c1,c2,k:$ $∀x>k: |c_1g(x)|≤|f(x)|≤|c_2g(x)| \}$

  • $c_1g(x)≤f(x)≤c_2g(x)$를 만족하는 $c_1과 c_2$가 존재하면
    $f(x)=Θ(g(x))$이다.

- Rules for Θ

• 대부분 빅-오 표기법과 동일하나, 다음과 같은 예외가 있다:

  • $b>0$에 대해 $∀f,g>0$ & $constants$ $a,b∈R$ 일 때,

    똑같은 점	차이점
    $af∈Θ(f)$	$g=Θ(1)$이 아니라면 $f∉Θ(fg)$
    	$\|f\|^{1-b}$ $∉ Θ(f)$
    	$(log_b\|f\|)^c ∉ Θ(f)$

- Examples of Θ