3-1. 시간복잡도 (Time Complexity)
보통의 알고리즘 문제는 시간 제한(Time limit)이 주어집니다. 무한대의 시간으로는 테스트도 불가능하고, 그렇게 한다면 의미가 없기 때문입니다.
현실 개발도 마찬가지입니다. 반응형 웹에서 real-time으로 대응하지 못한다면 사용이 가능할까요?
결국에 프로그램에서 시간은 매우 큰 요소입니다. 하지만 우리는 시간을 어떻게 예측할 수 있을까요?
3-1-a. 시간과 연산량
혹시 코드를 짤 때, 연산량을 손으로 카운트 해보신 적이 있나요? 생각보다 어려운 점이 많습니다.
반복문의 연산과 사칙연산, 함수 내부의 총 연산 횟수 등을 카운팅하기는 매우 어렵습니다. 만약 카운팅에 성공해도 덧셈과 곱셈에 걸리는 시간도 다릅니다.
여러분이 사용하는 환경과 채점 서버나 클라이언트에서의 속도도 분명 다를 것입니다. 그렇기에 정확한 시간 측정은 불가능합니다.
가장 중요한 것은 연산의 대략적인 횟수입니다. 그렇다면 횟수는 어떻게 대략적으로 계산할 수 있을까요?
많은 고민 끝에 나온 방법이 입력과 연산량의 관계를 찾아 이를 통해 대략적인 시간을 생각하는 방법입니다.
우리는 연산량을 어떻게 예측할 수 있는지 다음을 살펴보겠습니다.
3-1-b. worst, best, mean
알고리즘 별로 시간이 꼭 정해지는 것은 아닙니다. 물론 정해지는 알고리즘도 있지만 보통은 다음과 같은 기준으로 시간복잡도를 측정할 수 있습니다.
- 최악(worst) : 연산의 마지막 과정까지 마쳐야 완료 (upper bound)
- 최선(best) : 최적의 연산으로 완료 (lower bound)
- 평균(mean) : 평균적인 시간복잡도
보통은 최악을 기준으로 합니다. 데이터셋에 어떤 데이터가 들어있을지 저희는 모르기 때문입니다. 분명 똑똑한 출제자라면 최악의 케이스를 넣어두었을겁니다.
경우에 따라 worst와 best 방법의 시간복잡도가 같은 경우가 있습니다.
3-1-c. notation
보통은 Big-O Notation을 사용합니다. 전체적인 연산량에서 다음 값들을 생략한 표기법입니다.
- 계수 (2N -> N)
- 영향력이 없는 항 (N^2 + N => N^2)
구체적인 정의는 아래를 참고하면 됩니다.
보통 사용하는 시간복잡도 O 표기법은 Big-O Notation인데, worst case를 기준으로 계산합니다.
분할상환분석(Amortized Analysis) : 개별적인 시간복잡도를 생각하지 않고, 전체적인 평균 복잡도를 구하는 분석 방법
3-1-d. 대략적인 느낌
정확히는 아니지만 감을 잡을 수 있다면 그걸로 충분한 경우가 많습니다. \(O()\)를 생략하고 한 번 보겠습니다.
\[N! > X^N > N^X > N > \sqrt{N} > logN > 1\]순서는 직관적으로 증명을 할 수 있지만 생략하겠습니다. 다만 N에 따라 저 값들이 어느정도이고 Test환경에 돌아갈지는 고민해보도록 합시다.
3-2. 공간복잡도 (Space Complexity)
공간은 시간과 거의 마찬가지 입니다. 보통은 container, 즉 자료구조를 사용하는 경우에 신경쓸 상황이 나오니 경우에 따라 소개하도록 하겠습니다.