BST의 시간복잡도 O(log N) 증명하기

BST를 탐색하는 시간복잡도가 O(logN)이라고 한다.

이를 어떻게 유도할 수 있나?

유도 과정

기본적으로 크기가 N인 ordered array가 있다고 해 보자.

Binary search tree의 매커니즘과 동일하게 생각해보면, 우리는 숫자의 범위를 절반씩 잘라가는 행위를 결국에는 남은 숫자의 개수가 1이 될 때 까지 반복할 것이다. 이렇게 반복한 횟수를 k번이라 해 보자. (즉, 여기서 k가 의미하는 것은 결국 해당 연산을 몇 번 수행하냐를 의미하게 되며, 이는 BST의 탐색 연산 횟수와 같다.)

이를 수식화하면 N * (1/2)^k = 1 라고 표현할 수 있다. 이는 N = 2^k와 같다. 따라서 양 변에 밑이 2인 log를 취하면 log N = k 라는 결과가 나온다. 이는 N개의 숫자를 갖는 BST에서의 탐색 알고리즘은 log N이라는 시간복잡도를 갖는다는 것에 대한 증명이 된다.