빅오표기법
정의
알고리즘의 시간복잡도와 공간복잡도를 분석하는 방법
즉, 입력 크기(n)가 증가할 때 실행 시간이 어떻게 변하는지를 나타내는 수학적 표기법특징
- 최악의 경우(Worst Case)를 기준으로 분석
- 입력 크기 n이 커질 때 성능이 가장 나쁜 상황을 가정
- 예를 들어, 정렬 알고리즘에서 최악의 경우를 고려하는 이유는 안정적인 성능 예측을 위해서임
- 상수 및 낮은 차수 항 무시
- 예를 들어, O(2n + 5)는 O(n)으로 단순화됨
- 상수 시간은 입력 크기가 매우 커질 때 무의미해지기 때문
- 입력 크기 n이 증가할 때 알고리즘의 실행 속도를 표현
- 작은 입력에서는 차이가 크지 않지만, n이 매우 커질 때 어떤 알고리즘이 더 효율적인지 판단할 수 있음
주요 시간 복잡도 종류
빅오 성능 비교 그래프
- O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!) 순으로 성능이 나빠짐
시간복잡도
정의
- 알고리즘이 실행되는 데 걸리는 시간을 나타내는 척도
공간복잡도
정의
- 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 나타내는 척도
자료구조
배열(Array)
- 시간 복잡도:
접근: O(1) (인덱스를 통해 바로 접근할 수 있기 때문에)
삽입/삭제: O(n) (중간에 삽입하거나 삭제할 때, 뒤에 있는 원소들을 모두 이동해야 하므로)- 공간 복잡도: O(n) (배열에 저장된 원소의 개수만큼 메모리를 사용)
배열은 간단하고, 인덱스를 통해 빠르게 접근할 수 있지만, 삽입이나 삭제가 비효율적일 수 있습니다.연결 리스트(Linked List)
- 시간 복잡도:
접근: O(n) (특정 위치로 접근하려면 첫 번째 노드부터 차례대로 따라가야 함)
삽입/삭제: O(1) (특정 위치에서 삽입하거나 삭제하려면 해당 노드만 알고 있으면 됨)- 공간 복잡도: O(n) (각 노드마다 데이터 외에도 링크(포인터)가 추가로 필요)
연결 리스트는 삽입/삭제가 배열에 비해 효율적이지만, 특정 인덱스로의 접근이 느리다는 단점이 있습니다.스택(Stack)
- 시간 복잡도:
push: O(1)
pop: O(1)
peek (가장 최근 요소 확인): O(1)- 공간 복잡도: O(n) (스택에 저장된 원소 개수에 비례)
스택은 후입선출(LIFO) 방식으로 데이터를 처리하는 자료구조로, 주로 재귀 호출, 괄호 검사 등에서 활용됩니다. 삽입과 삭제는 매우 효율적입니다.해시 테이블(Hash Table)
- 시간 복잡도:
삽입: O(1) (평균적으로 매우 빠름, 하지만 해시 충돌이 발생하면 O(n)이 될 수 있음)
검색: O(1) (평균적으로 매우 빠름, 해시 충돌 시 O(n))
삭제: O(1) (평균적으로 매우 빠름, 해시 충돌 시 O(n))- 공간 복잡도: O(n)
해시 테이블은 키-값 쌍을 빠르게 검색할 수 있는 자료구조로, 데이터베이스나 캐시 시스템에서 매우 중요한 역할을 합니다. 해시 충돌이 발생할 경우 성능이 떨어질 수 있습니다.이진 탐색 트리(Binary Search Tree, BST)
- 시간 복잡도:
삽입: O(log n) (균형 잡힌 트리일 경우)
검색: O(log n) (균형 잡힌 트리일 경우)
삭제: O(log n) (균형 잡힌 트리일 경우)- 공간 복잡도: O(n)
이진 탐색 트리는 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 특성을 가집니다. 하지만 트리가 불균형할 경우 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.다익스트라 알고리즘(Dijkstra's Algorithm)
- 시간 복잡도:
기본 구현: O(V^2), V는 정점의 수 (인접 행렬을 사용할 경우)
우선순위 큐를 사용하는 구현: O((V + E) log V), E는 간선의 수- 공간 복잡도: O(V + E) (그래프를 표현하는데 필요한 공간)
다익스트라는 그래프에서 두 정점 간의 최단 경로를 구하는 알고리즘으로, 우선순위 큐를 활용하면 효율적으로 최단 경로를 계산할 수 있습니다.퀵 정렬(Quick Sort)
- 시간 복잡도:
평균: O(n log n)
최악: O(n^2) (피벗 선택이 나쁠 경우)- 공간 복잡도: O(log n) (분할 과정에서 호출 스택이 사용됨)
퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘입니다. 하지만 최악의 경우는 O(n^2)로 비효율적이므로, 피벗을 잘 선택하는 것이 중요합니다.병합 정렬(Merge Sort)
- 시간 복잡도:
최선/평균/최악: O(n log n)- 공간 복잡도: O(n) (임시 배열을 사용하기 때문에 추가 메모리가 필요)
병합 정렬은 안정적인 정렬 알고리즘으로, 항상 O(n log n) 시간 복잡도를 보장합니다. 추가적인 메모리가 필요하지만, 대체로 일관된 성능을 제공합니다.
