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.