logN의 시간 복잡도 (펌)

이진탐색트리를 공부하다가 O(logn) 의 시간복잡도에 대해 이해가 잘 가지 않아서 구글링하던 중 너무 명쾌한 글을 발견하여 가져온다.

https://neos518.tistory.com/145

내용을 조금 각색해서 써보자면..

예를 들어 2개의 자식 노드를 가지는 이진트리를 이용해서 M개의 노드 중 원하는 값의 노드를 찾는다고 해보자. 처음에는 M개의 노드 모두 탐색 대상이지만, 루트 노드에서 첫번째 자식 노드 층으로 이동하게 되면 절반으로 줄게 된다.
M/2 개 => M/4 개 => M/8 개 => ...
만약 탐색을 해야하는 자료의 수가 2^n 개라면, 이진 트리를 사용할 경우 n번의 탐색을 통해서 원하는 값을 찾을 수 있게 된다. 이를 수식으로 나타내면 아래와 같다.
이를 일반화하면, 각 노드의 자식노드가 M개인 트리에서 N개의 자료 중 원하는 자료를 탐색하는 알고리즘의 시간 복잡도는 아래와 같다.

위의 예들을 대상으로 구체적인 숫자를 대입해보면 이해하기에 좋다. 총 8개의 노드가 있는 이진탐색트리가 있다고 생각한다면 한번 탐색할 때마다 8 => 4 => 2 => 1 로 줄어들어 3번의 시행으로 원하는 노드를 찾아낼 수 있다.