TEORETICO LOGING LEGGE DI PORTARE Numero di occorrenze di un intero obiettivo in un array ordinato

Question

.

Data una serie ordinata di numeri interi e un numero intero di destinazione, trova il numero di occorrenze dell'Integer target.

È noto che una ricerca binaria ha la complessità del tempo $ o (\ lg n) $ dove $ n$ è la dimensione dell'array. Ad esempio, dato un array $ [1,2,3,4,4,5] $ e un bersaglio $ 3,$ L'algoritmo dovrebbe restituire $ 2 $ Poiché ci sono due copie di $ 3 $ nell'array.

.

Domanda: Esiste un algoritmo più rapido che ha la complessità del tempo inferiore a $ o (\ lg n)? $ altrimenti, c'è una prova per dimostrare che $ \ omega (\ lg n) $ è il limite inferiore teorico?

Answer 1

Il problema richiede $ \ omega (\ log n) $ accede alla memoria anche se si è promesso che il numero intero di destinazione appaia al massimo. Puoi dimostrarlo usando un argomento avversario.

Dì che il bersaglio è zero. Se il primo accesso all'array è rimasto del centro, risposta $ - 1 $ , e impostare mentalmente gli elementi a sinistra per essere $ - 2, -3, \ Ldots $ . Se il primo accesso è a destra del centro, rispondere a $ + 1 $ , e imposta mentalmente gli elementi a destra per essere $ 2 , 3, \ Ldots $ .

Supponiamo che il primo accesso sia stato a destra del centro, dire posizione $ i $ e considera il secondo accesso. Se è a destra del primo accesso, sai già cosa rispondere. Altrimenti, ci sono due casi. Se la posizione accessibile $ j $ è inferiore a $ i / 2 $ , risposta $ - 1 $ (e riempire elementi a sinistra). Se fosse più di $ i / 2 $ , risposta $ + 1/2 $ (e compilare elementi a destra fino alla posizione $ i $ ).

Continuare in questo modo, ad ogni passaggio il numero di posizioni che potrebbero contenere l'elemento di destinazione è al massimo dimezzato in ogni fase. Infine, quando solo un elemento è ancora in gioco, senza interrogarla, l'algoritmo non può sapere per certo se l'array contiene l'elemento di destinazione o meno. Ci vuole $ \ log_2 n $ passaggi per raggiungere questo passaggio.

Quanto sopra mostrano che la ricerca binaria è ottimale per la ricerca di un array ordinato.

Answer 2

Ci sono $ N $ Risposte possibili.Ogni confronto ti dà al massimo un bit di informazioni.Hai bisogno di almeno $ \ lg n $ bit di informazioni per descrivere la risposta, quindi è necessario almeno $ \LG N $ Confronti.