증명하기 까다로운 시간복잡도

for (int i=2; i<=e; i++)
    for (int j=i; j<=e; j+=i)

i를 2부터 e까지 돌리면서 각 i마다 j를 i부터 시작해 i씩 더하며 e까지 수행한다.
각 i마다 e/i번 돌린다고 생각하면 된다.
(e는 임의의 양의 정수, 2.71 아님)

수식으로 나타내면 다음과 같다:

\sum _{i\ =\ 2}^e\frac{e}{i}\ =\ e\sum _{i=2}^e\frac{1}{i}

조화급수에 e을 곱한 형태를 가지는 식이 된다.
이제 단조증가 함수에 대해서 다음이 성립한다.

\int _{n-1}^mf\left(x\right)dx\le \sum _{i=n}^mf\left(x\right)\le \int _n^{m+1}f\left(x\right)dx

f(x) = 1/x 라고 하면 f(x)는 1/x 는 단조 증가함수이므로
대입해서 시간복잡도를 구하자. (f(x) = 1/x, n = 2, m = e를 대입)

하한 시간복잡도 :

e\int _1^e\frac{1}{x}dx\ =\ e\left(\log e\ -\ \log 1\right)\ =\ e\log e\ =\ \Omega \left(e\log e\right)

상한 시간복잡도 :

e\int _2^{e+1}\frac{1}{x}dx\ =\ e\left(\log \left(e+1\right)\ -\ \log 2\right)\ =\ O\left(e\log e\right)

우리는 보통 상한 시간복잡도를 따지므로 다음과 같이 결론지을 수 있다.

O\left(e\log e\right)

댓글