2강 제 1강 알고리즘 1.3 알고리즘 설계

1. 3 알고리즘의 설계 

 

주어진 문제와 조건 등이 매우 다양하므로 알고리즘의 일반적인 설계 방법론은 존재하지 않지만,

많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법이 있다.

 

1. 4 알고리즘의 분석 

 

1. 4. 1 정확한 분석 

유효한 입력, 유한 기간 → 정확한 결과 생성 ? 

  다양한 수학적 기법을 사용해서 이론적 증명이 필요

 

1. 4. 2 효율성 분석 

알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

 

(1) 공간 복잡도( space complexity )  : 메모리의 총 양 

  고리즘 수행에 필요한 컴퓨터의 자원의 양을 측정 

  정적 공간 + 동적 공간

(2) 시간 복잡도 ( time complexity ) :  수행 시간 , 입력 데이터의 크기 의 함수표현

  알고리즘을 실행시켜 완료될 때까지 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 총 횟수로 표현

→ 최악의 경우 수행 시간을 입력 크기의 함수로 표현

 

 

1.5점근 성능

 

1.5.1 점근성능의 개념

점근성늠 ( asymptotic performance ) 

입력 크기 n 이 무한대로 커짐에 따라 결정되는 성능

 

an^2 + bn + c 의 수행시간을 가지는 알고리즘에서 

점근 성능은  계수를 제외한 최고차항인  n^2 가된다.

 

 

1.5.2. 점근 성능의 표기법

 

입력 크기 n이 무한히 커짐에 따라 결정되는 성능

→ 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현

→ 알고리즘의 수행 시간의 증가 추이를 나타내는 것으로 알고리즘의 우열을 따질 때 용이

 

표기법 : 최고차항만 따른다.....

 

① “Big-oh” 점근적 상한 f(n) = O(g(n)), 최악의 수행시간을 나타내는 표현법

정의 : 어떤 양의 상수 c 와 n0 이 존재하여 모든 n >= n0 에 대하여 f(n) <= c * g(n) 이면 f(n) = O(g(n)) 이다.

② “Big-omega” 점근적 하한 f(n) = Ω(g(n)),  최선의 수행시간을 나타내는 표현법

정의 : 어떤 양의 상수 c와 n0이 존재하여 모든 n>= n0 에 대하여  f(n) >= c * g(n) 이면 f(n) = Ω(g(n)) 이다

 

③ “Big-theta” 점근적 상하한 f(n) = Θ(g(n)) , 성능을 정밀하게 나타낼수 있음

정의 : 어떤 양의 상수 c1, c2 와 n0 이 존재하여 모든 n >= n0 에 대하여

c1 * g(n) <= f(n) <= c2 * g(n) 이면 f(n) = Θ(g(n)) 이다.

 

 

O-표기 간의 연산 시간의 크기 관계 :

O(1 ) <  O(logn)  <  O(n)  <  O(nlogn)  <  O(n^2)  <  O(n^3)  <  O(2^n)

상수시간 < 로그시간 <  선행시간 < 로그선행시간 < 제곱시간 < 세제곱시간 < 지수 시간

<<<<<<<<<<<<<효율적                                    비효율적 >>>>>>>>>>>>>>

 

연산 시간의 증가 추세

효율적인 알고리즘의 중요성

알고리즘의 시간 복잡도 구하기

알고리즘의 시간 복잡도를 구하려면

알고리즘의 수행 시간  f(n) 을 구한 후

f(n) = O(g(n))을 만족 하는 최소 차수의 함수 g(n)을 찾음

 

실용적인 접근 방법 

알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함

g(n)은 최고 차수에 의존

 

 

기본 점화식과 폐쇄형
T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n^2)
T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn)
T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)
T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)
T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn)

 

 

1.6 순환 알고리즘의 성능

순환 ( recursion ) : 재귀

알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태

 

 

 

 

 

(2), (3), (6) 중요

 

 

 

***  강의 2번 보고............... 공부하는데,,,,,,,,,,,,,,,,,,,,,,

 

하.............................................................................

 

내가 바보인건가....................................

 

교수님이.........................................................

 

 

 

 

나중에 보충해야지...........

이해가 안되니 글쓰는것도 힘드네 ㅜ

그저 옮겨 적엇을뿐...........

1강 제 1강 알고리즘

1강 제 1강 알고리즘

 

3강 제 2 장 분학정복 알고리즘

3강 제 2 장 분학정복 알고리즘