🧩 [Data Structure] 로그 시간(logarithmic time)이란?

🍎 Intro.

• 로그 시간(logarithmic time)은 시간 복잡도를 분석할 때 사용하는 용어로, 어떤 알고리즘이나 연산이 수행될 때 입력 크기(N)에 따라 작업 시간이 입력 크기의 로그 값에 비례하는 경우를 의미합니다.

✅1️⃣ 로그 시간의 정의.

• 로그 시간은 입력 크기 N이 증가하더라도 연산 시간 증가가 매우 느린 경우를 나타냅니다.
• 시간 복잡도를 표현할 때 O(log N)으로 나타냅니다.

✅2️⃣ 로그 시간의 의미.

• 만약 입력 크기 N이 2배로 늘어나도, 연산 시간은 1회 정도만 추가되는 방식으로 증가합니다.
  • 이는 로그(logarithm)의 성질에 기인하며, 효율적인 알고리즘의 특징입니다.

✅3️⃣ 로그 시간의 예시.

1️⃣ 이진 탐색(Binary Search) - O(log N)

• 이진 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용됩니다.
  • 배열을 절반으로 나누는 방식으로 탐색하므로, 입력 크기 N에 대해 시간 복잡도는 O(log N)입니다.

📌2️⃣ 예시.

• 배열 크기: N = 16
• 비교 횟수:
  • 첫 번째 비교 ➞ 크기 16 ➞ 8로 줄어듦.
  • 두 번째 비교 ➞ 크기 8 ➞ 4.
  • 세 번째 비교 ➞ 크기 4 ➞ 2.
  • 네 번째 비교 ➞ 크기 2 ➞ 1에서 종료.
• 총 비교 횟수: log₂(16) = 4

3️⃣ B-Tree와 B+ Tree 검색 - O(log N)

• B-Tree와 B+ Tree는 데이터베이스와 파일 시스템에서 사용되는 효율적인 데이터 구조입니다.
• 트리의 높이가 log에 비례하므로, 검색과 삽입/삭제 연산 모두 O(log N)의 시간 복잡도를 가집니다.

📌4️⃣ 예시.

• 데이터 개수: N = 1,000
• B+ Tree에서 최대 100개의 자식을 가진다면, 트리의 높이는 log₁₀(1,000) = 3
• 검색 시간은 3단계만에 원하는 데이터를 찾을 수 있습니다.

4️⃣ 이벤트 처리와 분할 정복 알고리즘.

• Merge Sort와 같은 분할 정복 알고리즘에서도 로그 시간이 나타납니다.
  • 문제를 절반으로 나누어 재귀적으로 처리하므로, 깊이는 log N에 비례합니다.
  • 병합 과정의 시간은 O(N), 따라서 전체 시간 복잡도는 O(N log N)입니다.

✅4️⃣ 로그 시간의 특징.

1️⃣ 효율성:

• 로그 시간 복잡도는 대규모 데이터를 처리할 때 매우 효율적입니다.
  • 데이터 크기 N이 기하급수적으로 증가하더라도, 작업 시간은 느리게 증가합니다.

2️⃣ 적용 사례:

• 검색 알고리즘 : 이진 탐색(Binary Search), B-Tree, AVL Tree, Hash Table 등.
• 정렬 알고리즘 : Merge Sort, Heap Sort 등.
• 파일 시스템 및 데이터베이스 : 인덱스 검색(B+ Tree).

3️⃣ 기본 수학:

• 로그 시간은 log₂(N) 또는 log₁₀(N) 같은 수학적 로그 함수의 성질에 기초합니다.

🚀5️⃣ 정리

• 로그 시간(logarithmic time)은 O(log N)의 시간 복잡도를 의미하며, 데이터 크기가 증가해도 연산 시간이 느리게 증가합니다.
  • 이는 이진 탐색, 트리 기반 구조, 분할 정복 알고리즘 등에서 나타나는 효율적인 시간 복잡도입니다.