O (logn)은 항상 트리입니까?

Question

우리는 트리 높이가 logn이기 때문에 항상 (이진 검색) 트리에서 연산이 O (logn) 최악의 경우 실행 시간이 있음을 확인합니다. 알고리즘에 logn의 함수로 실행 시간이 있다고 들었는지, 예를 들어 m + nlogn과 같이 (증가 된) 트리를 포함해야한다고 결론을 내릴 수 있습니까?

편집 : 의견을 보내 주시면 divide-conquer와 binary tree가 시각적/개념적으로 매우 유사하다는 것을 알게되었습니다. 나는 둘 사이를 연결 한 적이 없었다. 그러나 O (logn)가 BST/AVL/적 검은 색 나무의 특성이없는 나무를 포함하는 분할 정복 알고리즘이 아닌 경우를 생각합니다.

N은 요소 수, M은 찾기 연산 수와 함께 실행 시간이 O (N + MlogN) 인 찾기/결합 연산이있는 분리 된 데이터 구조입니다.

내가 sth가 없으면 알려주세요.하지만 어떻게 분할 정복이 여기에 나타나는지 알 수 없습니다. 이 BST 속성이없는 트리가 있고 실행 시간이 logN의 함수 인 트리가 있음을 볼 수 있습니다. 그래서 제 질문은 왜/왜 제가이 사건에서 일반화 할 수 있는지에 관한 것입니다.

Answer 1

보유하고있는 것은 거꾸로입니다. O(lg N)은 일반적으로 일종의 나누기 및 정복 알고리즘을 의미하며 나누기 및 정복을 구현하는 일반적인 방법 중 하나는 이진 트리입니다. 이진 트리는 모든 분할 및 정복 알고리즘의 상당 부분 집합이지만 어쨌든이 부분 집합입니다.

경우에 따라 다른 나누기 및 정복 알고리즘을 이진 트리로 직접 변환 할 수 있습니다 (예 : 다른 답변의 댓글은 이미 이진 검색이 유사하다고 주장하는 등의 시도를 이미 한 것입니다). 그러나 또 다른 명백한 예를 들면, 명확하게 나무가 명확하게 이 아니고 이진 트리 인 동시에 다원 트리 (예 : B- 트리, B + 트리 또는 B * 트리)가 있습니다.

다시 한번 말하지만, 충분히 나쁘다면 다중 경로 트리가 변형 된 이진 트리 버전으로 표시 될 수 있다는 점을 늘릴 수 있습니다. 원할 경우 모든 예외가 (적어도 뭔가 비슷한) 이진 트리라고 말하는 지점까지 모든 예외를 확장 할 수 있습니다. 그러나 저에게 적어도, "분열과 정복"과 동의어로 "이진 트리"를 만드는 것이 전부입니다. 즉, 당신이 성취 한 모든 것은 어휘를 왜곡하고 본질적으로 뚜렷하고 유용한 용어를 제거하는 것입니다.

Answer 2

아니요, 정렬 된 배열 (예 :)을 이진 검색 할 수도 있습니다. 그러나 카운터 예를 들어 그것을 http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

내 말을하지 않습니다

given array 'a' with length 'n' 
y = 0 
for x = 0 to log(length(a)) 
    y = y + 1 
return y 

실행 시간 (N 로그()) O, 그러나 여기에서 어떤 나무입니다!

Answer 4

로그 시간을 취하는 알고리즘은 일반적으로 이고 이진 트리 작업에서 발견되는입니다. O (logn)의

예 :

• 이진 검색 또는 균형 탐색 트리와 정렬 된 배열에서 항목을 찾기.

• 2 진수로 정렬 된 입력 배열에서 값을 찾습니다.

Answer 5

답은 no입니다. 정렬 된 배열의 이진 검색은 O(log(n))입니다.

Answer 6

O (log (n))는 상한선이므로 function (a, b) return a+b;과 같은 모든 O (1) 알고리즘도 조건을 충족시킵니다.

그러나 모든 Theta (log (n)) 알고리즘은 트리 알고리즘과 비슷하거나 적어도 트리로 추상화 될 수 있습니다.

Answer 7

짧은 답변 : 알고리즘은 분석의 일환으로 로그 (N)가

해서 나무가 관여하는 것을 의미하지 않는다. 예를 들어, 다음은 당신이 볼 수 있듯이, 어떤 나무는 포함되지 않았다 O(log(n)

for(int i = 1; i < n; i = i * 2) 
    print "hello"; 

입니다 매우 간단한 알고리즘이다. John은 또한 정렬 된 배열에서 이진 검색을 수행하는 방법에 대한 좋은 예를 제공합니다. 이 두 가지 모두 O (log (n)) 시간을 소요하며 생성하거나 참조 할 수있는 다른 코드 예제가 있습니다. 점근선의 시간 복잡성을 기반으로 가정을 세우지 말고, 알고있는 코드를 살펴보십시오. 나무에

더 : 알고리즘은 "나무"를 포함

해서 하나 O(logn)을 의미하지는 않습니다. 트리 유형과 조작이 트리에 미치는 영향을 알아야합니다.

몇 가지 예 :

• 예 1)

삽입하거나 다음 불균형 트리 검색은 O(n) 될 것이다.

• 예 2)

삽입 또는 검색 다음과 같은 균형 잡힌 나무 것 모두 O(log(n))에 의해.

균형 이진 트리 : 등급 3의

균형 트리 :

추가 댓글

당신이하지 않아도 사용하는 나무의 경우 좋은 것보다 "균형을 잡는"방법 귀하의 작업은 O(n) 시간이 아니며 O(logn)이 아닐 가능성이 있습니다. 자체 균형을 유지하는 트리를 사용하면 일반적으로 삽입 단계에서 나무의 균형이 맞춰지기 때문에 삽입 시간이 더 오래 걸립니다.