CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.
핵심 개념
- 시간 복잡도
- Big-O 표기법
- Big Ω
시간 복잡도
- 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것.
- 시간의 효율성이란?
- 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미
- 연산자의 처리 횟수가 적다 = 시간 복잡도가 낮다.
- 시간 복잡도가 낮을수록(=연산자의 사용 횟수가 적을수록) 효율성이 높은 알고리즘이 됨
Big-O 표기법
- 컴퓨터 과학에서 “대략”을 나타내는 공식적인 개념으로 최악의 경우에 대한 시간 복잡도를 나타내는 표현
- 선형 탐색
- O(n)으로 표현
- 찾는 값이 배열의 맨 끝에 있는 최악의 상황의 경우 n번의 단계를 거치면 됨
- 버블 정렬
- O( n^2)으로 표현
- n개의 자료를 갖는 배열은 n-1쌍을 비교(인접 자료와 쌍을 이루어 비교하기 때문)
- 전체 비교 횟수는 (n-1) + (n-2) + … + 1= n(n-1)/2 = n^2/2 - n/2
- 시간 복잡도는 가장 중요한(가장 지수가 큰) 부분만 남기고, 계수를 삭제
- 따라서 n^2/2 - n/2의 중요한 부분은 n^2/2가 되며 이것은 (1/2)n^2.
- 계수를 제외하면 n^2이 남기 때문에 O(n^2) 으로 표현.
- 선택 정렬
- O( n^2)으로 표현
- n개의 자료가 있다면 첫 번째 자료와 나머지 n-1개의 자료 중 가장 작은 값의 자리를 교환해줘야함
- n-1개의 자료 중 가장 작은 값을 찾기 위해선 n-1번의 비교가 필요
- 즉, (n-1) + (n-2) + … + 1이며 시간복잡도는 O( n^2)으로 표현.
- 삽입 정렬
- O( n^2)으로 표현
- n개의 자료가 있다면 첫 번째 자료는 정렬이 되었다고 생각하고,
- n-1개의 자료 중 첫 번째 자료와 정렬된 자료를 비교.
- 이때 정렬된 자료는 1개이기 때문에 비교 횟수는 1
- 정렬되지 않은 부분에 1개의 자료가 남게 되면, 정렬된 자료의 수 n-1개 만큼의 비교가 필요.
- 따라서, 비교 횟수는 1 + 2 + … + (n-1)이며 시간복잡도는 O( n^2)으로 표현.
Big Ω(omega) 표기법
- Big-O와 반대되는 개념으로 최선의 경우를 나타냄.
- 선형 탐색
- 배열의 크기와 상관없이 Ω(1)라고 나타냄
- 최선의 경우 -> 배열의 처음에 찾고자 하는 값이 있는 상황.
- 버블 정렬
- Ω(n)
- 최선의 경우 -> 이미 정렬된 배열
- 교환이 이루어지지 않더라도 배열이 정렬됐단 사실을 모르기 때문에 여전히 n-1번의 비교를 해줘야 함.
- 선택 정렬
- Ω(n^2)
- 버블 정렬과 마찬가지로 배열이 정렬되었다는 것을 알 수 없음
- 삽입 정렬
- Ω(n)
- 정렬되지 않은 부분에서 정렬된 부분으로 옮겨갈 때,
- 정렬된 부분의 가장 큰 수와 비교하기만 하면 되기 때문.
정리
Comments