Analisi degli algoritmi - Trova numero intero mancante nella matrice ordinata meglio di O (n)

Question

Sto lavorando per l'analisi della classe degli algoritmi per la prima volta e mi chiedevo se qualcuno potesse fornire assistenza nell'esempio seguente. Credo di averlo risolto per una complessità O (n), ma mi chiedevo se c'è una versione migliore che non sto pensando a O (logn)?

Siano A = A [1] = < ... < = A [n + 1] tramite un array ordinato di interi n distinte, in cui ogni intero è nell'intervallo [1 ... n + 1]. Cioè, manca esattamente un numero intero di {1, ..., n + 1} da A. Descrivi un algoritmo di efficeint per trovare il numero intero mancante. Analizza la complessità del caso peggiore (numero di accessi all'array A) del tuo algoritmo.

La soluzione che ho è relativamente semplice, e credo che nel peggiore dei casi sia N la complessità. Forse sto pensando troppo all'esempio, ma c'è una soluzione migliore?

mia soluzione

for(i = 1; i < n +1; i++) : 
    if(A[i-1] > i) : 
     return i 

La logica dietro questa è quanto è ordinato, il primo elemento deve essere 1, il secondo deve essere 2, e così via e così via, finché l'elemento nella matrice è più grande dell'elemento che si suppone essere, indicando che un elemento è stato perso, restituisce l'elemento che dovrebbe essere e ne abbiamo uno mancante.

Questa logica è corretta? C'è un modo migliore per farlo?

Grazie per la lettura e grazie in anticipo per l'assistenza.

Answer 1

Questa logica è sicuramente corretta, ma non è abbastanza veloce da battere O (n) perché si controlla ogni elemento.

È possibile farlo più velocemente osservando che se A[i]==i, quindi tutti gli elementi a j < i sono al loro posto corretto. Questa osservazione dovrebbe essere sufficiente per la costruzione di un approccio divide et impera che viene eseguito in O (log n):

• Controllare l'elemento in mezzo
• Se è nel posto sbagliato, andare a sinistra
• in caso contrario, andare a destra

Più formalmente, siete alla ricerca di un posto dove A[i]==i e A[i+1]==i+2. Si inizia con l'intervallo all'estremità dell'array. Ogni sonda al centro dell'intervallo riduce il doppio intervallo rimanente. Ad un certo punto ti rimane un intervallo di soli due elementi. L'elemento a sinistra è l'ultimo elemento "corretto", mentre l'elemento a destra è il primo elemento dopo il numero mancante.

Answer 2

È possibile eseguire una ricerca binaria per il primo indice i con A [i]> i. Se il numero intero mancante è k, allora A [i] = i per i < k e A [i] = i + 1 per i> = k.

Answer 3

A volte il trucco è pensare al problema in un modo diverso.

In spirito, si sta semplicemente lavorando con una serie di valori booleani; la voce nell'indice n è la verità di a[n] > n.

Inoltre, questo array inizia con zero o più false consecutivi e le voci rimanenti sono tutte true.

Il tuo problema, ora, è trovare l'indice della prima istanza di true nella matrice (ordinata) di valori booleani.