복잡도와 빅O표기법

복잡도

: 알고리즘의 성능을 나타내는 척도
크게 시간, 공간 복잡도 로 나뉜다
입력한 데이터가 ‘많아짐’에 따라 다음의 요소가 얼마나 늘어나는지를 측정
시간 복잡도 : 실행 시간
공간 복잡도 : 필요한 공간(메모리)
=> 입력이 늘어남에 따른 시간과 필요 공간의 증가량을 비교

점근 표현(표기)법 (asymptotic notation)

: 정수론과 해석학의 방법이며,
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
복잡도를 단순화 하거나 무한급수를 간소화할때 사용

빅 O 표기법

: O의 의미??? - (order of the function) : 대략 그 함수 정도
(ex : 배열이라면 n이 배열의 요소)

알고리듬의 실행 시간을 일반화하여 표기한다
(보통 알고리듬의 성능을 이야기할때 ‘시간 복잡도’를 설명하는 일이 많음)
이 때, 실행 시간 증가에 가장 큰 영향을 미치는 부분만 사용
(최고차항이 미치는 영향에 비해 다른 항들의 영향은 다소 미미하므로)
(ex : T(n) = 5n^2 + 3n + 5 라면 n^2 만 가져와 O(n^2)로 사용한다)

알고리즘의 최선 , 평균, 최악 시간 복잡도

: 실제 데이터의 상태에 따라서, 알고리즘의 결과가 다르게 나올 수 있음
예를 들어 배열에서 데이터를 검색할 때,
운 좋게 데이터를 한번에 찾을 수도 있겠지만(최선 : O(1)),
반대로 마지막 탐색에서 발견이 될 가능성도 있음(최악 : O(n))
확률을 계산을 통하여 ‘평균’ 시간 복잡도를 구한다(평균 : n/2 = O(n))

보통 알고리즘의 성능은 ‘평균’ 시간 복잡도로 얘기되며,
추가적으로 ‘최악’을 표기한다