시간 복잡도 유형

• 빅 - 오메가($Ω(n)$) : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법
• 빅 - 세타($θ(n)$) : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법
• 빅 - 오($O(n)$) : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법

0~99 사이의 숫자에서 어떤 숫자를 찾는다고 해보자. 빅 오메가일 경우 Ω(1), 빅 세타일 경우 θ(2/N), 빅 오일 경우 N번이 된다.

• 빅 오메가일 경우 어떤 숫자는 '0'이 되어 숫자를 한 번(시간 복잡도 1)에 찾을 수 있게 된다.
• 빅 세타일 경우 대충 평균 적인 횟수(50)를 구한다고 쳐서 시간 복잡도는 $n/2$가 된다.
• 빅 오일 경우 맨 어떤 숫자가 맨 마지막(99)에 있는 경우를 말해 복잡도는 $n$이 된다

코딩 테스트에서는?

<aside> 💡 코딩 테스트에서는 빅-오 표기법($O(n)$)을 기준으로 수행 시간을 계산하면 된다.

</aside>

일반적으로 코딩 테스트에서는 하나의 테스트 케이스가 아닌 여러 개의 테스트 케이스를 통과해야 합격되기 때문에 여러가지 다양한 경우의 수를 생각하여 문제를 풀어야하기 때문에 항상 최악일 때를 염두해야 한다.

빅-오 표기법으로 표현한 시간 복잡도 그래프

• $O(1)$ > $O(log n)$ > $O(n)$ > $O(n log n)$ > $O(n^2)$ > $O(2^n)$ > $O(n!)$

시간 복잡도 활용

<aside> 💡 버블 정렬($O(n^2)$), 병합 정렬($O(nlogn)$)을 알고있다고 가정

</aside>

입력에 주어지는 숫자( N(1 ≤ N ≤ 1,000,000)를 기준으로 연산 횟수를 계산하자.

연산 횟수 계산 방법

<aside> 💡 연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

</aside>