성능향상 문제
피보나치 수 구하기
재귀적 방법 (분할 정복법)
int fib(int n) {
if (n<=1)
return n;
else
return fib(n-1)+fib(n-2)
}
T(0)=1
T(1)=1
T(n)=T(n-1)+T(n-2)+1 (n=2k라 가정)
T(n)>2*T(n-2)
T(n)>2*2*T(n-2)
T(n)>2^kT(2k-2k)=2^kT(0)
T(n)>2^k=2^(n/2)
T(n)>2^k
- 수학적 귀납법으로 증명
반복법 (동적 계획법)
알고리즘의 분석
- 시간 복잡도 그 중에 WORST CASE를 고려한 시간 복잡도가 알고리즘 분석에 있어서 중요함
- 시간 복잡도란? 입력 크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차
배열의 덧셈
교환정렬
답: T(n)=2n(n−1)
답: W(n)=2n(n−1)
행렬곱셈
답: n개n개n개 T(n)=n3
순차검색
없으면 n번 다 돌아야 한다.
W(n)=n
확률도 고려(있는 경우 없는 경우 이항분포) A(n)=(1−p)n+k∑knp (p=1 있다 p=0 없다)
A(n)=2p(n+1)+(1−p)n
p는 x가 배열에 잇을 확률
차수:Order (차수는 집합)
- 필요성: 시간 복잡도 함수가 매우 복잡할 가능성이 있어 간단하게 표현하기 위해 고안된 개념
- 높은 차수항이 궁극적으로 지배한다.
big-O
-
정의: 점근적 상한 (asymptotic upperbound),최악의 경우의 시간복잡도를 간단히 표현한 가장 많이 사용하는 차수
-
수학적 정의
g(n)∈O(f(n))이란
∃c(양의실수),N(음이아닌정수)0≤g(n)≤cf(n)N≤n
-
의미: 이 알고리즘의 수행시간은 cf(n)보다 절대 늦을 수 없다.
-
예제
n2+10n∈O(n2)
n2+10n≤2n2
10n≤n2 (c=2 N=10 존재)
n2+10n∈O(n2)은 참인 명제
-
예제
T(n)=2n(n−1)
T(n)≤2n2∈O(n2)
T(n)∈O(n2)
N=0 c=1 이 존재
Ω 표기법
2≤n인 모든 n에 대해서 2n≤n−1 가 성립하므로
4n2≤T(n) 이때 4n2∈Ω(n2)이다.
따라서, c=1/4 N=2를 선택하면 T(n)∈Ω(n2)
-
예제 n3∈Ω(n2)
n2≤n3
1≤n
c와 N이 1일때 위 조건을 만족하므로 참인 명제
-
예제 n∈Ω(n2)
위 명제가 참이라고 가정하자 즉
cn2≤n인 양의 실수 c와 N≤n 음이 아닌 정수 N이 존재한다는 뜻이다.
이때 n≤c1인데 이것은 N≤n 이라는 조건에 모순이다.
Θ 표기법
같은 카테고리의 복잡도 함수인지 아닌지를 나타냄
small o 표기법
- 복잡도 함수끼리의 관계를 나타내긱 위함
- 의미: 훨씬 낫다.
- Big O는 c가 존재하면 되지만 small o는 모든 c에 대해서 부등식을 만족해야 한다.
ω 표기법
차수의 성질
차수 필살기
an∈o(n!)
로피탈 정리
복잡도와 컴퓨터 능력
t 시간에 m개의 문제를 해결한다 가정
처리 속도가 k배가 되었다 가정
- 복잡도가 cn일때 -> km개의 문제를 t 시간내에 해결
- 복잡도가 cns -> ks1m개의 문제를 t 시간내에 해결
- 복잡도가 c2n이라고 가정할때 2배가 향상된다면 m+1 만약 100배가 향상된다면 m+6 많게는 m+7개만큼 해결 가능
족보 풀이
2014 1학기 중간 1번
대체방법을 이용하여 T(n)을 정확히 구하시오 n=2k라 가정한다.
T(n)=T(n−2)+nT(0)=1
T(2)=T(0)+2=1+2
T(4)=T(2)+4=1+2+4
T(6)=T(4)+6=1+2+4+6
T(2*4)=1+2x1+2x2+2x3+2x4
T(2k)=1+2i∑ki=1+k(k+1)=k2+k+1
T(n)=4n2+2n+1
2014년 1학기 중간 1번
다음이 맞는 틀린 것인지 증명하시오 (n>=1)
2n2+n∈O(n2) True
c=3이라고 가정하자
2n2+n≤3n2
n≤n2 은 1≤n에 대해서 성립하는 부등식이다.
즉, 1≤n인 모든 정수 n에 대해서 2n2+n≤3n2이 성립하므로 big o의 정의에 따라
2n2+n∈O(n2)은 참인 명제이다.
2014 2학기 중간 1번
n=2k
T(2)=3T(1)+1=1+3
T(4)=3T(2)+1=1+(1+3)∗3=1+3+32
T(8)=3T(4)+1=1+3+32+33
T(2k)=i=0∑k3i
T(2k)=23k+1−1
k=lg(n)
T(n)=23lg(n)+1−1
2014 2학기 중간 3번
-
(1)
c=10,N=10 일때
-
(2)
극한이 0이 되므로 small o이다
2015 1학기 중간 1번
- 힌트: 식의 규칙을 관찰하고 테일러 급수를 이용해서 부등식을 만들어라
- 정답
T(n)=n!i=1∑n(i!1)∈O(n!)
반복대입법을 이용하여 T(n)을 정확히 구하고, Big-O로 표시하시오.
T(n)=nT(n−1)+1,T(0)=0,T(1)=1
T(2)=2T(1)+1=1+2×1
T(3)=3T(2)+1=1+3+1×2×3
T(4)=4T(3)+1=1+4+3×4+1×2×3×4
...
T(n)=n!n!+(n−1)!n!+(n−2)!n!+...0!n!
T(n)=n!k=0∑nk!1
k=0∑nk!1≤k=0∑∞k!1=e
T(n)≤e×n!
T(n)∈O(n!)
2015 1학기 중간 3번
(1) C=100 N=10에 대하여 성립하므로 정의에 의해서 명제는 참이다.
(2)
n→inflimlg(n)/ln(b)lg(n)/ln(a)=lg(a)lg(b)>0 이므로 loga(n)∈Θ(lobb(n)
2015 2학기 중간 1번
T(n)=23lg(2n)−1
T(n)∈O(3lg(2n))
2015 2학기 중간 3번
(1)
c=10000 N=0일때 성립하므로 정의에 의해서 위 명제는 참이다.
(2) True 로피탈 정리 사용
2016년 1학기 중간 1번
1) T(n)=(log3(n)+1)n
2) T(n)∈O(n2)
2016년 1학기 중간 3번
1) log(n!)=i=2∑nlog(i)
n=2일 때 log(2) <=4 그러므로 위 명제는 거짓이다.
2) 모순 정리로 해결 거짓이다.