[자료구조] 이진트리와 시간복잡도 로그의 의미

이진트리란?

: 모든 노드의 차수가 0 이상 2 이하인 트리

 

이진트리 모습

이진트리의 시간복잡도는 O(log(n))이라고 들어왔을 겁니다. 하지만 그 과정은 모르는 경우가 많다.(필자도 그랬다)

 

그래서 과정을 설명하려고 합니다. 그리고 왜 이진트리를 사용할수록 2배씩 빨라진다고 말하는지도 알아보도록 하겠습니다.

 

1. 이진트리 시간복잡도 계산

 

트리는 h의 높이를 가질때 최대 n = 2^h - 1의 노드 수를 가지고 최소 n = h의 노드 수를 가집니다.

 

최대	n = 2h - 1
최소	n = h

 

기억할 것은 최대 노드의 개수!!

 

왜냐하면 빅오 표기법은 최악을 기준으로 삼기 때문에 가장 오래 걸리는 기준은 노드 수가 가장 많은 경우이기 때문입니다.

 

n = 2^h - 1

 

n + 1 = 2^h

 

log(n + 1) = h

 

h = log(n)

 

==> O(log(n))

 

이진트리의 시간 복잡도는 이렇게 구합니다.

(로그의 밑인 2는 생략한 것을 기억해 주세요)

 

2. 이진트리가 2배씩 빠르다는 의미

 

로그의 성질에 의해 [x = log_a^b]는 a를 b로 만드는 지수는 x라는 의미이다.

 

이진트리에서는 a가 2이기 때문에 그리고 지수 x가 아닌 로그이기 때문에 2배씩 시간이 덜 걸리게 됩니다.