Ottimalità di Binary Search

Question

Questa può essere una domanda stupida, ma qualcuno sa di una prova che la ricerca binaria è asintoticamente ottimale? Cioè, se ci viene data una lista ordinata di elementi in cui l'operazione solo consentito su quegli oggetti è un confronto, come si fa a dimostrare che la ricerca non può essere fatto in O (lg n)? (Questo è poco-o di lg n, tra l'altro). Nota che sto limitando questo per gli elementi in cui l'unica operazione consentita operazione è un confronto, dal momento che ci sono algoritmi ben noti che possono battere O (lg n) in aspettativa se si è permesso di fare operazioni più complesse sui dati (si veda, ad esempio, la ricerca per interpolazione).

Answer 1

qui :

• Il numero di possibili risultati dovrebbe essere almeno O (n).
• È possibile rappresentare le decisioni fatte dal algoritmo nodi di un "albero di decisione": se le voci confrontano maggiore allora va avanti così, se non si va nella direzione opposta. I nodi dell'albero sono gli stati dell'algoritmo e le foglie sono i risultati. Quindi non ci dovrebbero essere i nodi di almeno O (n) nella struttura.
• Ogni albero su O (n) i nodi ha almeno O (log N) i livelli.

Answer 2

La logica è semplice. Supponiamo che abbiamo matrice di n diversi elementi ordinati.

1. Ci sono 2 possibili esiti di 1 confronto (primo elemento è minore o maggiore). Così, se uno confronto è abbastanza, n <= 2. In caso contrario, se abbiamo 3 elementi (a, b, c) e il nostro algoritmo ha 2 possibili risultati, non sarà mai scelto uno dei 3 elementi.
2. Ci sono 4 possibili esiti di 2 confronti. Così, se 2 confronti è sufficiente, n <= 4.
3. Allo stesso modo, per i confronti k di essere abbastanza n dovrebbe essere n <= 2^k.

Invertire l'ultima disuguaglianza e avrai logaritmo:. k >= log(2, n)

Answer 3

Come descritto Nikita è impossibile avere qualcosa di sempre meglio di O (log n).

Anche se si è permesso di fare alcune operazioni aggiuntive, è ancora sufficiente -. Sono sicuro che è possibile preparare sequenza di elementi in cui la ricerca per interpolazione si esibirà peggio di ricerca binaria

Possiamo dire la ricerca per interpolazione è meglio solo perché:

1. Consideriamo performance media, non caso peggiore.
2. Probabilità di ogni possibile set di dati in entrata non è uniforme.

Quindi la risposta è -. Tutto dipende dalla conoscenza aggiuntiva che abbiamo su insiemi di dati in arrivo