[SW Expert Academy][Computational Thinking] 기초 수식

링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPCwCKAAPw5UW6&subjectId=AV1lG0SaAAgCFAb_

문제 1

재귀식을 풀기 위해 초기 조건을 $T(1)=1$로 가정하고, $n$ ~ $2$까지의 재귀식을 구하면
$T(n)=T(n-1)+1$
$T(n-1)=T(n-2)+1$
$...$
$T(2)=T(1)+1$
이므로 각 식을 모두 더하면
$T(n)+T(n-1)+...+T(2)=T(n-1)+T(n-2)+...+T(1)+1\times{(n-1)}$
이고 다시한번 정리하면
$T(n)=T(1)+(n-1)$이다. 이때, 초기조건에 의해 T(1)=1이기 때문에 $T(n)=1+n-1=n$이다.
이를 $O-notation$으로 나타내면 $T(n)=O(n)$이다.

문제 2

재귀식을 풀기 위해 초기 조건을 $T(1)=1$로 가정하고, $n$ ~ $2$까지의 재귀식을 구하면
$T(n)=T(n-1)+n$
$T(n-1)=T(n-2)+(n-1)$
$T(n-2)=T(n-3)+(n-2)$
$...$
$T(2)=T(1)+2$
이므로 각 식을 모두 더하면
$T(n)+T(n-1)+T(n-2)+...+T(2)=T(n-1)+T(n-2)+T(n-3)+...+T(1)+n+(n-1)+(n-2)+...+2$
양변을 다시한번 정리하고 $T(1)$을 대입하면
$T(n)=T(1)+\frac{n(n+1)}{2}-1=\frac{n(n+1)}{2}$이다.
이를 $O-notation$으로 나타내면 $T(n)=O(n^2)$이다.

문제 3

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
$T(n)=T(n-1)+logn$
$T(n-1)=T(n-2)+log(n-1)$
$T(n-2)=T(n-3)+log(n-2)$
$...$
$T(2)=T(1)+log2$
이므로 각 식을 모두 더하면
$T(n)+T(n-1)+T(n-2)+...+T(2)=T(n-1)+T(n-2)+T(n-3)+...+T(1)+logn+log(n-1)+log(n-2)+...+log2$
양변을 다시한번 정리하고 $T(1)=C$을 대입하면
$T(n)=C+logn+log(n-1)+...+log2=C+log(1\cdot{2}\cdot{3}\cdot...\cdot{n})=C+log(\frac{n!}{1})=C+log(n!)$
스털링의 근사에 의해 $log(n!)\approx{nlogn-n}$이므로
이를 $O-notation$으로 나타내면 $T(n)=O(nlogn)$이다.

문제 4

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
$T(n)=T(\frac{n}{2})+1$
이고
$T(\frac{n}{2})=T(\frac{n}{4})+1$
$T(n)=T(\frac{n}{2})+1$
이므로 두식을 더하여 양변을 한번 정리하면
$T(n)=T(\frac{n}{4})+1+1$
이므로 이를 일반화 하면, k번째에서
$T(n)=T(\frac{n}{2^k})+k$
이므로 초기 조건을 사용하기 위해 $\frac{n}{2^k}=1$이 되는 조건을 찾으면 $n=2^k$이고 이는 $k=log_2{n}$과 같다. 그렇기에 이를 사용하면 $T(n)=C+log_2{n}$이므로 $O-notation$으로 나타내면 $O(logn)$이다.

