Trovare i 2 numeri più alti - informatica

Question

Sto cercando di capire un algoritmo per trovare i 2 numeri più alti in un elenco di numeri.

Il numero più alto si trova negli stadi n-1, forse facendo il primo passo di una sorta di bolla o qualcosa del genere. A me sembra che trovare anche il prossimo numero più alto si possa trovare in media un confronto di 1,5 n.

Il mio professore ci ha fatto fare i compiti per scrivere un alogritm che trova i 2 numeri più alti nei confronti di n + log (n). È possibile? Qualche idea, suggerimento?

Modifica: quando dico n + log (n) non mi riferisco a O (n + log n), ma piuttosto esattamente n + log n

Answer 1

Sì, è possibile farlo in non più di (n + log n). Non posso davvero dirti come senza dare via la risposta, ma lasciami provare. :-)

Prendi i n numeri, confrontali in coppie alla volta. Prendi il ceil (n / 2) "vincitori", e ripeti, "come un albero binario". Domande: quanti confronti sono necessari per trovare il più grande? Quante persone fa questo "vincitore" vincere contro? A chi potrebbe aver perso il secondo più grande? Quindi quanti confronti ci vogliono ora per trovare il secondo numero più grande?

La risposta risulta essere un totale di n-1 + limiti (log n) - 1 confronti, in cui il registro deve basarsi 2. Puoi anche provare usando un argomento contraddittorio che non è possibile fare meglio di così nel peggiore dei casi.

Answer 2

Modifica: Ops, ho perso una cosa semplice a causa della stupidità. Questa soluzione non è corretta, anche se la tengo qui perché è ancora avg (n + log (n)). Grazie a ShreevatsaR per aver sottolineato la mia stupidità. Ho preso in considerazione la ricerca dell'albero, ma ho completamente perso l'idea di tornare indietro per trovare il secondo numero più alto nel registro (n).

Comunque, qui segue la mia prova del perché l'algoritmo inferiore non è altro che avg (n + log (n)). Nella vita reale dovrebbe comunque funzionare abbastanza bene.

• Primo confronto con il secondo numero più alto registrato.
• Solo se il confronto ha esito positivo, confronta con il numero più alto registrato.

Per dimostrare che è in media n + log n, dobbiamo semplicemente dimostrare che il primo confronto ha successo solo in media log (n) volte. E questo è abbastanza semplice da vedere o dimostrare.

1. Supponi che P sia la posizione effettiva dell'attuale secondo numero più grande in una versione ordinata dell'elenco ed esegui l'algoritmo
2. Se P > 2, quando viene trovato un numero maggiore, la nuova P sarà in media non più di P / 2.
3. Se P = 2, il primo confronto non può avere esito positivo, poiché non esiste un numero maggiore del secondo numero più grande corrente.
4. P può al massimo uguale a N
5. Da 2, 3 e 4 dovrebbe essere banale vedere che il primo confronto non può avere successo più dei log (N) volte in media.

Answer 3

Che ne dici di questo:

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Answer 4

La risposta inviata da ShreevatsaR sembra essere O (n log n).

Il primo passaggio (n operazioni) produce n / 2 risposte. Ripetendo, immagino che intendi fare n / 2 operazioni per produrre n / 4 risposte. Eseguirai il registro del ciclo n volte. È molto simile a un ordinamento di tipo merge tranne per il fatto che il tipo di merge elabora sempre n nodi ogni volta. Esegue anche il registro del ciclo n volte. E non vedo come questo algoritmo terrà traccia del secondo numero più alto.

nickf ha la risposta giusta. il caso peggiore è quando l'elenco è ordinato, farà 2n confronti - cioè O (n).

tra l'altro, O (n + log n) è O (n) la notazione dell'Ordine si riferisce alla crescita asintotica nel caso peggiore.

Answer 5

È possibile utilizzare l'ordinamento conteggio, l'ordinamento radix, l'ordinamento bucket o altri algoritmi di tempo lineare per ordinare prima l'elenco in ordine decrescente. Quindi basta ottenere i primi 2 elementi dell'elenco ordinato. Quindi ci vorrà (n) + 2 = (n)

Nota che questi algoritmi possono essere ordinati in tempo lineare perché ognuno ha i suoi presupposti.

Answer 6

Pseudocodice (non è essenzialmente n?)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}