[알고리즘분석] 시간 복잡도 정리 with 족보

이정운·2022년 10월 9일
1

성능향상 문제



피보나치 수 구하기

재귀적 방법 (분할 정복법)

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)=n(n1)2T(n)=\frac{n(n-1)}{2}

답: W(n)=n(n1)2W(n)=\frac{n(n-1)}{2}

행렬곱셈


답: n개n개n개 T(n)=n3T(n)=n^3

순차검색



없으면 n번 다 돌아야 한다.
W(n)=nW(n)=n

확률도 고려(있는 경우 없는 경우 이항분포) A(n)=(1p)n+kkpnA(n)=(1-p)n+\sum\limits_{k}k\frac{p}{n} (p=1 있다 p=0 없다)

A(n)=p(n+1)2+(1p)nA(n)=\frac{p(n+1)}{2}+(1-p)n
p는 x가 배열에 잇을 확률

차수:Order (차수는 집합)

  • 필요성: 시간 복잡도 함수가 매우 복잡할 가능성이 있어 간단하게 표현하기 위해 고안된 개념
  • 높은 차수항이 궁극적으로 지배한다.

big-O

  • 정의: 점근적 상한 (asymptotic upperbound),최악의 경우의 시간복잡도를 간단히 표현한 가장 많이 사용하는 차수

  • 수학적 정의

    g(n)O(f(n))g(n) \in O(f(n))이란
    c(양의실수),N(음이아닌정수)0g(n)cf(n)Nn\exists c(양의 실수),N(음이아닌정수) 0\le g(n) \le cf(n) N\le n

  • 의미: 이 알고리즘의 수행시간은 cf(n)보다 절대 늦을 수 없다.

  • 예제
    n2+10nO(n2)n^2+10n \in O(n^2)
    n2+10n2n2n^2+10n \le 2n^2
    10nn210n \le n^2 (c=2 N=10 존재)
    n2+10nO(n2)n^2+10n \in O(n^2)은 참인 명제

  • 예제
    T(n)=n(n1)2T(n)=\frac{n(n-1)}{2}
    T(n)n22O(n2)T(n)\le \frac{n^2}{2}\in O(n^2)
    T(n)O(n2)T(n)\in O(n^2)
    N=0 c=1 이 존재

Ω\Omega 표기법

  • 의미: 이 알고리즘의 수행시간은 cf(n)보다 더 빠를 수는 없다.

    • 정의
      g(n)Ω(f(n))g(n) \in \Omega(f(n))이면
      NnN \le n인 모든 정수 n에 대해서 0cf(n)g(n)0 \le cf(n) \le g(n) 이 성립하는 양의 실수 c음이 아닌 정수 N이 존재한다.
  • 예제 T(n)=n(n1)2T(n)=\frac{n(n-1)}{2}

2n2\le n인 모든 n에 대해서 n2n1\frac{n}{2}\le n-1 가 성립하므로
n24T(n)\frac {n^2}{4} \le T(n) 이때 n24Ω(n2)\frac{n^2}{4} \in \Omega(n^2)이다.
따라서, c=1/4 N=2를 선택하면 T(n)Ω(n2)T(n) \in \Omega(n^2)

  • 예제 n3Ω(n2)n^3 \in \Omega(n^2)
    n2n3n^2 \le n^3
    1n1 \le n
    c와 N이 1일때 위 조건을 만족하므로 참인 명제

  • 예제 nΩ(n2)n \in \Omega(n^2)
    위 명제가 참이라고 가정하자 즉
    cn2ncn^2 \le n인 양의 실수 c와 NnN \le n 음이 아닌 정수 N이 존재한다는 뜻이다.
    이때 n1cn \le \frac{1}{c}인데 이것은 NnN \le n 이라는 조건에 모순이다.

Θ\Theta 표기법

같은 카테고리의 복잡도 함수인지 아닌지를 나타냄


small oo 표기법

  • 복잡도 함수끼리의 관계를 나타내긱 위함

  • 의미: 훨씬 낫다.
  • Big O는 c가 존재하면 되지만 small o는 모든 c에 대해서 부등식을 만족해야 한다.

ω\omega 표기법

차수의 성질


차수 필살기

ano(n!)a^n \in o(n!)

로피탈 정리

복잡도와 컴퓨터 능력

t 시간에 m개의 문제를 해결한다 가정
처리 속도가 k배가 되었다 가정

  • 복잡도가 cn일때 -> km개의 문제를 t 시간내에 해결
  • 복잡도가 cnscn^s -> k1smk^{\frac{1}{s}}m개의 문제를 t 시간내에 해결
  • 복잡도가 c2nc2^n이라고 가정할때 2배가 향상된다면 m+1 만약 100배가 향상된다면 m+6 많게는 m+7개만큼 해결 가능

족보 풀이

2014 1학기 중간 1번

