Quali sono alcuni motivi per cui potresti scegliere un algoritmo di runtime peggiore? E quali sono alcuni vantaggi di una lista collegata rispetto a una tabella hash / array in cui l'accesso è un tempo costante.
What are some reasons you may choose a worse runtime algorithm?
Di gran lunga la ragione più comune è che l'algoritmo "peggio" è molto più semplice, o è la prima soluzione a cui penso, e ottenere prestazioni matematicamente ottimali non ha importanza nella parte del codice che sto attualmente lavorandoci. Quale è la maggior parte delle parti del codice.
Un altro motivo comune è che, in generale, gli algoritmi teoricamente più veloci spesso richiedono di formulare ipotesi più incisive sull'input. L'ordinamento di Radix è molto più veloce di quicksort / mergesort / heapsort / etc, ma funziona solo se si presuppongono valori minimi e massimi per i numeri di input. Non voglio hardcode mins e maxs arbitrari nel mio programma senza una molto buona ragione, dal momento che questo è esattamente il genere di cosa che rende i programmi fragili e imprevedibili nel lungo periodo. Quindi la maggior parte delle volte non userò l'ordinamento digitale a meno che i requisiti aziendali non mi diano un minimo e un massimo gratis.
And what are some advantages of a linked list vs a hash table/array where access is constant time?
Il più grande vantaggio di un elenco collegato su un array o una tabella hash è che l'inserimento o la rimozione di un elemento in qualsiasi punto dell'elenco è un'operazione a tempo costante, anche nel caso peggiore non ammortizzato (purché tu abbia già un riferimento al nodo che si desidera inserire / rimuovere in). Per gli array, l'inserimento e la rimozione sono operazioni di tempo lineare. Per le tabelle hash, l'inserimento e la rimozione sono tempi di ammortamento costanti, ma tempo lineare in generale.
In alcuni casi, anche gli elenchi collegati (e gli alberi) sono utili perché i puntatori ai loro nodi non vengono invalidati in caso di inserimenti futuri. Diventano non validi solo quando quel particolare nodo viene cancellato. Con matrici e tabelle hash, troppi inserimenti forzeranno una riallocazione totale che invalida tutti i puntatori agli elementi esistenti. In molte lingue questo è un non-problema completo, ma in qualcosa come C o C ++ può essere a volte molto importante.
Leggi altre domande sui tag design programming-practices data-structures algorithms complexity