Algoritmi e strutture dati: Perché un computer più veloce non salva un cattivo algoritmo
Come il modo di organizzare i dati decide che cosa è veloce: O-grande, tabelle hash, alberi, heap, ordinamento, grafi, programmazione dinamica e scelte greedy.
Prova 3 domande
1. Un algoritmo O(n²) passa a un computer 1.000 volte più veloce. Nello stesso tempo, quanto più grande può essere l'input?
- Circa 100 volte più grande
- Circa 1.000 volte più grande
- Circa 32 volte più grande
Mostra la risposta
Risposta: Circa 32 volte più grande
Il tempo cresce con n al quadrato, quindi un'accelerazione di 1.000 volte consente solo la radice quadrata di 1.000, circa 32 volte più dati.
2. Raddoppiare la dimensione dell'input di un algoritmo O(n log n) che effetto ha all'incirca sul tempo di esecuzione?
- Lo raddoppia esattamente, non di più
- Lo quadruplica all'incirca
- Lo raddoppia e poco più
Mostra la risposta
Risposta: Lo raddoppia e poco più
n raddoppia e log n cresce di un solo passo, quindi il tempo sale di poco più del doppio, molto meno della crescita quadratica.
3. Che cosa ignora deliberatamente la notazione O-grande?
- I fattori costanti e i termini minori
- Come cresce il tempo con l'input
- Come si comporta l'algoritmo nel caso peggiore
Mostra la risposta
Risposta: I fattori costanti e i termini minori
L'O-grande descrive il ritmo di crescita per input grandi, quindi 3n² + 100n e n² sono entrambi O(n²).
Il quiz completo arriva prima delle tue app
BrainTok ti fa qualche domanda come queste prima di aprire le app che scegli, e il tempo davanti allo schermo diventa apprendimento. Per iPhone.
Unisciti alla beta