파이썬 알고리즘 테스트: 자료구조
파이썬 알고리즘 테스트
빅오 표기법
빅오(big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법
| 표기 | 설명 | 활용 예시 |
|---|---|---|
| $O(1)$ | 입력값이 아무리 커도 실행 시간이 일정 | 해시 테이블의 조회 및 삽입 |
| $O(log n)$ | 로그는 매우 큰 입력값에도 크게 영향을 받지 않음 | 이진 검색 |
| $O(n)$ | 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간이 입력값에 비례(선형 시간, Linear-Time) 알고리즘 | 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우(모든 입력값을 적어도 한 번 이상 살펴봐야 하는 경우) |
| $O(n log n)$ | 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘 | 병합 정렬 |
| $O(n^2)$ | 비효율적인 정렬 알고리즘 | 버블 정렬 |
| $O(2^n)$ | 재귀로 계산하는 알고리즘 | 피보나치 수를 재귀로 계산하는 알고리즘 |
| $O(n!)$ | 가장 느린알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어려움 | 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(Traveling Sales Problem, TSP)를 브루트 포스로 풀이 할 때 해당 |
정렬 알고리즘 별 시간 복잡도
| 알고리즘 | 최선 | 평균 | 최악 |
|---|---|---|---|
| 퀵 정렬 | $\Omega (n log n)$ | $\theta (n log n)$ | $ O (n^2)$ |
| 병합 정렬 | $\Omega (n log n)$ | $\theta (n log n)$ | $ O (n log n)$ |
| 팀소트 | $\Omega (n)$ | $\theta (n log n)$ | $ O (n log n)$ |
선형 자료 구조
자료 구조는 크게 메모리 공간 기반의 연속(Contiguous) 방식과 포인터 기반의 연결(Link) 방식으로 나뉨.
배열
배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.
배열은 연속(Contiguous) 방식의 가장 기본이 되는 자료 형
✔️ 정적 배열 vs 동적 배열
정적 배열은 고정된 크기만큼의 연속된 메모리 할당
동적 배열은 크기를 지정하지 않고 자동으로 리사이징 하는 배열
Python에서는 리스트가 동적 배열 자료 형으로 정적 배열은 따로 제공하지 않음
✔️ 동적 배열 원리
미리 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사
- 보통 2배씩 늘려준다하여 더블링, Doubling이라 함.
Cpython의 listobject.c
// cpython/Objects/listobject.c
// The growth pattern is: 0,4,8,16,25,35,46,58,72,88, ...
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)
- 재할당 비율을 그로스 팩터(Growth Factor), 다른 말로 ‘성장 인자’라고 한다.