Ch01, Ch02

Ch01. 알고리즘이란

01. 알고리즘은 문제 해결 과정을 묘사하는 것

: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

- 명확하고 효율적으로 설계해야

- 입력이 충분히 큰 경우에 대한 분석 : 점근적 분석

 

02. 알고리즘은 생각하는 방법을 훈련하는 것

 

03. 알고리즘은 자료구조의 확장

 

 

 

Ch02. 알고리즘 설계와 분석의 기초

01. 몇 가지 기초 사항들

1 알고리즘 분석의 필요성

시간 분석(최악의 경우, 평균적인 경우)을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다

2 알고리즘의 수행 시간

입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다

Ex

Ex factorial(n) -> n에 비례

3 재귀(자기호출)와 귀납적 사고

자신보다 작은 문제를 자기호출, 옳다고 가정

~수학적 귀납법

 

02. 점근적 표기

 

 

알고리즘의 성능분석

 

● 실험적 분석 : 주어진 알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간을 측정.

● 이론적 분석 : 알고리즘 수행 시간 (= 성능) 을 실제 구현을 통해서가 아닌, high-level 에서 이론적으로 기술하는 방법

- 시간은 보통 입력 사이즈 (보통 n으로 표기) 에 관한 함수로 표현됨.

- 사용하는 하드웨어 및 소프트웨어와 무관하게 알고리즘의 성능을 표현 가능.

- 이론적 분석을 통해 구한 알고리즘 수행 시간을 시간 복잡도 (time complexity)

- 상수시간 : 입력 크기와는 무관할 때 ex. 숫자를 변수에 대입, 함수 호출, 함수 결과값 반환, 정수 사이 사칙연산, ...

 

 

Big-Oh notation

- 점근적 분석 : 입력의 크기가 충분히 큰 경우에 대한 분석

- 알고리즘의 소요시간이 입력크기 n에 대해서 기껏해야 걸리는 시간

- 점근적 상한을 표시

- O(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합

5n^2+4 ∈ O(n^2)

5n^2+4 = O(n^2)  O(n^2) = 5n^2+4

- 입력 사이즈에 비례해서 해당 함수가 어느 정도로 증가하는가에 더 관심이 많음

 

 

Big-Oh notation (Big-Oh 표기법) 의 수학적 정의

f(n) 와 g(n) 를 자연수에서 실수로의 함수라고 하자.
이 때 만약 모든 n > n 0(초기값) 에 대하여
f(n) ≤ c•g(n)
를 만족하는 어떤 실수 constant c>0 와 자연수 n 0 > 0 이 존재하면
f(n) = O(g(n)) (f(n) is big-oh of (order) g(n)) 이라고 한다.

O(g(n)) = { f(n) | ∃c > 0, n 0 ≥ 0 s.t.∀n ≥ n 0 , cg(n) ≥ f(n) }

 

제일 간략한 형태로 표현   

지수함수 > 다항식 > 로그함수

 

- Comparison of Algorithms

 

Notation Ω (Omega)

- 알고리즘의 소요시간이 입력크기 n에 대해서 적어도 걸리는 시간

- Ω(f(n))은 점근적 증가율이 적어도 f(n)이 되는 모든 함수의 집합

5n 2 +4n = Ω (n 2 ), 7n 3 = Ω(n 2 )

- 점근적 하한을 표시 (=최소한 이 정도 시간이 걸려)

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

 

Notation Θ (Theta)

- 알고리즘의 소요시간이 입력크기 n에 대해서 대략 걸리는 시간
- Θ(f(n))은 점근적 증가율이 f(n)으로 일치되는 모든 함수의 집합

 ex) 5n 2 +4n = Θ (n 2 ), 7n 2 = Θ(n 2 )
- 점근적 증가율을 보임 (= 대충 이정도 시간이 걸려)
- 수학적 정의
Θ( g(n) ) = O( g(n) ) ∩ Ω( g(n) )

 

 

 

- Algorithm analysis using Big-Oh notation

Ex..

 

- 알고리즘 분석에는 O가 가장 많이 쓰임, 대부분의 관심은 가장 최악일 경우에 어떻게 되는지가 중요하기 때문,

최선의 시간보다는 최악의 시간이 알고리즘의 성능을 평가하기에 더 적합

 

Q. 5n^2 = O(n^2)를 증명하라.

c=1, n0=1로 잡는다. 모든 n>=n0(=1)에 대하여 5n^2<=6n^2이다. 즉, 정의를 만족하는 상수 c와 n이 존재한다. 따라서 ~