5.13. Sumário¶
A busca sequencial é \(O(n)\) para listas ordenadas ou não.
A busca binária de uma lista ordenada é \(O(\log n)\) no pior caso.
Tabelas de dispersão podem fornecer busca em tempo constante.
O bubble sort, a ordenação por seleção e a ordenação por inserção são algoritmos de ordem \(O(n^{2})\).
O shell sort melhora a ordenação por inserção ao ordenar sublistas de maneira incremental. A complexidade fica entre \(O(n)\) and \(O(n^{2})\).
O merge sort é \(O(n \log n)\), mas requer espaço adicional para o processo de intercalamento.
O quick sort é \(O(n \log n)\), mas pode decair para \(O(n^{2})\) se os pivôs não estiverem próximos do meio da lista. Ele não requer espaço adicional.