로가리즘(log)

O(logN)을 이해하려면 먼저 로가리즘을 이해해야한다.

왜 이진 검색 같은 알고리즘을 O(logN)이라 표현할까?
log는 무엇일까?
로그는 로가리즘의 줄임말이다.
우선 로가리즘과 알고리즘은 비슷하지만 전혀 관련없는 단어이다.

로가리즘은 지수(exponent)와 역(inverse)의 관계이다.
지수 : $2^4$ 에서 제곱의 위치에 있는 수를 지수라고 부른다.
역 : $log_2 8$ < -- > $2^3$

---

2의 3제곱은 2 x 2 x 2와 같다.
$\log_2 8$은 $2^3$의 역(converse)이다.
즉 2를 몇 번 곱해야 8을 얻을 수 있는지를 뜻한다.
2를 세 번 곱해야 8이 나오므로 $log_2 8 = 3$이다.

이 처럼 2를 6번 곱해야 64가 나오므로 $log_2 64 = 6$이다.

다른 방식으로도 표현할 수 있다.
$log_28$을 다른 방식으로 표현하자면 1이 될 때 까지 8을 2로 나눌 때 등식에 등장하는 2는 몇개인지 구하면 된다.

다시 말해 1이 나올 때까지 8을 2로 몇 번 나눠야 할까? 위 수식에서 3번이다. 따라서

이다.