시간복잡도 Big O

Big-oh(O)

f와 g를 각각 양의 정수를 갖는 함수라 할 때, 만일 어떤 두 양의 상수 a와 b가 존재하고, 모든 n ≥ b에 대하여, f(n) ≤ a*g(n)이면 f(n) = O(g(n))이다.

함수 ex1()의 소스 코드는 다음과 같이 분석할 수 있다.

함수 ex1()의 경우	실행 빈도수
void ex1(int n) {	-
int count = 0;	1
int i;	1
for (int i = 0; i < n; i++)	n + 1
count++;	n
}	-

 

따라서 함수 ex1()의 프로그램 단계들의 총 실행 빈도수,

즉 실행 시간은 2n+3 이 된다. 그러나 이 보고서에서 실행 시간은 count값으로 하기 때문에 실행 시간은 n 이 된다.

여기서

big-oh 표기법으로 나타내면

f(n) = n, g(n) = n 으로 놓으면

n≥b 인 모든 n에 대하여 n ≤ a*n 인 a와 b를

a = 2, b = 1 로 정할 수 있으므로

함수 ex1()의 시간 복잡도는 O(n) 으로 쓸 수 있다.

 

 

함수 ex2()의 소스 코드는 다음과 같이 분석할 수 있다.

함수 ex2()의 경우	실행 빈도수
void ex2(int n) {	-
int count = 0;	1
int i;	1
for (int i = 0; i < n; i+=2)	(n / 2) + 1
count++;	n / 2
}	-

 

따라서 함수 ex2()의 실행 시간(count 값)은 n/2 가 된다.

여기서

big-oh 표기법으로 나타내면

f(n) = n/2, g(n) = n 으로 놓으면

n≥b 인 모든 n에 대하여 n/2 ≤ a*n 인 a와 b를

a = 1, b = 1 로 정할 수 있으므로

함수 ex2()의 시간 복잡도는 O(n) 으로 쓸 수 있다.

 

함수 ex3()의 소스 코드는 다음과 같이 분석할 수 있다.

함수 ex3()의 경우	실행 빈도수
void ex3(int n) {	-
int count = 0;	1
int i;	1
for (int i = 0; i < n*n; i+=2)	((n*n) / 2) + 1
count++;	((n*n) / 2)
}	-

 

따라서 함수 ex3()의 실행 시간(count 값)은 (n^2)/2 이 된다.

여기서

big-oh 표기법으로 나타내면

f(n) = (n^2)/2, g(n) = n^2 으로 놓으면

n≥b 인 모든 n에 대하여 (n^2)/2 ≤ a*(n^2) 인 a와 b를

a = 1, b = 1 로 정할 수 있으므로

함수 ex3()의 시간 복잡도는 O(n^2) 으로 쓸 수 있다.

 

 

함수 ex4()의 소스 코드는 다음과 같이 분석할 수 있다.

함수 ex4()의 경우	실행 빈도수
void ex4(int n) {	-
int count = 0;	1
int i, j;	1
for (int i = 0; i < n; i++)	n + 1
for (int j = 0; j <= i; j++)	((n * (n+1)) / 2) +1
count++;	(n * (n+1)) / 2
}	-

 

따라서 함수 ex4()의 실행 시간(count 값)은 (n^2)/2+n/2 가 된다.

여기서

big-oh 표기법으로 나타내면

f(n) = (n^2)/2+n/2, g(n) = n^2 으로 놓으면

n≥b 인 모든 n에 대하여 (n^2)/2+n/2 ≤ a*(n^2) 인 a와 b를

a = 1, b = 1 로 정할 수 있으므로

함수 ex4()의 시간 복잡도는 O(n^2) 으로 쓸 수 있다.

 

 

 

함수 ex5()의 소스 코드는 다음과 같이 분석할 수 있다.

함수 ex5()의 경우	실행 빈도수
void ex5(int n) {	-
int count = 0;	1
int i, j;	1
for (int i = 0; i < n*n; i++)	n*n + 1
for (int j = 0; j <= i; j++)	((n*n * (n*n+1)) / 2)+1
count++;	(n*n * (n*n+1)) / 2
}	-

따라서 함수 ex5()의 실행 시간(count 값)은 (n^4)/2+(n^2)/2 가 된다.

여기서

big-oh 표기법으로 나타내면

f(n) = (n^4)/2+(n^2)/2, g(n) = n^4 으로 놓으면

n≥b 인 모든 n에 대하여 (n^4)/2+(n^2)/2 ≤ a*(n^4) 인 a와 b를

a = 1, b = 1 로 정할 수 있으므로

함수 ex5()의 시간 복잡도는 O(n^4) 으로 쓸 수 있다.