03d. 시간 복잡도 계산과 빅오(Big-Oh) 표기법

알고리즘 분석에 인정되는 연산

연산 횟수에 카운트 되는 기본 연산은 다음과 같습니다.

• 변수에 값을 배정
• 함수를 호출
• 산술연산(더하기, 빼기, 곱하기, 나누기 등)
• 비교연산(크다, 작다, 같다, 아니다)
• 인덱싱을 이용한 코드
• 반환(return)
• 참조 또는 내부 속성 접근

시간 복잡도 T(n) 계산

만일 n개의 데이터서 각각 기본연산 3번씩한다면 시간 복잡도는 다음과 같습니다.

T(n) = n * 3 = 3n

빅오(Big-Oh) 표기법

경우에 따라서 정확한 시간복잡도를 구하는 게 어려울 수 있습니다. 이에 가장 차수가 높은 것만 남겨놓아 비교하는 빅오 표기법이 있습니다. 차수가 높은 n이 처리할 데이터가 많을수록 그 차이가 크기 때문입니다.

$T(n) = n^5+n^3+n+5$ => $O(n) = n^5 $

빅오 표기법은 식을 단순화하는 것보다 "알고리즘을 수행시간에 따른 성능 기준을 나누기 쉽다"에 의미가 있습니다. 정확한 식을 모르더라도 "이 알고리즘의 성능은 여기 정도다"라고 판단할 수 있는거죠. 다음은 기준으로 자주 사용되는 빅오 표기입니다.

• $O(1)$ : 상수시간(Constant Time)
• $O(logn)$ : 로그시간 또는 대수시간(Logarithmic)
• $O(n)$ : 선형시간(Linear)
• $O(nlogn)$ : 로그선형시간(Log-Linear)
• $O(n^2)$ : 제곱시간(Quadratic)
• $O(n^3)$ = 세제곱시간(Cubic)
• $O(2^n)$ = 지수시간(Exponential)

직접 그래프는 https://www.desmos.com/calculator 에서 그려볼 수 있습니다.
그런데 $2^n$을 제외하면 초반부에 $O(1)$보다 더 좋은 성능처럼 그래프에 나오지만, 실제로 데이터 처리는 개수가 1부터 시작이므로 의미가 없습니다.

위키독스 연재 : https://wikidocs.net/book/2868