[알고리즘] 알고리즘 복잡도

알고리즘의 효율성을 알아내기 위해 알고리즘을 측정하는 방법

 

 

---

 

 

종류

시간 복잡도

공간 복잡도

 

 

---

 

 

 

1. 공간 복잡도 (Space Complexity)

• 프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정하는 방법

공간복잡도는 시간 복잡도와 반비례하는 경우가 많다.

컴퓨터의 발전으로 대용량 지원이 많이되며 시간 복잡도보다 덜 중요시되는 경우가 많다.

 

 

 

1-1. 공간 복잡도 계산법

• 공간 복잡도는 알고리즘에 사용되는 저장 공간을 계산하면된다.
• 빅 오 표기법으로 표현할 수 있어야한다.

 

int Factoria(int _fac){
	int _return = 1;

	for (int n = 2; n < (_fac + 1); n++)
		_return *= n;
    
	return _return;
}

• 위 팩토리얼 함수는 _fac, _return, n 변수들만 사용한다.
• 공간 복잡도는 O(1)이다.

 

int Factorial(int _fac){
	return (_fac == 1) ? 1 : (Factorial(_fac - 1) * _fac);
}

• 위 팩토리얼 함수는 재귀함수를 사용한 예제이다.
  • 함수를 재귀함수로 1까지 호출하여, _fac번째까지 함수를 스택에 쌓게된다.
• 공간 복잡도는 O(n)이다.

 

 

 

---

 

2. 시간 복잡도 (Time complexity)

• 프로그램이 시작하며 종료될때까지 걸리는 시간을 측정하는 방법
• 코드 작성자의 숙련도와 다양한 언어의 차이 등 다양한 변수로 객관적 효율성의 평가가 어렵다.
• 따라서, 알고리즘의 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현하는 법이다.

알고리즘의 효율성을 측정하는데 사용된다.

 

 

 

2-1. 알고리즘 복잡도 표현

1. 최악 경우 분석 (Worst case analysis)
   • 알고리즘이 가장 오래 반복/실행되는 경우를 말한다.
   • '어떤 입력이 주어지더라도 이 이상을 넘지 않는다'라는 최악의 경우이기에 알고리즘의 복잡도로 사용된다.
2. 평균 경우 분석 (Average case analysis)
   • 입력 값을 최선과 최악의 사이에서 균등하게 무작위로 주고 분석하는 것을 말한다.
3. 최선 경우 분석 (Best case analysis)
   • 거의 사용되지 않으나 최적 알고리즘 고안에 참고 자료가 된다.

 

---

 

 

 

복잡도의 점근적 표기

빅오 표기 O (Big-Oh) - 상한 (이보다 빠르게 작동할 수 없다.)
빅 오메가 표기 Ω (Big-Omega) - 하한 (이 정도 작동이 평균이다.)
데타 표기 θ (Theta) - 평균 (이 이상 빨리 작동하지 않는다.) 

 

 

• 복잡도는 입력 크기에 대한 함수로 표기한다. 함수는 주로 여러 항을 가지는 다항식이다. 그래서 이를 단순화 표현한 것이 점근적 표기(Asymptotic notation)이다.
• 이는 입력 크기 n이 무한으로 커질 때의 복잡도를 간단히 표현한 것이다.

 

가장 중요한 것은 핵심이 되는 연산(무한에 가정한 연산 중 식에서 가장 큰 영향을 미치는 개수)을 찾는 것

 

 

$3n^3 - 15n^2 + 10n - 18  = O(n^3)$
$2n^2 - 8n                      = O(n^2)$
$4n + 6                           = O(n)$

• 함수를 변환하는 예는 위와 같이 다항식의 최고 차항만을 계수 없이 취하는 것이다.

 

 

 

 

O - 표기

$O(1)$	상수 시간	Constant time	빠름 ∧ ㅣ ㅣ ㅣ ㅣ ㅣ ㅣ ㅣ ㅣ ∨ 느림
$O(logN)$	로그(대수) 시간	Logarithmic time
$O(n)$	선형 시간	Linear time
$O(NlogN)$	로그 선형 시간	Log-linear time
$O(n^2)$	제곱 시간	Quadratic time
$O(n^3)$	세제곱 시간	Cubic time
$O(2^n)$	지수 시간	Exponential time