시간복잡도

시간 복잡도는 알고리즘의 수행 시간을 분석하는 것으로, 입력 데이터의 크기에 따른 알고리즘의 수행 시간 증가율을 나타내는 것입니다. 자료구조에서 사용되는 여러 연산들(탐색, 삽입, 삭제 등)의 시간 복잡도는 알고리즘의 성능을 파악하는데 중요한 지표가 됩니다.

시간 복잡도는 대개 O 표기법(Big-O Notation)을 사용하여 표현됩니다. 이 표기법에서 O는 "최악의 경우(Worst Case)"의 시간 복잡도를 나타내며, n은 입력 데이터의 크기를 나타냅니다. 예를 들어, O(1)은 입력 데이터의 크기와 관계없이 항상 일정한 시간만큼 수행된다는 것을 의미합니다.

일반적으로 사용되는 시간 복잡도의 종류는 다음과 같습니다.

1. O(1) : 상수 시간(Constant Time)

• 입력 데이터의 크기와 관계없이 항상 일정한 시간만큼 수행됩니다.
• 예: 배열(Array)에서의 인덱스 접근, 해시 테이블(Hash Table)에서의 탐색, 큐(Queue)와 스택(Stack)에서의 삽입과 삭제

1. O(log n) : 로그 시간(Logarithmic Time)

• 입력 데이터의 크기가 2배가 되어도 수행 시간이 약간씩 증가합니다.
• 예: 이진 검색(Binary Search), AVL 트리와 레드-블랙 트리에서의 검색, 힙(Heap)에서의 삽입과 삭제

1. O(n) : 선형 시간(Linear Time)

• 입력 데이터의 크기와 비례하여 수행 시간이 증가합니다.
• 예: 배열에서의 선형 탐색, 리스트(List)에서의 탐색, 트리(Tree)에서의 전위, 중위, 후위 순회

1. O(nlog n) : 로그 선형 시간(Log-Linear Time)

• 입력 데이터의 크기가 증가함에 따라 수행 시간이 빠르게 증가합니다.
• 예: 퀵 정렬(Quick Sort), 머지 정렬(Merge Sort), 힙 정렬(Heap Sort)

1. O(n^2) : 이차 시간(Quadratic Time)

• 입력 데이터의 크기가 조금만 커져도 수행 시간이 급격히 증가합니다.
• 예: 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort)

1. O(2^n) : 지수 시간(Exponential Time)

• 입력 데이터의 크기