O (logn) è sempre un albero?

Question

Vediamo sempre le operazioni su un albero (ricerca binaria) ha il caso di esecuzione del caso più importante a causa dell'altezza dell'albero è logn. Mi chiedo se ci viene detto che un algoritmo ha tempo di esecuzione in funzione di Logn, ad esempio M + NLOGN, possiamo concludere che deve coinvolgere un albero (aumentato)?

EDIT: grazie ai tuoi commenti, ora mi rendo conto che Divide-Conquer e Binary Tree sono così simili/concettualmente. Non avevo mai stabilito una connessione tra i due. Ma penso a un caso in cui O (Log) non è un algo di divisione che coinvolge un albero che non ha proprietà di un albero BST/AVL/rosso-nero.

Questa è la struttura dei dati set disgiunta con operazioni di ricerca/sindacale, il cui tempo di esecuzione è O (n + mlogn), con n è il numero di elementi e il numero di operazioni di ricerca.

Per favore fatemi sapere se mi manca STH, ma non riesco a vedere come entra in gioco di Divide-Conquer. Vedo solo in questo caso (set di disgiunzione) che ha un albero senza proprietà BST e un tempo di esecuzione che è una funzione di Logn. Quindi la mia domanda è sul perché/perché no posso fare una generalizzazione da questo caso.

Answer 1

Quello che hai è esattamente all'indietro. O(lg N) generalmente significa una sorta di algoritmo di divisione e conquista e un modo comune di implementare Divide and Conquer è un albero binario. Mentre gli alberi binari sono un sottoinsieme sostanziale di tutti gli algoritmi di divisione e conquista, sono comunque un sottoinsieme.

In alcuni casi, è possibile trasformare altri algoritmi di divisione e conquista abbastanza direttamente in alberi binari (ad esempio commenti su un'altra risposta hanno già tentato di rivendicare una ricerca binaria è simile). Solo per un altro esempio ovvio, tuttavia, un albero a più vie (ad esempio un albero B, B+ Tree o B*), mentre chiaramente un albero è altrettanto chiaramente non un albero binario.

Ancora una volta, se vuoi abbastanza male, puoi allungare il punto che un albero a più vie può essere rappresentato come una specie di versione deformata di un albero binario. Se vuoi, probabilmente puoi allungare tutte le eccezioni al punto da dire che tutti sono (almeno qualcosa di simile) alberi binari. Almeno per me, tuttavia, tutto ciò che fa è rendere "Binary Tree" sinonimo di "Divide and Conquer". In altre parole, tutto ciò che realizzi è deformare il vocabolario e cancellare essenzialmente un termine distinto e utile.

Answer 2

No, puoi anche cercare binario un array ordinato (ad esempio). Ma non crederci la parola per questo http://en.wikipedia.org/wiki/binary_search_algorithm

Answer 3

Come bancone:

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

Il tempo di esecuzione è O (log (n)), ma nessun albero qui!

Answer 4

La risposta è no. La ricerca binaria di un array ordinato è O(log(n)).

Answer 5

Gli algoritmi che impiegano tempo logaritmico sono comunemente Trovato nelle operazioni sugli alberi binari.

Esempi di O (logn):

• Trovare un elemento in un array ordinato con una ricerca binaria o un albero di ricerca bilanciato.

• Cerca un valore in un array di input ordinato per bisezione.

Answer 6

Come O (log (n)) è solo un limite superiore anche tutti gli algoritmi O (1) come function (a, b) return a+b; soddisfare la condizione.

Ma devo essere d'accordo su tutti gli algoritmi Theta (log (n)) sembrano algoritmi degli alberi o almeno possono essere astratti su un albero.

Answer 7

Risposta breve:

Solo perché un algoritmo ha un registro (N) come parte della sua analisi non significa che sia coinvolto un albero. Ad esempio, quello che segue è un algoritmo molto semplice che è O(log(n)

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

Come puoi vedere, nessun albero è stato coinvolto. John, fornisce anche un buon esempio su come la ricerca binaria può essere effettuata su un array ordinato. Entrambi richiedono tempo O (log (n)) e ci sono altri esempi di codice che potrebbero essere creati o referenziati. Quindi non fare ipotesi basate sulla complessità del tempo asintotico, guarda il codice per sapere con certezza.

Altro sugli alberi:

Solo perché un algoritmo coinvolge "alberi" non implica O(logn) o. Devi conoscere il tipo di albero e come l'operazione influisce sull'albero.

Qualche esempio:

• Esempio 1)

Sarebbe inserire o cercare il seguente albero sbilanciato O(n).

• Esempio 2)

Inserire o cercare i seguenti alberi bilanciati sarebbero entrambi O(log(n)).

Albero binario equilibrato:

Albero equilibrato del grado 3:

Commenti aggiuntivi

Se gli alberi che stai usando non hanno un modo per "equilibrio" di quanto ci siano buone probabilità che le tue operazioni siano O(n) tempo no O(logn). Se si usano alberi che sono auto -bilancianti, gli inserti normalmente richiedono più tempo, poiché il bilanciamento degli alberi si verifica normalmente durante la fase di inserto.