알고리즘의 성능 분석

공간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장 공간
• 공간 복잡도 = 고정 공간 + 가변 공간
• 고정 공간: 프로그램 크기나 입출력 횟수와는 상관없이 고정적으로 필요한 저장 공간, 프로그램 저장 공간과 변수 및 상수를 저장하는 공간
• 가변 공간: 실행 과정에서 사용하는 자료와 변수를 저장하는 공간과 함수를 실행하는데 관련 있는 정보를 저장하는 공간

시간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하는 데까지 소요되는 시간
• 시간 복잡도 = 컴파일 시간 + 실행 시간
• 컴파일 시간은 프로그램 특성과 큰 관련 없으므로 고정된 같은 시간으로 가정한다.
• 실행 시간은 같은 프로그램이라도 컴퓨터 성능에 따라 달라질 수 있기 때문에 실제 실행 시간을 측정하기 보다는 명령문의 실행 빈도수를 계산하여 추정
• 시간 복잡도는 각 알고리즘을 서로 비교하기 위한 것이므로, 정확한 실행 시간을 측정하기보다는 실행 빈도수를 구하여 사용한다.
• 지정문,조건문, 반복문안에 있는 제어문과 return문은 시간차이가 거의 없기 때문에 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 실행 빈도수를 계산, 이 과정에서 입력 크기 n에 대한 실행 빈도 함수 구할 수 있다.
• 피보나치 알고리즘을 예로 들어서 시간 복잡도를 구해보자

fibonacci(n)
	if(n<0) then
    	stop;
    if(n≤1) then
    	return n
    f0 ← 0;
	    f1 ← 1;
    for(i←2; i≤n; i ← i+1)do{
    	fn ← f1 + f2;
        f1 ← f2;
        f2 ← fn;
    }
    
    return fn;
 end
    

a) n<0,n=0,n=1인경우

행번호	n < 0	n = 0	n = 1
01	1	1	1
02	1	0	0
03	0	1	1
04	0	1	1
05~13	0	0	0

b) n>1인경우

행번호	n>1	행번호	n>1
01	1	08	n-1
02	0	09	n-1
03	1	10	n-1
04	0	11	0
05	1	12	1
06	1	13	0
07	n

b에서 총 실행 빈도수 계산하면
1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n+2

4n+2는 매개변수 n에대한 실행 빈도 함수이다.
n이 10이면 실행빈도는 42, n이1000이면 실행빈도는 4002다

빅-오 표기법

• 빅-오 표기법은 O(f(n))과 같이 표현 "Big Oh of f(n)으로 읽는다"
• 실행 빈도 함수에서 구한 시간 복잡도가 $n^2$이라면 O($n^2$)으로 표기 하고
  "Big oh of $n^2$"으로 읽는다.

함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ n0 에 대하여 |f(n)|≤ c |g(n)| 을 만족하는 c와 n0이 존재하면, f(n) = O(g(n))이다.

• 빅-오 표기법은 함수의 상한을 나타내기 위한 표기법이다. 다시말해 최악의 경우에도 g(n) 의 수행 시간 안에는 알고리즘이 완료된다는 것을 보장한다.

• 위의 피보나치에서 실행 시간 함수는 4n+2이고 4를 생략해서 O(n)으로 표기한다.

• 다음 알고리즘의 시간 복잡도를 구하시오.

A(n)

	for (m←1,i←1; i < n; i ← i+1) do{
    	while(m < n) do{
        	x ← x*i;
            m ← m*1;
        }
    }
    for(j←0; j<n; j←j+1) do
    	x ← x + j;
        return x;

end

1줄 -> n
2줄 -> n
3줄 -> n-1
4줄 -> n-1
5줄 -> 0
6줄 -> 0
7줄 ->n+1
8줄 ->n
9줄 ->n
모두 더하면 7n-1
답은 O(n)

빅-오메가 표기법

• 빅-오메가 표기법은 Ὠ(f(n))과 같이 표기하며,"Big Omega of f(n)"으로 읽는다.
• 실행빈도에서 구한 시간 복잡도가 $n^2$이라면 Ὠ($n^2$)으로 표기하고 "Big Omega of $n^2$"으로 읽는다.
• 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ n0 에 대하여 |f(n)|≥ c |g(n)| 을 만족하는 c와 n0이 존재하면, f(n) = Ὠ(g(n))이다.
• 빅-오메가 표기법은 함수의 하한을 나타내기 위한 표기법이다.
  어떤 알고리즘의 시간 복잡도가 Ὠ(g(n))으로 분석되었다면, 이 알고리즘에는 적어도 g(n)의 수행 시간이 필요함을 의미한다.

빅-세타 표기법

• 빅-세타 표기법은 θ(f(n))과 같이 표기하며, "Big Theta of f(n)"으로 읽는다.
• 실행 빈도에서 구한 시간 복잡도가 $n^2$이라면 θ($n^2$)으로 표기하고 "Big Theta of $n^2$"으로 읽는다.
• 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ n0 에 대하여
  c1 |g(n)| ≤ |f(n)| ≤ c2 |g(n)| 을 만족하는 상수 c1과 c2와 n0이 존재하면,
  f(n) = θ(g(n))이다.

실행 시간 함수 값의 크기

• 실행 시간 함수값의 크기
  log n < n <nlog n < $n^2$ < $n^3$ < $2^n$