자료구조·알고리즘 복잡도 정리
탐색·정렬·트리·그래프의 대표 복잡도와 선택 기준을 정리합니다.
관련 시험 9급 컴퓨터일반정보처리기사
복잡도 해석
빅오 표기법은 입력 크기가 커질 때 증가율의 상한을 중심으로 비교합니다. 상수와 낮은 차수 항을 제거하되, 입력 특성과 평균·최악 조건을 함께 확인해야 합니다.
- 이진 탐색은 정렬된 배열에서 O(log n)이다.
- 해시 탐색은 평균 O(1)이지만 충돌에 따라 달라진다.
- 중첩 반복문의 범위가 종속되면 단순히 차수를 곱하지 않는다.
정렬 비교
퀵 정렬은 평균적으로 빠르지만 피벗 분할이 치우치면 최악 O(n²), 병합 정렬은 O(n log n)을 보장하지만 추가 메모리가 필요합니다. 힙 정렬도 O(n log n)을 보장합니다.
- 삽입 정렬은 거의 정렬된 자료에 유리하다.
- 병합 정렬은 안정 정렬이다.
- 선택 정렬은 교환 횟수가 비교적 적다.
트리와 그래프
이진 탐색 트리는 왼쪽이 작고 오른쪽이 큰 순서 관계를 사용합니다. BFS는 큐, DFS는 스택 또는 재귀를 사용하며 최단 경로 조건을 구분해야 합니다.
- 가중치가 없는 그래프의 최소 간선 경로에는 BFS가 적합하다.
- 최소 신장 트리는 모든 정점을 사이클 없이 연결한다.
- 균형이 무너지면 이진 탐색 트리의 탐색이 O(n)이 될 수 있다.
자주 틀리는 판단
- 퀵 정렬의 최악 복잡도를 O(n log n)으로 단정
- BFS와 DFS의 자료구조를 반대로 암기
- 안정 정렬과 제자리 정렬을 같은 개념으로 판단
개념을 확인했다면 실제 문제에서 판단 기준을 적용해보세요.
분야별 문제 풀기