기록기록 우는 갈매기

점근 표기법(asymptotic notation)은 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 교집합(Θ)이 있다. 먼저 간략하게 뜻을 말하면 아래와 같다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 하나 하나 알아보기전에, 앞서 말한 '빠르다', '느리다'라는 표현에 대해 그 뜻을 정리할 필요가 있다. 함수의 차수가 높을수록 더 빠를 것 같지만, 차수가 낮은 것이 더 빠르다고 표현한다. 즉, 그래프 상으로 그렸을 때 더 아..

알고리즘을 짰다고해서 끝나는 것이 아니다. 짜긴 짰는데 결과 값을 얻어내기까지 어마어마한 시간을 요구한다면 소용이 없기 때문이다. 따라서 분석을 통해 알고리즘의 효율성을 판단해야한다. 알고리즘의 성능은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 표현한다. 시간복잡도: 얼마나 빠른가? 공간복잡도: 얼마나 많은 공간을 차지하는가? 우선, 시간 복잡도 측정에 대해 주로 다뤄보도록 하겠다. (공간 복잡도는 나중에 중간중간 나올 예정) 시간복잡도 시간복잡도(Time Complexity)는 알고리즘이 '얼마나 빠른가'를 나타내는 함수이며, 보통 함수 이름으로 T(n)을 사용한다. 즉, n과 T(n)의 관계를 구하는 것인데, 이 때 n은 input size가 된다. 시..