O (logn) é sempre uma árvore?

Question

Sempre vemos as operações em uma árvore (Binária Pesquisa) O (logn), o pior dos casos, devido à altura da árvore. Gostaria de saber se nos dizem que um algoritmo tem tempo de execução em função do logn, por exemplo, m + nLogn, podemos concluir que ele deve envolver uma árvore (aumentada)?

EDIT: Graças aos seus comentários, agora percebo que a árvore de conversação e binária é tão semelhante visual/conceitualmente. Eu nunca tinha feito uma conexão entre os dois. Mas penso em um caso em que o (logn) não é um algo de conquista de divisão que envolve uma árvore que não tem propriedade de uma árvore BST/AVL/Red-Black.

Essa é a estrutura de dados do Definir Disjunt com operações de Find/Union, cujo tempo de execução é O (n + mLogn), sendo n o número de elementos e o número de operações de localização.

Informe-me se estou perdendo o STH, mas não consigo ver como o Divide-Conquer entra em jogo aqui. Acabei de ver neste caso (Discarint Set) que ele possui uma árvore sem propriedade BST e um tempo de execução é uma função do logn. Portanto, minha pergunta é sobre por que/por que não posso fazer uma generalização a partir deste caso.

Answer 1

O que você tem é exatamente para trás. O(lg N) Geralmente significa algum tipo de algoritmo de dividir e conquistar, e uma maneira comum de implementar a divisão e a conquista é uma árvore binária. Enquanto as árvores binárias são um subconjunto substancial de todos os algoritmos de divisão e conquista, são um subconjunto de qualquer maneira.

Em alguns casos, você pode transformar outros algoritmos de divisão e conquista diretamente em árvores binárias (por exemplo, comentários em outra resposta já fizeram uma tentativa de reivindicar uma pesquisa binária é semelhante). Apenas para outro exemplo óbvio, no entanto, uma árvore de várias via (por exemplo, uma árvore B, B+ ou B* árvore), enquanto claramente uma árvore é tão claramente não uma árvore binária.

Novamente, se você quiser muito o suficiente, pode aumentar o ponto em que uma árvore multi -via pode ser representada como uma espécie de versão distorcida de uma árvore binária. Se você quiser, provavelmente pode esticar todas as exceções a ponto de dizer que todas elas são (pelo menos algo como) árvores binárias. Pelo menos para mim, no entanto, tudo o que faz é fazer "árvore binária" sinônimo de "dividir e conquistar". Em outras palavras, tudo o que você realiza é deformar o vocabulário e essencialmente obliterar um termo que é distinto e útil.

Answer 2

Não, você também pode pesquisar binárias uma matriz classificada (por exemplo). Mas não aceite minha palavra para isso http://en.wikipedia.org/wiki/binary_search_algorithm

Answer 3

Como um contra -exemplo:

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

O tempo de execução é O (log (n)), mas nenhuma árvore aqui!

Answer 4

A resposta é não. A pesquisa binária de uma matriz classificada é O(log(n)).

Answer 5

Algoritmos que tomam tempo logarítmico são comumente encontrado em operações em árvores binárias.

Exemplos de O (logn):

• Encontrar um item em uma matriz classificada com uma pesquisa binária ou uma árvore de pesquisa equilibrada.

• Procure um valor em uma matriz de entrada classificada por bissecção.

Answer 6

Como O (log (n)) é apenas um limite superior também todos os algoritmos O (1) function (a, b) return a+b; satisfazer a condição.

Mas eu tenho que concordar com todos os algoritmos teta (log (n)) meio que parecem algoritmos de árvore ou pelo menos podem ser abstraídos em uma árvore.

Answer 7

Resposta curta:

Só porque um algoritmo possui log (n) como parte de sua análise não significa que uma árvore esteja envolvida. Por exemplo, a seguir é um algoritmo muito simples que é O(log(n)

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

Como você pode ver, nenhuma árvore estava envolvida. John, também fornece um bom exemplo de como a pesquisa binária pode ser feita em uma matriz classificada. Eles levam o tempo O (log (n)) e existem outros exemplos de código que podem ser criados ou referenciados. Portanto, não faça suposições com base na complexidade do tempo assintótico, observe o código para saber com certeza.

Mais em árvores:

Só porque um algoritmo envolve "árvores" não implica O(logn) qualquer. Você precisa conhecer o tipo de árvore e como a operação afeta a árvore.

Alguns exemplos:

• Exemplo 1)

Inserir ou pesquisar a seguinte árvore desequilibrada seria O(n).

• Exemplo 2)

Inserir ou pesquisar as seguintes árvores equilibradas por ambos O(log(n)).

Árvore binária equilibrada:

Árvore equilibrada do grau 3:

Comentários adicionais

Se as árvores que você está usando não têm uma maneira de "equilibrar", há uma boa chance de que suas operações sejam O(n) tempo não O(logn). Se você usa árvores que são auto -equilíbrio, as inserções normalmente levam mais tempo, pois o equilíbrio das árvores normalmente ocorre durante a fase de inserção.