-
O pior caso do shell sort é O(n log n) e não O(1) como o ML escreveu acima.
-
Para o caso médio, temos que a complexidade do Radix Sort é dada por Q((b/r)(n+2r)), onde n é a quantidade de números, b é a quantidade de dígitos e r é um inteiro positivo qualquer, tal que r <= b.
-
Cabe anulação nesta questão. Os únicos algorítmos que possuem complexidade de O(n log n) em todos os casos são Heapsort e MergeSort.
QUICKSORT:
• Melhor caso: O(N log N)
• Caso Médio: O(N log N)
• Pior caso: O(N^2) – ARQUIVO JÁ CLASSIFICADO
HEAPSORT:
• Melhor caso: O(N log N)
• Caso Médio: O(N log N)
• Pior caso: O(N log N)
SHELLSORT (Refinamento do Insertionsort)
• Melhor caso: O(N)
• Caso Médio: Depende da sequência do GAP.
• Pior caso: O(N log^2 N)
-
O Radixsort é um método de ordenação por contagem que é executado em tempo linear O(n).
-
O radix sort LSD opera na notação Big O, em O(nk), onde "n" é o número de chaves, e "k" é o comprimento médio da chave. É possível garantir esse desempenho para chaves com comprimento variável agrupando todas as chaves que tem o mesmo comprimento e ordenando separadamente cada grupo de chaves, do mais curto para o mais comprido, de modo a evitar o processamento de uma lista inteira de chaves em cada passo da ordenação.
Em muitas aplicações em que é necessário velocidade, o radix sort melhora as ordenações por comparação, como heapsort e o mergesort, que necessitam de Ω(n · log n) comparações, onde "n" é o número de itens a serem ordenados. Em compensação, algoritmos de ordenação baseados em comparações oferecem flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica. No entanto, essa habilidade é de pouca importância em várias aplicações práticas.
-
Acho que essa questão cabe anular sim.
Olha o estudo detalhado de como é calculado a complexidade dos algoritmos.
http://www.decom.ufop.br/menotti/aedI082/tps/tp3-sol1.pdf
-
Curiosidade: RadixSort é o método de ordenação usado pelos Correios para ordenar as cartas por CEP.
-
Não tem nada de anulação nessa questão!
Complexidade = Inserção O(n
2
); | Seleção O(n
2
); | Shellsort O(n log n); | Quicksort O(n log n); | Heapsort O(n log n). Apesar de não se conhecer analiticamente o
comportamento do Shellsort, ele é
considerado um método eficiente).
radixsort
O algoritmo de ordenação radix foi originalmente usado para ordenar cartões perfurados.
-
LETRA D
Só lembrar que o RADIX SORT é o diferentão da galera. Ele apresenta K(Tamanho da String) e S(Tamanho do Alfabeto)
Complexidade de Tempo: O(nk)
Complexidade de espaço: O(n + s)
-
d-
o radix sort é usadso para ordenar algortimos identificados por um chave unica, sendo cada chave é um string ou um nome consoante a ordem lexicografica.
https://www.bigocheatsheet.com/