Sommario¶

• Una ricerca sequenziale prende \(O(n)\) tempo per liste ordinate o non ordinate.
• Una ricerca binaria di una lista ordinata prende \(O(\log n)\) tempo nel caso peggiore.
• Le tabelle Hash forniscono tempo di ricerca costante.
• Il bubble sort, il selection sort e l’insertion sort prendono \(O(n^{2})\) tempo.
• Lo shell sort migliora l’insertion sort ordinando incrementalmente le sottoliste. Ci mette tra \(O(n)\) e \(O(n^{2})\) tempo.
• Il merge sort prende \(O(n \log n)\) tempo, ma richiede spazio addizionale per il processo di fusione.
• Il quick sort prende \(O(n \log n)\) tempo, ma può degradare in \(O(n^{2})\). Non richiede spazio addizionale.