이진 검색 트리에서 Big O에 대한 로그의 기본은 무엇입니까

Question

이 표에서와 같이 평균 시간 복잡성을 논의 할 때.

O (로그 n)이

나는이 2 가정 만 확인하고 싶어 해요. 또한이 데이터 구조에 대해 항상 2입니까? 상수는 중요하지 않습니다 O 표기법에서

http://bigocheatsheet.com/

Answer 1

. 예를 들어 log2 (n)과 log10 (n)은 상수로만 다르기 때문에 O 표기법에서 log (n) 만 표시됩니다.

Answer 2

Roman Cortes가 다른 답변에서 올바르게 표시했습니다. a과 b이 1보다 큰 정수인 경우 을 표시하기 쉽기 때문에 점근 적 복잡성에 대한 문제입니다.

그러나 처음에는 log의 출처를 고려하는 것이 여전히 유익하다고 생각합니다. 첫 번째 장소에서 이러한 종류의 경계를 유도하는 데 도움이되는 동기 부여 및 이해와 관련된 숫자가있을 것입니다.

이진 검색 트리는 값 검색을 빠르게하기 위해 구성됩니다. 모든 노드에는 최대 두 개의 하위 트리가 있으며, 여기에서 왼쪽 하위 트리의 모든 값은 상위 노드의 값보다 작고 오른쪽 하위 트리의 모든 값은 상위 노드의 값보다 큽니다. 평형 이진 검색 트리를 검색 할 때 (균형을 잡는 것이 중요합니다!) 대상 값을 검색 할 노드의 수를 효과적으로 반으로 줄이거 나 반으로 줄이면됩니다. 런타임 반복 관계 T(n) = T(n/2) + c을 사용하여이를 표현할 수 있습니다. 이 말한다 :

균형 이진 검색 트리에서 검색 작업의 실행은 왼쪽이나 오른쪽 중 하나를 검색 현재 노드의 값 ( c)을 더한 시간으로 대상을 비교로부터 일정한 기간에 의해 주어진다

서브 트리가 있지만 둘 다 결코 (T(n/2)). T(0) = a 일부 일정 a, 우리는 T의 몇 가지 값을 쓸 수 있도록 합리적으로 가정

:

n T(n) 
- ---- 
0 a 
1 T(1/2) + c = a + c 
2 T(2/2) + c = a + c + c = a + 2c 
4 T(4/2) + c = a + 2c + c = a + 3c 
8 T(8/2) + c = a + 3c + c = a + 4c 
... 
2^k T(2^k/2) + c = a + kc + c = a + (k+1)c 

k = log_2(n)을 보자. 그런 다음 T(n) =T(2^k) = a + (k+1)c = a + (1 + log_2(n))c이됩니다. 따라서 T(n) = O(log_2(n)) = O(log n). 대상의 하한은 현재 노드의 하한보다 작은 경우

1. 대상 왼쪽 하위 트리에 있습니다

   한다고 가정 우리는 값이 범위이며, 다음과 같은 규칙이 적용 균형의 삼중 트리를했다.

2. 대상의 상한이 현재 노드의 상한보다 큰 경우 대상이 오른쪽 하위 트리에 있습니다.
3. 대상은 중간 부분 트리에 있습니다.오히려 하나보다 두 조건을 확인하고 세 가지 하위 트리 중 하나보다는 하나를 선택 제외

     (10,20) 
         | 
       +----------+----------+ 
       |   |   | 
   (5,11) (11,15) (21,24) 
            | 
           (22,23) 
   

   검색 이진 검색과 같이 작동 할 수 있습니다 :

그래서,이 균형의 삼중 탐색 트리 수 있습니다 두 가지 가능성이있다. 되풀이 관계는 T(n) = T(n/3) + c'이되고 솔루션은 T(n) = a' + (1 + log_3(n))c' = O(log_3(n)) = O(log n)이됩니다.