쉽게 배우는 알고리즘-02 알고리즘 설계와 분석의 기초

알고리즘이란

-문제 해결 절차를 체계적으로 기술한 것

-문제 요구 조건 : 1) 입,출력 명시  2) 입력으로 출력 만드는 과정

 

알고리즘 분석

-해당 알고리즘이 자원(소요시간, 메모리 등)을 얼마나 소모하는지

-시간 분석  : 1) 최악/평균의 경우

                     2) 어느정도 입력에 어느 정도 시간이 필요한 지 짐작

                     3)입력 크기 대해 시간이 어떤 비율로 소요되는지로 표현

 

O(1) : n과 상관 없이 상수 시간 소모

O(n) : n에 비례하는 시간, 반복 1

O(n^2) : 반복 2번

O(n^3) : for루프 2번 + k←A[1 ... n]에서 반복

 

 

재귀 = 자기호출, 어떤 문제 안에 크기만 다를 뿐 같은 성격의 작은 문제들이 포함되어 있는 것

        = factorial, 점화식

 

점근석 알고리즘 분석

-크기가 작은 문제는 알고리즘 효율성이 중요하지 않음

-크기가 충분히 큰 문제는 알고리즘 효율성 중요함

-입력의 크기가 춤분히 큰 경우에 대한 분석

- Ο, Ω, Θ, ω, ο 표기법

 

 

1) O( g(n) ) 표기법

-점근적 상한

-f(n)≤g(n)

-일단 그냥 f(n)보다 크면 O(n)되는 거임

2) Ω( g(n) ) 표기법

-점근적 하한, O( g(n) )과 대칭

-f(n)≥g(n) 

-일단 그냥 f(n)보다 작으면 다 가능

 

3) Θ( g(n) ) 표기법

-g(n)의 비율로 증가

- f(n) = Θ(g(n))