Tenho uma dúvida, pela aula havia entendido que o insertion sort era O(n²), mas na tabela na atividade 5 está como O(n). Qual é o Big O do insertion sort?
Tenho uma dúvida, pela aula havia entendido que o insertion sort era O(n²), mas na tabela na atividade 5 está como O(n). Qual é o Big O do insertion sort?
hoje, com a Alura e o Google Gemini
Olá Wagner! Tudo bem?
Peço desculpa pela demora para responder o seu tópico.
O insertion sort é um algoritmo de ordenação que possui complexidade O(n²) no pior caso. Porém, no melhor caso, quando o vetor já está ordenado, a complexidade é O(n).
Na tabela da atividade 5, foi provavelmente considerado o melhor caso para o insertion sort. Mas é importante lembrar que, na prática, é difícil que um vetor já esteja completamente ordenado antes de ser ordenado novamente.
Espero ter ajudado a esclarecer sua dúvida.
Bons estudos!