로그 함수와 알고리즘 특징

---

로그 함수 §

${\log }_b(a)=x$ >>> $b^x=a$ ex)

• ${\log }_2(8)=3$ >>> $2^3=8$

로그 함수 특징 §

로그 성장 : 로그 함수의 값은 입력 값이 커짐에 따라 증가하지만, 그 증가율은 점차 감소한다.

로그 복잡도 $O(\log n)$ §

• 알고리즘의 실행 시간이 입력 크기 $n$ 에 비례하게 증가함을 의미함
• 이는 입력 크기가 두 배로 증가할 때마다 알고리즘의 실행 시간이 한 단계만 증가한다는 것을 의미함
  • ex) 입력 크기 : 8
    • ${\log }_2(8)=3$
    • 실행 시간 : 3
  • 입력 크기 : 16
    • ${\log }_2(16)=4$
    • 실행 시간 : 4
• 이러한 로그 성장의 특성 때문에, 로그 시간 복잡도를 가진 알고리즘은 큰 입력 데이터에 대해 효율적이며 빠른 성능을 보임