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

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

 

복잡도의 종류

시간 복잡도	공간 복잡도
프로그램이 시작하며 종료될때까지 걸리는 시간을 측정하는 방법	프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정하는 방법

 

 

---

공간 복잡도 (Space Complexity)

• 프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정
• 공간복잡도는 시간 복잡도와 반비례하는 경우가 많다.
• 컴퓨터의 발전으로 대용량 지원이 많이되며 시간 복잡도보다 덜 중요시되는 경우가 많다.

 

공간 복잡도 계산법

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

예제)

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)이다.

 

 

---

시간 복잡도 (Time complexity)

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

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

 

알고리즘 복잡도 표현

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

 

 

---

복잡도의 점근적 표기

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

복잡도는 입력 크기에 대한 함수로 표기한다.

함수는 주로 여러 항을 가지는 다항식이다. 그래서 이를 단순화 표현한 것이 점근적 표기(Asymptotic notation)이다.

입력 크기 n이 무한으로 커질 때의 복잡도를 간단히 표현이는 한 것이다.

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

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