Vedo dove la maggior parte delle letture online deriva dal fatto che la notazione Big-Oh di una ricerca binaria è O (log (n)), ma questo non presuppone un albero bilanciato? Cosa succede se l'albero è completamente sbilanciato (ad esempio simile a un elenco collegato). In questo caso l'altezza dell'albero non è log (n) è n.
Quindi considerando che Big-Oh prende in considerazione il caso peggiore, perché la ricerca binaria O (n) non è?
I see where most readings online derive that the Big-Oh notation of a Binary Search is O(log(n)), but doesn't this assume a balanced tree? What if the tree is completely unbalanced (i.e. similar to a linked list). In this case the height of the tree is not log(n) it is n.
Ricerca binaria non presuppone affatto un albero . La ricerca binaria presuppone una struttura dati che è
Un array, un vettore o un hash ordinato, per esempio.
Quello che probabilmente stai pensando è Ricerca in un albero di ricerca binario .
So considering that Big-Oh takes into account the worst case, why isn't the Binary Search O(n)?
Big-Oh non tiene conto di nulla.
Big-Oh descrive il tasso di crescita di una funzione confrontandola con il tasso di crescita di un'altra funzione. Cosa queste funzioni significano è totalmente irrilevante per Big-Oh. Potrebbe essere una funzione che descrive la complessità temporale del caso peggiore di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale di best-case di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale del caso medio di un algoritmo. Potrebbe essere una funzione che descrive la complessità temporale amortizzata nel caso peggiore di un algoritmo. Potrebbe essere una funzione che descrive la peggiore complessità step di un algoritmo. Potrebbe essere una funzione che descrive la peggiore complessità di spazio di un algoritmo. Potrebbe essere una funzione che descrive la quantità di umani nel mondo in funzione del tempo. Potrebbe essere una funzione che descrive la quantità di denaro che un film fa in relazione al suo costo di produzione. Potrebbe essere una funzione che descrive la quantità di denaro che un film fa in relazione alla dimensione del seno del protagonista femminile.
Big-Oh non importa. Big-Oh dice semplicemente: questa funzione cresce più velocemente di quell'altra funzione. (Questa è una semplificazione grossolana che uso solo per effetto!) Ecco fatto. Come interpreti la funzione dipende da te, non ha nulla a che fare con Big-Oh.
Sì, il presupposto è che si tratta di un albero binario bilanciato, o almeno di uno che è caricato a caso. Lo scenario elenco collegato è solo una configurazione di molti, e le probabilità di ottenerlo per caso sono estremamente piccole, a meno che non si ordinino prima i nodi, prima di inserirli nell'albero.
Le ricerche in un albero binario bilanciato sono O (log (n)) nel peggiore dei casi.
Leggi altre domande sui tag algorithms big-o order