대체방법을 이용하여 T(n)을 정확히 구하시오 n=2k라 가정한다.
T(n)=T(n2)+nT(0)=1T(n)=T(n-2)+n T(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+2iki=1+k(k+1)=k2+k+1\sum\limits_i^ki=1+k(k+1)=k^2+k+1
T(n)=n24+n2+1T(n)=\frac{n^2}{4}+\frac{n}{2}+1

2014년 1학기 중간 1번

다음이 맞는 틀린 것인지 증명하시오 (n>=1)
2n2+nO(n2)2n^2+n \in O(n^2) True

c=3이라고 가정하자
2n2+n3n22n^2+n \le 3n^2
nn2n \le n^21n1\le n에 대해서 성립하는 부등식이다.

즉, 1n1 \le n인 모든 정수 n에 대해서 2n2+n3n22n^2+n \le 3n^2이 성립하므로 big o의 정의에 따라
2n2+nO(n2)2n^2+n \in O(n^2)은 참인 명제이다.

2014 2학기 중간 1번


n=2kn=2^k
T(2)=3T(1)+1=1+3T(2)=3T(1)+1=1+3
T(4)=3T(2)+1=1+(1+3)3=1+3+32T(4)=3T(2)+1=1+(1+3)*3=1+3+3^2
T(8)=3T(4)+1=1+3+32+33T(8)=3T(4)+1=1+3+3^2+3^3
T(2k)=i=0k3iT(2^k)=\sum\limits_{i=0}^k3^i
T(2k)=3k+112T(2^k)=\frac{3^{k+1}-1}{2}
k=lg(n)k=lg(n)
T(n)=3lg(n)+112T(n)=\frac{3^{lg(n)+1}-1}{2}

2014 2학기 중간 3번

  • (1)
    c=10,N=10 일때

  • (2)
    극한이 0이 되므로 small o이다

2015 1학기 중간 1번


  • 힌트: 식의 규칙을 관찰하고 테일러 급수를 이용해서 부등식을 만들어라
  • 정답
    T(n)=n!i=1n(1i!)O(n!)T(n)=n!\sum\limits_{i=1}^n(\frac{1}{i!}) \in O(n!)

반복대입법을 이용하여 T(n)을 정확히 구하고, Big-O로 표시하시오.

T(n)=nT(n1)+1,T(0)=0,T(1)=1T(n)=nT(n-1)+1, T(0)=0,T(1)=1
T(2)=2T(1)+1=1+2×1T(2)=2T(1)+1=1+2\times1
T(3)=3T(2)+1=1+3+1×2×3T(3)=3T(2)+1=1+3+1\times2\times3
T(4)=4T(3)+1=1+4+3×4+1×2×3×4T(4)=4T(3)+1=1+4+3\times4+1\times2\times3\times4
......
T(n)=n!n!+n!(n1)!+n!(n2)!+...n!0!T(n)=\frac{n!}{n!}+\frac{n!}{(n-1)!}+\frac{n!}{(n-2)!}+...\frac{n!}{0!}
T(n)=n!k=0n1k!T(n)=n!\sum\limits_{k=0}^n\frac{1}{k!}
k=0n1k!k=01k!=e\sum\limits_{k=0}^n\frac{1}{k!} \le \sum\limits_{k=0}^\infty\frac{1}{k!}=e
T(n)e×n!T(n)\le e\times n!
T(n)O(n!)T(n) \in O(n!)

2015 1학기 중간 3번

(1) C=100 N=10에 대하여 성립하므로 정의에 의해서 명제는 참이다.
(2)
limninflg(n)/ln(a)lg(n)/ln(b)=lg(b)lg(a)>0\lim\limits_{n \rightarrow \inf}\frac{lg(n)/ln(a)}{lg(n)/ln(b)}=\frac{lg(b)}{lg(a)}>0 이므로 loga(n)Θ(lobb(n)log_a(n) \in \Theta(lob_b(n)

2015 2학기 중간 1번


T(n)=3lg(2n)12T(n)=\frac{3^{lg(2n)}-1}{2}
T(n)O(3lg(2n))T(n) \in O(3^{lg(2n)})

2015 2학기 중간 3번


(1)
c=10000 N=0일때 성립하므로 정의에 의해서 위 명제는 참이다.
(2) True 로피탈 정리 사용

2016년 1학기 중간 1번

1) T(n)=(log3(n)+1)nT(n)=(log_3(n)+1)n
2) T(n)O(n2)T(n) \in O(n^2)

2016년 1학기 중간 3번

1) log(n!)=i=2nlog(i)log(n!)=\sum\limits_{i=2}^n log(i)
n=2일 때 log(2) <=4 그러므로 위 명제는 거짓이다.
2) 모순 정리로 해결 거짓이다.

profile
헬스 ,강화학습,3D Vision,Robotics를 좋아하는 엔지니어 입니다.

0개의 댓글