복잡도?

복잡도란, 알고리즘의 성능과 효율을 나타내는 척도이다. 크게 시간복잡도와 공간복잡도로 나눌 수 있다.
복잡도를 나타내는 방법으로는 점근 표기법으로 주로 빅오와 세타 표기법이 많이 사용된다.
즉, 복잡도란 어떤 알고리즘이 효율적인지를 판단해주는 척도다.

시간복잡도

시간복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
이름은 시간복잡도인데 왜 연산의 횟수를 나타내냐 하면, 첫째로 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않기 때문이고, 둘째로 실행 시간 측정을 위한 또다른 방법이 필요하기 때문이다.
코드에서 성능에 가장 영향을 끼치는 요인은 반복문이다. 반복문이 여러번 반복될수록 실행시간이 길어진다. 래서 알고리즘의 성능을 평가할 때는 알고리즘의 반복문을 보고 평가한다.

알고리즘의 성능 평가 Case

1. 최선의 경우 -> Big 오메가
   • 최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
2. 최악의 경우 -> Big-O
   • 최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
3. 평균의 경우 -> Big 세타
   • 여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

• 알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 평균을 구하기 어려워져 최악의 경우로 알고리즘 성능을 파악한다.

공간복잡도

공간복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.
공간 복잡도를 결정하는 것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼친다.
알고리즘을 실행시키기 위해 필요한 공간은 두가지로 나눌 수 있다.

1. 알고리즘과 무관한 공간인 고정 공간
	-> 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간
2. 알고리즘과 밀접한 공간, 즉 가변 공간
	-> 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등

시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적이다.

시간복잡도 vs 공간복잡도

시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
지금은 예전에 비해 메모리 용량이 넘쳐나다 보니 시간복잡도에 비해 중요도는 떨어졌다.
시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.

빅오 표기법

빅오 표기법(Big-O notation)은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생한다.

이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 한다.

빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.

다시 말해 최악의 경우를 고려하는 데 가장 좋은 표기법이다! (알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적임을 의미)

빅오 표기법의 특징

1. 상수항 무시
   • 빅오 표기법은 n이 충분히 크다고 가정하고 있고, 알고리즘의 효율성은 n의 크기에 영향을 받으므로 상수항 같은 사소한 부분은 무시한다.
   • O(2n)은 O(n)으로 간주
2. 영향력 없는 항 무시
   • 빅오 표기법은 n의 크기에 영향을 받으므로 가장 영향력이 큰 항 이외에 영향력이 없는 항은 무시한다.
   • O(n^2 + 2n + 1)은 O(n^2)으로 간주