[알고리즘 특강 2일차] 시간복잡도의 이해

알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다.
자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다.
내용이 이상하다면 지적해주시면 감사하겠습니다. 👍

안녕하세요 오늘은 알고리즘 2일차로 시간복잡도와 공간복잡도를 공부하겠습니다.

 

 

 

 

 

시간복잡도 (Time Complexity)

시간복잡도를 표기할 때는 보통 빅-오(Big-Oh) 표기법으로 최악의 경우 (Worst Case)의 연산 횟수를 나타냅니다.

이제는 문제를 풀을 때 구현은 기본이고 “시간복잡도"를 줄이는 훈련을 의식적으로 연습해야 합니다.

 

 

 

 

 

시간복잡도의 종류

상수형 (O(1))

• 길이가 N인 배열에서 M번 째 배열값 출력

로그형 (O(logN))

• N개의 정렬된 수열에서 이분탐색을 통해 특정 숫자를 탐색
• 우선순위 큐, 힙에서의 원소 삽입, 삭제 연산
• 모듈러 거듭제곱 빠르게 연산하기

선형 (O(N))

• 정렬되지 않은 길이가 N인 배열에서 가장 작은 수를 탐색

선형로그형 (O(NlogN))

• 힙 정렬, 병합 정렬, 퀵 정렬의 평균 케이스

2차형(O(N^2))

• 버블 정렬, 삽입 정렬, 퀵 정렬의 최악 케이스

3차형(O(N^3))

• 플로이드-워셜 알고리즘

지수형(O(2^N))

• 번호가 매겨진 N개의 동전을 던졌을 때 나올 수 있는 경우를 출력하는 함수

팩토리얼형(O(N!))

• 1부터 N까지의 숫자를 나열할 수 있는 모든 방법

 

 

 

 

 

 

 

logN 시간복잡도 봐보기

저는 엣날부터 $logN$ 시간복잡도가 항상 헷갈렸습니다.

뭔가 $logN$만큼 줄어든다는게 크게 와닿지 않았어서 아래와 같이 정리해보았습니다.

 

 

 

 

이분탐색의 시간복잡도

이분 탐색은 logN 시간복잡도의 대표적인 알고리즘이고 이분 탐색의 개념을 잘 알아둔다면 후에 응용하는데 큰 도움이 됩니다.

• 탐색을 진행할 수록 범위가 $1/2$로 줄어든다.
• 범위가 한 개 남았을 때 답을 찾는다.
• 10 → 5 → 2 → 1
• $O(logN)$

 

 

 

병합 정렬의 시간복잡도

이분 탐색처럼 범위가 1/2로 줄어드는 것을 볼 수 있습니다.

병합정렬에서 분해 후 다시 합칠 때 ‘투포인터' 개념을 사용합니다.

• N개의 수열을 병합 정렬로 오름차순 정렬할 때, 최대 탐색 횟수
• 이분탐색처럼 N개의 원소를 분할할 때 N번의 분할연산이 필요합니다.
• 분할된 원소들을 병합할 때 최대 N개의 원소의 순서를 비교해야 하고, $log_2N$번의 병합연산이 필요합니다.
• 결국, $N + Nlog_2N$의 연산이 필요하므로 $O(NlogN)$이 됩니다.