1. 사전적 정의

Big-O Notation은 알고리즘의 성능을 설명하기 위한 수학적 표기법으로, 주로 입력 크기와 관련하여 알고리즘이 얼마나 빠르거나 느린지, 얼마나 많은 메모리를 사용하는지를 평가하는 데 사용된다. Big-O는 알고리즘의 시간 복잡도와 공간 복잡도를 나타내며, 최악의 경우의 수행 시간을 설명하는 데 주로 사용된다.

2. 주요 Big-O Notation 종류

1. O(1) - 상수 시간 복잡도

• 입력 크기와 상관 없이 항상 일정한 시간 내에 작업을 완료하는 알고리즘
• 예시: 배열의 특정 요소에 접근하는 연산

2. O(log n) - 로그 시간 복잡도

• 입력 크기가 커질 수록 시간이 느리게 증가하는 알고리즘
• 예시: 이진 탐색 트리에서 요소를 찾는 경우

3. O(n) - 선형 시간 복잡도

• 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘
• 예시: 리스트에서 모든 요소를 한 번씩 탐색하는 경우

4. O(nlog n)

• 대부분의 효율적인 정렬 알고리즘의 시간 복잡도
• 입력 크기와 로그의 곱에 비례하는 시간 복잡도를 가짐
• 예시: Quick Sort, Merge Sort 등

5. O(n^2) - 이차 시간 복잡도

• 이중 루프를 사용하는 경우로, 입력 크기의 제곱에 비례하여 시간이 증가하는 알고리즘
• 예시: 이중 반복문을 사용하는 버블 정렬

6. O(2^n) - 지수 시간 복잡도

• 입력 크기가 커질 수록 실행 시간이 매우 빠르게 증가하는 알고리즘
• 보통 재귀적으로 많은 경우의 수를 탐색하는 알고리즘에서 발생
• 예시: 피보나치 수열을 재귀적으로 계산하는 알고리즘 (단순한 경우)

7. O(n!) - 팩토리얼 시간 복잡도

• 매우 비효율적인 알고리즘으로, n개의 요소에 대해 가능한 모든 순열을 탐색할 때 발생
• 예시: 여행하는 외판원 문제(Brute-force 접근)

3. Big-O Notation을 사용하는 이유

• 코드의 성능을 수학적으로 평가하여, 다양한 입력에 대해 어떻게 작동할지를 예측하고 비교할 수 있게 해줌
• 최적화해야 할 부분이나 비효율적인 알고리즘을 식별하는 데 도움을 줌
• 어떤 알고리즘이 특정 문제에 더 적합한지를 판단하는 기준이 됨

4. 알고리즘 별 시간복잡도

1. 정렬 알고리즘

• 버블 정렬 (Bubble Sort)

  • 시간 복잡도: 최선 - O(n), 평균/최악 - O(n^2)
  • 인접한 두 요소를 비교하여 교환하며 정렬. 정렬이 완료될 때까지 여러 번 배열을 순회하며, 비효율적이지만 간단한 정렬 방식

• 삽입 정렬 (Insertion Sort)

  • 시간 복잡도: 최선 - O(n), 평균/최악 - O(n^2)
  • 배열을 탐색하면서 각 요소를 이미 정렬된 부분과 비교하여 알맞은 위치에 삽입. 정렬이 거의 되어 있을 때 효율적

• 선택 정렬 (Selection Sort)

  • 시간 복잡도: O(n^2)
  • 배열에서 가장 작은(또는 큰) 요소를 선택하고 정렬되지 않은 부분의 첫 번째 요소와 교환하는 방식으로 정렬

• 병합 정렬 (Merge Sort)

  • 시간 복잡도: 최선/평균/최악 - O(n logn)
  • 배열을 반으로 나누고 각 부분을 재귀적으로 정렬한 후, 두 부분을 병합하여 최종 정렬. 안정 정렬이며 효율적.

• 퀵 정렬 (Quick Sort)

  • 시간 복잡도: 평균 - O(n logn), 최악 - O(n^2)
  • 피벗을 선택하고 피벗보다 작은 요소와 큰 요소로 분할한 후 재귀적으로 정렬하는 방식. 평균적으로 빠른 성능을 보임.

• 힙 정렬 (Heap Sort)

  • 시간 복잡도: O(n log n)
  • 최대 힙이나 최소 힙을 생성하여 정렬. 배열을 트리 구조로 표현해 정렬하는 방식.

• 계수 정렬 (Counting Sort)

  • 시간 복잡도: O(n + k) (k는 데이터의 최대 값)
  • 정수나 정해진 범위의 데이터를 정렬할 때, 각 요소의 발생 횟수를 카운트하여 정렬.

2. 탐색 알고리즘

• 이진 탐색 (Binary Search)
  • 시간 복잡도: O(log n)
  • 정렬된 배열에서 중간 요소와 목표 값을 비교하고, 절반씩 나누어 탐색하는 방식.
• 선형 탐색 (Linear Search)
  • 시간 복잡도: O(n)
  • 배열의 첫 번째 요소부터 하나씩 비교하며 찾고자 하는 값을 찾는 방식.

3. 자료구조 관련

• 스택, 큐 삽입/삭제 연산
  • 시간 복잡도: O(1)
  • 스택은 LIFO(Last In, First Out) 구조로, 가장 최근에 삽입된 요소가 먼저 제거됨. 큐는 FIFO(First in, First Out) 구조로, 가장 먼저 삽입된 요소가 먼저 제거됨.
• 이진 검색 트리(BST) 탐색, 삽입, 삭제
  • 평균 시간 복잡도: O(log n), 최악의 경우: O(n)
  • 각 노드의 왼쪽 하위 노드는 그 노드보다 작고, 오른쪽 하위 노드는 그 노드보다 큰 트리 구조
• 해시 테이블 삽입/검색
  • 평균 시간 복잡도: O(1), 최악의 경우: O(n) (해시 충돌이 발생할 경우)
  • 키-값 쌍을 저장하며, 해시 함수를 사용하여 데이터를 빠르게 검색하는 자료구조

4. 그래프 알고리즘

• 너비 우선 탐색(BFS)
  • 시간 복잡도:
    • 인접 리스트: O(V + E) (V는 노드 수, E는 간선 수)
    • 인접 행렬: O(n * m)
  • 그래프의 정점들을 너비 우선으로 탐색. 큐를 사용하여 가까운 정점부터 탐색하는 방식
• 깊이 우선 탐색(DFS)
  • 시간 복잡도:
    • 인접 리스트: O(V + E) (V는 노드 수, E는 간선 수)
    • 인접 행렬: O(n * m)
  • 그래프의 정점들을 깊이 우선으로 탐색. 스택을 사용하거나 재귀를 통해 한 방향으로 끝까지 탐색한 후, 다른 경로를 탐색.
• 다익스트라 알고리즘 (Dijkstra's Algorithm)
  • 시간 복잡도: O(V^2), 개선된 구현에서는 O(E + V log V)
  • 가중치가 있는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
• 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)
  • 시간 복잡도: O(V^3)
  • 모든 정점 쌍에 대한 최단 경로를 찾는 알고리즘. 동적 프로그래밍을 사용.