[CS] 시간 복잡도와 공간 복잡도

알고리즘의 복잡도를 판단하는 척도에는 시간 복잡도와 공간 복잡도가 있다.

 

1. 시간 복잡도

시간 복잡도는 알고리즘의 실행시간을 측정하며, 연산의 횟수와 밀접한 관계가 있다.

알고리즘은 입력의 크기가 충분히 클 때의 성능을 따진다. 따라서 입력이 무한일 때를 분석하기 위해 점근적 분석을 해야한다.

이때 사용되는 표기법이 점근적 표기법으로, 그중 알고리즘의 시간복잡도는 빅오 표기법을 사용한다.

빅오 함수의 정의는 아래와 같다.

즉 빅오 표기법은 수행시간의 상한선을 기준으로 시간 복잡도를 서술하는 것이다.

입력의 크기(n)가 충분히 크다고 가정하므로, 함수에 유의미한 영향을 주는 최고차항(계수 제외)만을 표기한다.

연산식의 계수보다는 차수를 줄여야 알고리즘의 효율을 늘릴 수 있으며, 이것이 빅오 함수가 시사하는 바이다.

 

알고리즘 풀이시 시간 복잡도 활용 - 컴퓨터는 대략 1초에 코드 1억 번 정도를 수행한다. 입력 데이터 범위와 실행 시간 범위를 고려하여, 전체 수행시간을 어림잡아 알고리즘 사용 가능 여부를 판단한다.

 

2. 공간 복잡도

공간 복잡도는 필요한 메모리를 측정한다.

메모리 용량이 충분히 커진 현대에는 시간 복잡도를 고려하는 것이 우선이다. 컴퓨터의 연산속도는 물리적인 한계점에 다다랐기에 알고리즘의 시간복잡도를 줄이는 것은 여전히 유의미하다.

 

 

네이버 블로그 [Ries 마법의 슈퍼마리오]를 참고하여 작성하였습니다.