시간 복잡도 분석

1. 알고리즘의 효율을 비교하려면?

두 알고리즘 A와 B를 비교할 때 다음과 같은 문제점이 있습니다:
1. 모호한 표현: "A가 B보다 조금 빠르다"와 같은 표현은 정확하지 않음.
2. 환경 의존성: 실행 속도 비교는 하드웨어, 운영 체제, 컴파일러 등에 따라 달라질 수 있음.
3. 입력 크기: 작은 입력에서는 두 알고리즘 간 차이가 크지 않지만, 입력이 커질수록 성능 차이가 극명하게 드러날 수 있음.

Big-O 표기법이 해결하는 문제

• 실행 시간 대신 연산의 수를 기준으로 비교.
• 입력 크기 ( N )에 따라 성능을 표현.
• 알고리즘의 최악의 경우를 예측하여 성능을 정량적으로 평가.

---

2. Big-O 표기법의 단계별 분석

2.1 1단계: 대략적인 연산 수 계산

• 알고리즘이 입력 데이터 ( N )에 대해 수행하는 산술, 비교, 대입 연산의 개수를 판단합니다.
• 예:

  for (int i = 0; i < N; i++) {
      cout << i;
  }

  • 위 코드의 반복문은 ( N )번 실행되므로, 연산 수는 ( O(N) )입니다.

---

2.2 2단계: 대표 항목만 남기기

• 알고리즘 성능에 가장 큰 영향을 미치는 대표 항목만 남기고 나머지는 제거합니다.
• 상수는 무시:
  • ( O(3N) ) → ( O(N) ) (상수 3 제거)
• 가장 큰 항만 유지:
  • ( O($N^2$ + N + 1) ) → ( O($N^2$) ) (입력 크기가 커질수록 ( $N^2$ )이 지배적)

---

2.3 Big-O 표기법의 의미

• Big-O는 입력 크기 ( N )이 증가함에 따라 알고리즘의 연산량(시간 복잡도)이 증가하는 비율을 나타냅니다.
• 실제 실행 시간은 하드웨어에 따라 달라질 수 있으나, Big-O는 하드웨어와 무관한 상대적 효율성을 평가합니다.

---

3. 시간 복잡도의 주요 유형

3.1 상수 시간: O(1)

• 입력 크기와 관계없이 일정한 시간이 걸림.
• 예:

  int x = arr[0]; // 배열의 첫 번째 요소 접근

---

3.2 로그 시간: O(log N)

• 입력 크기가 증가해도 처리 시간이 완만히 증가.
• 예: 이진 탐색

  int binarySearch(int arr[], int n, int target) {
      int low = 0, high = n - 1;
      while (low <= high) {
          int mid = (low + high) / 2;
          if (arr[mid] == target) return mid;
          else if (arr[mid] < target) low = mid + 1;
          else high = mid - 1;
      }
      return -1;
  }

  • 배열의 크기가 16일 때: 최대 4번의 비교.
  • 배열의 크기가 32일 때: 최대 5번의 비교.

---

3.3 선형 시간: O(N)

• 입력 크기에 비례하여 시간이 증가.
• 예:

  for (int i = 0; i < N; i++) {
      cout << i;
  }

---

3.4 선형 로그 시간: O(N log N)

• 대표적으로 병합 정렬과 같은 효율적인 정렬 알고리즘이 해당.
• 예:
  • 데이터 분할: ( O(log N) ).
  • 각 단계에서 전체 데이터 처리: ( O(N) ).

---

3.5 이차 시간: O($N^2$)

• 중첩 반복문을 사용하는 알고리즘.
• 예: 버블 정렬

  for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
          if (arr[i] > arr[j]) swap(arr[i], arr[j]);
      }
  }

---

3.6 지수 시간: O($2^N$)

• 입력 크기가 커질수록 시간이 기하급수적으로 증가.
• 예: 피보나치 수열 (재귀)

  int fibonacci(int n) {
      if (n <= 1) return n;
      return fibonacci(n - 1) + fibonacci(n - 2);
  }

---

4. 벡터(Vector)와 리스트(List)의 성능 비교

4.1 Vector의 시간 복잡도

• 삽입/삭제:

  • 시작: ( O(N) ) (모든 요소를 한 칸씩 이동)
  • 중간: ( O(N) ) (중간 삽입 시 나머지 요소 이동 필요)
  • 끝: ( O(1) ) (추가적인 메모리 할당이 없을 경우)

• 임의 접근: ( O(1) ) (인덱스를 통한 직접 접근 가능)

---

4.2 List의 시간 복잡도

• 삽입/삭제:

  • 시작: ( O(1) ) (노드 연결만 변경)
  • 중간: ( O(1) ) (현재 노드와 새 노드 연결)
  • 끝: ( O(1) ) (노드 연결만 변경)

• 임의 접근: ( O(N) ) (특정 위치까지 순차 접근 필요)

---

5. LOG 함수의 의미

5.1 LOG 함수란?

• 로그 함수는 지수의 반대 개념으로, 알고리즘의 성능 분석에서 자주 사용됩니다.
• LOG의 의미: ( $\log_b N = x$ )는 ( $b^x$ = N )을 의미합니다.

5.2 LOG 함수와 알고리즘

1. 이진 탐색:

   • ( O($\log N$) ): 탐색 범위를 절반씩 줄이기 때문에 로그 시간.
   • 데이터 크기가 커질수록 효율적.

2. 정렬 알고리즘:

   • 병합 정렬, 힙 정렬 등은 ( O($N \log N$) )의 성능을 가짐.

---