Supponiamo di avere una matrice ordinata di elementi unici, A[n] . Sto cercando di trovare il limite inferiore per trovare un elemento specifico x nella matrice. Sospetto che il limite inferiore sia log_2(n+1) .
Ho provato ad usare un albero decisionale per risolvere questo problema, e in effetti sappiamo tra 2 elementi che è maggiore, che dà 2 per la base del logaritmo, ma perché tutti i possibili casi n+1 ?
L'algoritmo a cui stai pensando è Ricerca binaria .
Ha un limite inferiore di O(1) , che si presenta nel suo migliore dei casi: il primo elemento selezionato è l'elemento desiderato x . Non è richiesta alcuna ulteriore ricerca.
Ha un limite superiore di O(log_2(n)) . Ogni volta che scegli un elemento e decidi se vuoi che la tua prossima ricerca si muova più in alto o più in basso, stai eliminando metà dello spazio di ricerca. Poiché ogni passo dimezza lo spazio di ricerca, la domanda diventa "quante volte posso dividere la dimensione dello spazio di ricerca in 2, finché non raggiungo un singolo elemento"? Questa domanda di dimezzamento ripetuto è l'opposto del raddoppio ripetuto (esponenziazione) e viene risolta con un logaritmo.
Leggi altre domande sui tag array algorithms sorting