Eficiência de Ordenação de Algoritmos

Question

Estou estudando para um amanhã entrevista muito importante e há uma coisa que eu tenho uma grande quantidade de problemas com:. Algoritmos de ordenação e eficiências Bigo

O número é importante saber? O melhor, pior, ou a eficiência média?

Answer 1

pior, seguida pela média. estar ciente do impacto do mundo real das chamadas "constantes escondido" também - por exemplo, o algoritmo quicksort clássico é O (n ^ 2), no pior caso, e O (n log n), em média, enquanto que mergesort é o (N log N), no pior caso, mas quick irá superar mergesort na prática.

Answer 2

Todos eles são importantes para saber, é claro. Você tem que entender os benefícios de um algoritmo de ordenação no caso médio pode se tornar um déficit terrível no pior dos casos, ou o pior caso não é tão ruim, mas o melhor caso não é tão bom, e só funciona bem em dados não classificados, etc.

Answer 3

Em suma.

Classificando eficiência algoritmo irá variar em dados de entrada e tarefa.

• triagem velocidade máxima, que pode ser arquivado é n * log (n)
• se os dados contém dados sub ordenadas, velocidade máxima pode ser melhor, então n * log (n)
• se os dados consiste de duplicatas, a triagem pode ser feita em tempo linear perto
• a maioria dos algoritmos de ordenação têm seus usos

A maioria das variantes de ordenação rápidas ter seu caso médio também n * log (n), mas o teu são geralmente mais rápido do que outros algoritmos não altamente otimizado. É mais rápido quando não é estável, mas variantes estáveis ??são apenas uma fração mais lento. Principal problema é pior caso. Melhor correção casual é introsort.

A maioria das variantes merge sort tem seu melhor caso, média e pior fixo para n * log (n). É estável e relativamente fácil de escalar. Mas precisa de uma árvore binária (ou sua emulação) com relação ao tamanho dos itens totais. Principal problema é a memória. Melhor correção casual é timsort.

algoritmos de ordenação variam também pelo tamanho de entrada. Eu posso fazer uma reclamação novato, que a entrada de dados tamanho ao longo 10T, não é páreo para merge sort variantes.

Answer 4

Eu recomendo que você não apenas memorizar esses factóides. Saiba por que eles são o que são. Se eu estava entrevistando você, eu teria certeza de fazer perguntas que mostram o meu você entende como analisar um algoritmo, não só pode cuspir de volta para fora algo que você viu em uma página ou em um livro. Além disso, um dia antes de uma entrevista não é o momento de estar fazendo isso estudando.

Desejo-lhe a melhor sorte !! Por favor, informe em um comentário como foi!

Answer 5

Estou mais com um conjunto de entrevistas na minha faculdade agora ...

Cada algoritmo tem seus benefícios, caso contrário ele não vai existir. Assim, o seu melhor para entender o que é tão bom com o algoritmo que você está estudando. Onde é que isso faz bem? Como é que pode ser melhorado?

Eu acho que você vai automaticamente precisa ler várias notações de eficiência quando você faz isso. Cuidado com o pior caso, e prestar atenção ao caso médio, melhores casos são raros.

Todo o melhor para sua entrevista.

Answer 6

Você também pode querer olhar para outros tipos de classificação que pode ser usado quando existem certas condições. Por exemplo, considere Radix tipo. http://en.wikipedia.org/wiki/Radix_sort