logN의 시간 복잡도가 나오는 이유

흔히 알고리즘을 공부하다보면 logN의 시간 복잡도를 심심치 않게 만나게 된다.

이미 대다수의 사람들이 트리를 사용할 때 시간 복잡도가 로그 값이 나온다는 사실에 대해서 알고 있을 것이다.

이때, 많은 사람들이 이 로그의 값이 어디에서 나오게 된 것인지 제대로 이해를 하지 않고, 단순히 암기를 하려고 한다.

 

사실, logN의 시간 복잡도가 나오는 이유는 그리 어렵지 않다.

예를 들어서 2개의 자식 노드를 가지는 이진 트리(binary tree)를 이용해서 M개의 값들 중에서 원하는 값을 찾는다고 해 보자.

처음에는 M개의 값들 모두 탐색 대상이지만, 루트 노드에서 첫 번째 자식 노드 층으로 이동하게 되면 그 수가 절반으로 줄게 된다.

이제 M/2개의 값들이 남게 되는데, 다시 한번 다음 자식 노드 층으로 넘어가게 되면 M/4개의 값들이 남게 된다.

이런 식으로 매번 층을 내려갈 때마다 남은 값의 수들이 절반이 되게 된다.

 

만약 탐색을 해야 하는 자료의 수가 2^n 개라면, 이진 트리를 사용할 경우 n번의 탐색을 통해서 원하는 값을 찾을 수 있게 된다.

log_2(2^n) = n 이기 때문에, 이진 탐색 트리(Binary Search Tree)를 이용한 이진 탐색 기법의 시간 복잡도가 log_2(N)이 되는 것이다.

 

다시 말해서, 자식 노드의 수가 m개인 트리로 N개의 자료에서 원하는 값을 탐색하는 알고리즘의 시간 복잡도는 log_m(N)이 된다.