유사개발자 샤이와 무지

얼마전 지하철 안에서 그런 생각이 들었다. "근데 시간복잡도가 log가 나오는 경우가 발생할 수 있긴 한가? 어떻게하면 log가 튀어나올까?" 그리고 이곳저곳을 둘러보게 되는데 이런 결론이 나왔다. 이진 트리에서 총 데이터의 개수가 N개라고 하고 그 데이터 중에서 특정 데이터를 1개 찾아내는데 최악을 가정한다면? 그 깊이가 k라 가정할때 데이터는 Leaf Node에 있을 것이고 마지막 데이터의 수는 1 = N X 2^(-k)이므로 식을 풀어보면 1 = N X 2^(-k) log_2(1) = log_2(N X 2^(-k)) #양변에 log_2를 취함 0 = log_2(N) -k #어떤 수의 제곱수가 1이 되는 케이스는 0일때 밖에 없다 = 로그 내의 곱은 로그 밖에서의 합이다 k = log_2(N) 이란 ..