5.13. Resumen¶
Una búsqueda secuencial es \(O(n)\) para listas ordenadas y no ordenadas.
Una búsqueda binaria en una lista ordenada es \(O(\log n)\) en el peor de los casos.
Las tablas hash pueden proporcionar una búsqueda de tiempo constante.
Un ordenamiento burbuja, un ordenamiento por selección y un ordenamiento por inserción son algoritmos \(O(n^{2})\).
Un ordenamiento de Shell mejora con respecto al ordenamiento por inserción mediante el ordenamiento de sublistas incrementales. Se encuentra entre \(O(n)\) y \(O(n^{2})\).
Un ordenamiento por mezcla es \(O(n \log n)\), pero requiere espacio adicional para el proceso de mezcla.
Un ordenamiento rápido es \(O(n \log n)\), pero puede degradarse a \(O(n^{2})\) si los puntos de división no están cerca de la mitad de la lista. Este ordenamiento no requiere espacio adicional.