>> DOUG LLOYD: Então, nós aprendemos sobre CS50 uma variedade de classificação e pesquisa
algoritmos.
E às vezes isso pode ser um pouco complicado para manter
a par do que algoritmo faz o quê.
Nós temos realmente apenas desnatado a superfície também,
existem muitos outros pesquisa e algoritmos de ordenação.
Portanto, neste vídeo, vamos apenas levar alguns minutos
para tentar e destilar cada algoritmo para baixo a seus elementos centrais
para que você possa lembrar o mais informações importantes sobre eles
e ser capaz de articular a diferenças, se necessário.
>> O primeiro é a seleção de classificação.
A idéia básica por trás de seleção tipo é encontrar o menor elemento não triados
em uma matriz e trocá-lo com o primeiro elemento não ordenado desse array.
Nós dissemos que o pior caso tempo de execução do que foi n ao quadrado.
E se você quiser recordar por que razão, tomar um olhar para o vídeo selecção de classificação.
O tempo de execução do melhor caso é também n ao quadrado.
>> Bubble sort, a idéia por trás disso um é trocar os pares adjacentes.
Então, essa é a chave que ajuda você lembre-se a diferença aqui.
Seleção tipo é, até agora, encontrar o bubble smallest--
Sort é trocar os pares adjacentes.
Nós trocar pares adjacentes de elementos se
estão fora de ordem, o que efetivamente Bolhas de elementos maiores para a direita,
e, ao mesmo tempo que também começa para mover elementos menores para a esquerda.
O pior caso de tempo caso de execução de bubble sort é n ao quadrado.
O tempo de execução do melhor caso de bubble sort é n.
Porque nessa situação nós não actually--
que talvez não seja necessário fazer quaisquer swaps em tudo.
Nós só tem de fazer uma passar por todos os elementos n.
>> Na ordenação por inserção, o idéia básica aqui está mudando.
Essa é a palavra-chave para a inserção de classificação.
Nós vamos para a etapa através de uma vez a matriz da esquerda para a direita.
E como nós fazemos, nós somos vai mudar elementos
já vimos para dar lugar a os menores que necessitam de um lugar para caber
de volta em que parcela classificada.
Então, nós construímos a matriz classificada uma elemento de cada vez, para a esquerda para a direita,
e mudamos coisas para fazer o quarto.
O tempo de execução do pior caso de ordenação por inserção é n ao quadrado.
O melhor caso o tempo de execução é n.
>> Mesclar sort-- a palavra-chave aqui é dividir e mesclar.
Podemos dividir o conjunto completo, se é seis elementos, oito elementos,
10.000 elements-- nós dividi-lo para baixo pela metade, pela metade, pela metade,
até que tenhamos sob matriz n de um elemento de matrizes.
Um conjunto de matrizes n um elemento.
Então começamos com uma 1000-elemento da matriz,
e chegarmos ao ponto em que 1.000 matrizes tem um único elemento.
Então começamos a mesclar essas sub matrizes juntos novamente na ordem correta.
Então, tomamos duas matrizes de um elemento e criar uma matriz de dois elementos.
Tomamos duas matrizes de dois elementos e criar uma matriz de quatro elementos
e assim por diante e assim por diante até que tenhamos novamente reconstruída uma matriz elemento n.
>> O tempo de execução do pior caso de merge sort é n vezes log n.
Temos n elementos, mas este processo de recombinação
pega no registo n passos para obter de volta para um conjunto completo.
O melhor caso o tempo de execução também é log n N porque este processo não realmente
importam se a matriz foi classificadas ou não para começar.
O processo é o mesmo, não há nenhuma maneira de curtos circuitos coisas.
Então n log n, no pior caso, n log n na melhor das hipóteses.
>> Falamos sobre dois busca algoritmos.
Assim, busca linear é sobre iteração.
Prosseguimos em toda a gama uma vez que, a partir da esquerda para a direita,
tentando encontrar o número que estamos procurando.
O tempo de pior caso executar é grande O de n.
Ele pode nos levar a iteração através de cada elemento
para encontrar o elemento que estamos procurando para, quer na última posição,
ou não em todos.
Mas não podemos confirmar que até nós olhamos tudo.
sou o melhor caso, encontramos imediatamente.
O tempo de execução do melhor caso de busca linear é omega de 1.
>> Por último, não havia pesquisa binária, que requer gama variada.
Lembre-se que é muito consideração importante
quando se trabalha com pesquisa binária.
É um pré-requisito para utilizar ele-- a matriz que você está procurando através
deve ser classificado.
Caso contrário, a palavra-chave é dividir e conquistar.
Dividir a matriz em metade e eliminar metade dos elementos
cada vez que à medida que avançar através.
Devido a isso dividir e conquistar e as coisas dividindo pela metade abordagem,
o tempo de execução do pior caso de busca binária é
log n, que é substancialmente melhor do que de busca linear n.
O melhor caso o tempo de execução ainda é um.
>> Podemos encontrá-lo imediatamente a primeira vez que fazemos uma divisão, mas,
novamente, lembre-se que embora busca binária é
substancialmente melhor do que a pesquisa linear em virtude de ser log n contra n,
você pode ter que ir através do trabalho de classificar a matriz primeiro, que
pode torná-lo menos eficaz, dependendo sobre o tamanho da iteração classificados.
>> Eu sou Doug Lloyd, este é CS50.