Quindi, ecco la domanda:un altro algoritmo Job-intervista
Supponiamo di avere 100 mila numeri interi che varia da 1 a 1 milione. Si prega di ordinare i numeri interi. La complessità temporale dovrebbe essere O (n).
Chiunque condivida le proprie idee è molto apprezzato.
Suona come un tipo di conteggio diretto.
Lo spazio è costante. Il runtime è O (n).
Gotcha, grazie, sembra che questa domanda non sia così difficile. me stesso il tempo di esecuzione – Tracy
è costante, a meno che non si modifichi il domanda, che come ho scritto dovresti. Quindi Space è O (n), il runtime è O (n). Non puoi averlo in entrambe le direzioni. – piccolbo
Un'altra cosa da aggiungere a questa buona risposta.Per l'installazione 4, se si desidera avere un ordinamento stabile, è necessario eseguire il retrocondizionamento dell'array (ad esempio, in caso di parità, le stampe vengono stampate nell'ordine dell'array pre-ordinato). –
Utilizzare il numero di conteggio. Contateli tutti (O (n)), quindi create il riempimento dell'array dei risultati (O (n), di nuovo).
Il suggerimento dovrebbe essere che vanno da 1 a 1 milione.
Vedi pigeonhole sort
È necessario utilizzare algoritmi di ordinamento conosciuti con complessità O (n)
Poiché il problema è di dimensione fissa e comprende un insieme finito di casi, qualsiasi algoritmo di ordinamento terminerà in O (1). Dovresti dire al tester di tornare alla scuola di analisi algoritmica. Un possibile modo per generalizzare questo problema su un insieme infinito è: hai una matrice di dimensione n con numeri che vanno da [0, 10n]. Puoi ordinarlo in O (n)? Questo ha senso per me. Oppure puoi parametrizzare il problema con la dimensione dell'array e l'intervallo degli interi e ottenere un vincolo O (f (n, k)). Il problema è quando ricevi una domanda come questa in un'intervista, che cosa fai? Cerchi di indovinare ciò che l'intervistatore vorrebbe sentire o dici qualcosa come "fammi riformulare la tua domanda"? Oppure vai verso l'uscita con un grande sorriso?
Conteggio sort: http://en.wikipedia.org/wiki/Counting_sort –
@Paul R: L'articolo di Wikipedia afferma che questo è O (n + k), e solo efficiente se n> k. In questo caso n = 100.000 e k = 1.000.000. –
O ordinamento radix (1 milione è 20 bit, quindi 20 passa oltre 100.000 numeri interi in maiuscolo, l'ordinamento conteggio ingenuo richiede di azzerare il milione di contatori (utilizzando una tabella hash no, ma non si digitano i risultati in ordine , quindi è necessario ordinarlo, utilizzando una mappa ad albero non, ma inserendo il tempo non costante) e quindi scorrere su di essi per ottenere il risultato, che è anche dell'ordine di 2 milioni di operazioni; l'ordinamento di tipo binario radix può essere fatto in posizione quindi non richiede alcuna memoria aggiuntiva –