문제 5

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
첫 번째 과정에서
$T(n)=T(\frac{n}{2})+n$
두 번째 과정에서
$T(\frac{n}{2})=T(\frac{n}{4})+\frac{n}{2}$
$T(n)=T(\frac{n}{2})+n$
에 의해
$T(n)=T(\frac{n}{4})+\frac{n}{2}+n$
세 번째 과정에서
$T(\frac{n}{4})=T(\frac{n}{8})+\frac{n}{4}$
$T(\frac{n}{2})=T(\frac{n}{4})+\frac{n}{2}$
$T(n)=T(\frac{n}{2})+n$
에 의해
$T(n)=T(\frac{n}{8})+\frac{n}{4}+\frac{n}{2}+n$
이 과정을 일반화하면
$T(n)=T(\frac{n}{2^k})+\frac{n}{2^{k-1}}+\frac{n}{2^{k-2}}+...+\frac{n}{2}+n$
이고 초기 조건을 사용하기 위해 $\frac{n}{2^k}$=1이라고 한다면 $2^k=n$이고 $k=log_2{n}$이다. 또한 여기서 우변의 $\frac{n}{2^{k-1}}+\frac{n}{2^{k-2}}+...+\frac{n}{2}+n$을 정리하면
$S=\frac{n}{2^{k-1}}+\frac{n}{2^{k-2}}+...+\frac{n}{2}+n$
$\frac{1}{2}\times{S}=\frac{n}{2^{k}}+\frac{n}{2^{k-1}}+...+\frac{n}{4}+\frac{n}{2}$
이므로 차를 계산하면
$\frac{1}{2}\times{S}=n-\frac{n}{2^{k}}=n-1$
$S=2n-2$
이기 때문에 $T(n)=T(1)+2n-2=C+2n$이므로 $T(n)=O(n)$이므로 시간 복잡도는 $O(n)$이다.

문제 6

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
첫 번째 과정에서
$T(n)=2T(\frac{n}{2})+n$
두 번째 과정에서
$T(n)=2T(\frac{n}{2})+n$
$T(\frac{n}{2})=2T(\frac{n}{4})+\frac{n}{2}$
위에 식에 아래 식을 대입하면
$T(n)=2T\{2T(\frac{n}{4})+\frac{n}{2}\}+n=4T(\frac{n}{4})+2n$
세 번째 과정에서
$T(\frac{n}{4})=2T(\frac{n}{8})+\frac{n}{4}$
위에 식의 두 번째 과정에서 얻은 식에 대입하면
$T(n)=4\{2T(\frac{n}{8})+\frac{n}{4}\}+2n$
$T(n)=8T(\frac{n}{8})+3n$
이므로 이를 일반화 시키면 k번째 과정에서
$T(n)=2^kT(\frac{n}{2^k})+kn$
이므로 초기조건을 사용하기 위해 $\frac{n}{2^k}=1$이 되기 위해서는 $n=2^k$이고 $k=log_2n$이다. 대입해보면
$T(n)=2^{log_2n}T(1)+nlog_2n=nC+nlog_2n$이므로 $O-notation$으로 나타내면 $O(nlogn)$이다.

문제 7

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
첫 번째 과정에서
$T(n)=3T(\frac{n}{2})+n$
두 번째 과정에서
$T(\frac{n}{2})=3T(\frac{n}{4})+\frac{n}{2}$
첫 번째 식에 대입하면
$T(n)=3\{3T(\frac{n}{4})+\frac{n}{2}\}+n=9T(\frac{n}{4})+n+\frac{3n}{2}$
세 번째 과정에서
$T(n)=9T(\frac{n}{4})+n+\frac{3n}{2}$
$T(\frac{n}{4})=3T(\frac{n}{8})+\frac{n}{4}$
두번째 식을 대입하면
$T(n)=9\{3T(\frac{n}{8})+\frac{n}{4}\}+n+\frac{3n}{2}=27T(\frac{n}{8})+n+\frac{3n}{2}+\frac{9n}{4}$
이를 일반화 시키면 k번째 식에 대해서
$T(n)=3^kT(\frac{n}{2^k})+n\sum_{i=0}^{k-1}\frac{3^i}{2^i}$
이므로 초기조건을 사용하기 위해 $T(1)$인 상황을 찾으면 $\frac{n}{2^k}=1$이기 때문에 $k=log_2{n}$이다. 이를 대입하면
$T(n)=3^{log_2n}T(1)+n\sum_{i=0}^{log_2{n}-1}\frac{3^i}{2^i}$
기하급수 수열의 합의 계산에 의해 $S=\sum_{i=0}^{m-1}r^i=\frac{r^m-1}{r-1}$이므로
$\sum_{i=0}^{k-1}(\frac{3}{2})^i=\frac{(\frac{3}{2})^k-1}{\frac{3}{2}-1}=2((\frac{3}{2})^k-1)$이므로 $k=log_2{n}$를 대입하면
$(\frac{3}{2})^k=(\frac{3}{2})^{log_2n}=(2^{log_2{\frac{3}{2}}})^{log_2n}=n^{log_2{\frac{3}{2}}}$이기 때문에
$\sum_{i=0}^{k-1}(\frac{3}{2})^i=2(n^{log_2{\frac{3}{2}}}-1)$이고 최종적으로 초기조건을 사용하면
$T(n)=n^{log_23}C+n\cdot2(n^{log_2{\frac{3}{2}}}-1)=n^{log_23}C+2n^{1+log_2{\frac{3}{2}}}-2n$이므로 주요항만 추출해서 $O-notation$으로 표현하면 $O(n^{log_23})$이다.

