02. 알고리즘 설계와 분석 2 - 점근적 표기법

* 해당 포스트는 PC환경에 최적화 되어있습니다.

* 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다.

* 저작권 문제는 hjl3066@gmail.com으로 연락주시면 빠르게 조치하겠습니다.

---

입력의 크기가 충분히 클 때 알고리즘의 효율성이 중요해진다.

점근적 분석은 입력의 크기가 충분히 큰 경우에 대한 분석이다.

 

점근적 증가율 : 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율

점근적 표기법 : 점근적 증가율의 표기법

 

아래는 고등학교 때 배우는 점근적 분석의 예이다.

$$\lim_{n \to \infty}$$

 

여기서 다루게될 점근적 표기법은 고등학교에서 배우는 극한보다 더 단순화(?)시킨다.

 

점근적 표기법 : O( g(n) ) - 오(또는 빅오) 표기법

g(n)의 비율로 증가하고, 증가율이 g(n)을 넘지않는다. (점근적 상한)

ex) n, n log n, n², 2^n

정의 : O( g(n) ) = { f(n) | ∃ c > 0, n₀ ≥ 0 s.t. ∀ n ≥ n₀, cg(n) ≥ f(n) } → 증명 수식

- f(n)은 내 프로그램의 수행 시간이다.

- ∃는 존재(Exist)기호로 원소 중 하나라도 참이라면 참이라는 뜻이다.

- ∀는 전칭(All로 생각하면 외우기 편함)기호로 원소 중 모두 참이면 참이라는 뜻이다.

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

 

내 프로그램의 수행 시간 f(n)이 g(n)의 비율로 증가하지만, g(n)을 넘지않을 경우 빅오 표기법을 사용한다.

 

점근적 복잡도 계산 예

• 5n² = O(n²)임을 보여라.

 ① C = 6, n₀ = 1로 잡는다. (대충 적합한 숫자면 됨)

 ② 모든 n ≥ n₀에 대해 5n² ≤ 6n²이 만족

• 5n² + 3 = O(n²)임을 보여라.

 ① C = 6으로 잡는다.

 ② 5n² + 3 ≤ 6n² → 3 ≤ n² → √3 ≤ n

 ③ 모든 n ≥ n₀ (= 2)에 대해 5n² + 3 ≤ 6n²이 만족

• n²/2 - 5 = O(n²)임을 보여라.

 ① C = 1, n₀ = 1로 잡는다.

 ② 모든 n ≥ n₀ (= 1)에 대해 n²/2 - 5 ≤ n²이 만족

 

점근적 표기법 : Ω( g(n) ) - 오메가(또는 빅오메가) 표기법

적어도 g(n)의 비율로 증가하고, O(g(n))과 대칭된다. (점근적 하한)

정의 : Ω( g(n) ) = { f(n) | ∃ c > 0, n₀ ≥ 0 s.t. ∀ n ≥ n₀, cg(n) ≤ f(n) }

→ f(n) = Ω( g(n) ), f는 g보다 느리게 증가하지 않는다.

 

내 프로그램의 수행 시간 f(n)이 적어도 g(n)의 비율로 증가하면서 o(n)과 대칭될 때 빅오메가 표기법을 사용한다.

 

점근적 복잡도 계산 예

• 5n² = Ω(n²)임을 보여라.

 ① C = 4, n₀ = 1로 잡아도 충분

 ② 모든 n > n₀ (= 1)에 대하여 5n² ≥ 4n²이 만족

• 5n² + 3 = Ω(n²)임을 보여라.

 ① C = 1로 대충 잡는다.

 ② 5n² + 3 ≥ n² → 4n² ≥ -3, 모든 자연수에 대하여 만족

 ③ 모든 n > n₀ (= 1)에 대하여 5n² + 3 ≥ n²이 만족

• n²/2 - 5 = Ω(n²)임을 보여라.

 ① C = 1/3로 대충 잡아본다.

 ② n²/2 - 5 ≥ n²/3 → 3n²/6 - 2n²/6 ≥ 5 → n²/6 ≥ 5, n₀는 6이상의 자연수가 만족한다.

 ③ 모든 n > n₀ (= 6)에 대하여 n²/2 - 5 ≥ n²/3이 만족한다.

 

점근적 표기법 : Θ( g(n) ) - 세타 표기법

O(g(n))과 Ω(g(n))이 동시에 성립해야 한다. (가장 tight하게)

정의 : Θ( g(n) ) = O( g(n) ) ∩ Ω( g(n) )

→ f(n) = Θ(g(n)), f는 g와 같은 정도로 증가한다.

 

Θ(g(n))은 O(g(n))일 수도 있고 Ω(g(n))일 수도 있다.

다만, O(g(n))이 무조건 Θ(g(n))이 될 수는 없다.

Ω(g(n))도 마찬가지로 무조건 Θ(g(n))이 될 수는 없다.

 

가장 tight해야 Θ(g(n))을 사용할 수 있기 때문이다.

 

각 점근적 표기법의 직관적 의미

O(g(n)) : tight 하거나 loose하면서 상향선

Ω(g(n)) : tight 하거나 loose하면서 하향선

Θ(g(n)) : 둘 다 tight

 

시간 복잡도 분석 종류

• Worst-case (최악)
  - worst-case 입력에 대한 분석
  - 많이 사용된다.
• Average-case (평균)
  - 모든 입력에 대한 분석
  - 분석이 다소 어려우나, 많이 사용된다.
• Best-case (운빨)
  - best-case 입력에 대한 분석
  - 유용하지 않아서 사용되지 않음

가로축은 n, 세로축은 수행 시간, 점선은 n₀