문제 8

재귀식을 풀기 위해 초기 조건을 $T(1)=C$(상수)로 가정하고 재귀식을 풀면
첫 번째 과정에서
$T(n)=T(n-1)+\frac{1}{n}$
두 번째 과정에서
$T(n-1)=T(n-2)+\frac{1}{n-1}$
첫 번째 식과 더해서 정리하면
$T(n)=T(n-2)+\frac{1}{n-1}+\frac{1}{n}$
세 번재 과정에서
$T(n-2)=T(n-3)+\frac{1}{n-2}$
이를 첫 번째와 두 번째 식과 더해서 정리하면
$T(n)=T(n-3)+\frac{1}{n-2}+\frac{1}{n-1}+\frac{1}{n}$
이므로 이를 일반화하여 정리하고 초기 조건을 대입하면
$T(n)=T(1)+\sum_{2}^{n}\frac{1}{k}=C+\sum_{2}^{n}\frac{1}{k}$
$\sum_{1}^{n}\frac{1}{k}$은 조화급수의 합에 의해
$\sum_{1}^{n}\frac{1}{k}\approx{\ln{n}}$이므로 $\log{n}$과 비례한다고 할 수 있다.
그렇기에 $O-notation$으로 표현하면 $O(\log{n})$이다.

문제 9

각 재귀식의 각 단계를 계산하면,
$T(\frac{n}{2})=T(\frac{n}{4})+T(\frac{n}{8})+T(\frac{n}{16})+T(\frac{n}{32})+1$
$T(\frac{n}{4})=T(\frac{n}{8})+T(\frac{n}{16})+T(\frac{n}{32})+T(\frac{n}{64})+1$
$T(\frac{n}{8})=T(\frac{n}{16})+T(\frac{n}{32})+T(\frac{n}{64})+T(\frac{n}{128})+1$
$T(\frac{n}{16})=T(\frac{n}{32})+T(\frac{n}{64})+T(\frac{n}{128})+T(\frac{n}{256})+1$
이므로 이를 모두 합치면
$T(n)=T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+T(\frac{n}{16})+1=[T(\frac{n}{4})+T(\frac{n}{8})+T(\frac{n}{16})+T(\frac{n}{32})+1]+[T(\frac{n}{8})+T(\frac{n}{16})+T(\frac{n}{32})+T(\frac{n}{64})+1]+[T(\frac{n}{16})+T(\frac{n}{32})+T(\frac{n}{64})+T(\frac{n}{128})+1]+[T(\frac{n}{32})+T(\frac{n}{64})+T(\frac{n}{128})+T(\frac{n}{256})+1]$
여기서 각 항이 지수적으로 증가하므로 전체 항의 개수는 $\log{n}$개로 추정할 수 있다. 그러므로 재귀호출의 수는 대략 $O(\log{n})$이 된다.

문제 10

$n=2^k$이라고 하면 $T(n)=\sqrt{n}\cdot{T(\sqrt{n})}+n$에서
$T(2^k)=2^{\frac{k}{2}}\cdot{T(2^{\frac{k}{2}})}+2^k$이므로 각 변을 $2^k$로 나누면
$\frac{T(2^k)}{2^k}=\frac{T(2^{\frac{k}{2}})}{2^{\frac{k}{2}}}+1$
$\frac{T(2^k)}{2^k}=T'(k)$이라고 한다면 $T'(k)=T'(\frac{k}{2})+1$이기 때문에 문제4에 따라 $O(\log{n})$이다.
이를 이용하면 $\frac{T(2^k)}{2^k}=\log{k}$ 이므로 $T(2^k)=2^k\cdot{\log{k}}$이라고 한다면
$T(n)=n\log({\log{n}})$이라고 할 수 있다. 이때, $\log(\log{n})$의 증가폭이 n이 증가함에 비해 매우 느리게 증가하므로 n과 거의 같다고 할 수 있다. 그러므로 시간복잡도는 $O(n)$이다.