>> Doug LLOYD: Entón, nós aprenden sobre CS50 unha variedade de clasificación e investigación
algoritmos.
E ás veces isto pode ser un pouco complicado para manter
ao tanto do que algoritmo fai o que.
Temos realmente só desnatado a superficie tamén,
hai moitos outros investigación e algoritmos de ordenación.
Polo tanto, neste vídeo, imos só levar uns minutos
para tratar e destilar cada algoritmo abaixo aos seus elementos centrais
para que poida lembrar o máis información importante sobre eles
e ser capaz de articular a diferenzas, se fose necesario.
>> A primeira é a selección de clasificación.
A idea básica por tras de selección tipo é atopar o menor elemento sen clasificar
nunha matriz e troca-lo co primeiro elemento non ordenado dese array.
Nós dixemos que o peor caso tempo de execución que se n ao cadrado.
E se queres lembrar por que razón, tomar un ollar para o vídeo selección de clasificación.
O tempo de execución do mellor caso é tamén n ao cadrado.
>> Bubble sort, a idea detrás diso un é cambiar os pares adxacentes.
Entón, esa é a clave que axuda Teña en conta que a diferenza aquí.
Selección tipo é, ata agora, atopar o bubble smallest--
Sort é cambiar os pares adxacentes.
Nós trocar pares adxacentes de elementos se
están fóra de orde, o que efectivamente Burbullas de elementos máis grandes para a dereita,
e, á vez que tamén comeza para mover elementos menores á esquerda.
O peor caso de tempo caso de execución de bubble sort é n ao cadrado.
O tempo de execución do mellor caso de bubble sort é n.
Porque nesa situación non actually--
que quizais non sexa necesario facer os swaps en todo.
Nós só ten que facer unha pasar por todos os elementos n.
>> Na ordenación por inserción, o idea básica aquí está cambiando.
Esa é a palabra clave para a inserción de clasificación.
Nós imos para a etapa a través dunha vez a matriz de esquerda a dereita.
E como nós facemos, nós somos cambiará elementos
vimos para dar lugar a os menores que necesitan un lugar para caber
de volta en que parte clasificada.
Entón, nós construímos a matriz clasificada unha elemento de cada vez, para a esquerda a dereita,
e cambiamos cousas que facer o cuarto.
O tempo de execución do peor caso de ordenación por inserción é n ao cadrado.
O mellor caso o tempo de execución é n.
>> Mesturar sort-- a palabra chave aquí é dividir e mesturar.
Podemos dividir o conxunto completo, se é seis elementos, oito elementos,
10.000 elements-- nós división lo abaixo á metade, á metade, á metade,
ata que teñamos baixo matriz n dun elemento de matrices.
Un conxunto de matrices n un elemento.
Entón comezamos cunha 1000-elemento da matriz,
e chegamos ao punto en que 1.000 matrices ten un único elemento.
Entón comezamos a mesturar estas sub matrices xuntos na orde correcta.
Entón, tomamos dúas matrices dun elemento e crear unha matriz de dous elementos.
Tomamos dúas matrices de dous elementos e crear unha matriz de catro elementos
e así por diante e así por diante ata que teñamos novamente reconstruída unha matriz elemento n.
>> O tempo de execución do peor caso de merge sort é n veces rexistro n.
Temos n elementos, pero este proceso de recombinación
colle no rexistro n pasos para obter de volta a un conxunto completo.
O mellor caso o tempo de execución tamén é log n N porque este proceso non realmente
importan a matriz foi clasificadas ou non para comezar.
O proceso é o mesmo, non hai ningunha forma de curtos circuítos cousas.
Entón n log n, no peor caso, n log n no mellor dos casos.
>> Falamos sobre dous busca algoritmos.
Así, busca linear é sobre iteración.
Continuar en toda a gama xa que, a partir de esquerda a dereita,
intentando atopar o número que estamos a procurar.
O tempo de peor caso executar é grande O n.
Pode levar a iteración a través de cada elemento
para atopar o elemento que estamos a buscar para, tanto na última posición,
ou non en todos.
Pero non podemos confirmar que ata nós miramos todo.
son o mellor caso, atopamos inmediatamente.
O tempo de execución do mellor caso busca linear é omega de 1.
>> Para rematar, non había investigación binaria, que require gama variada.
Lembre que é moi consideración importante
cando se traballa con pescuda binária.
É unha condición previa para utilizar ele-- a matriz que está a buscar a través
debe ser clasificado.
Se non, a palabra chave é dividir e conquistar.
Dividir a matriz en metade e eliminar a metade dos elementos
cada vez que a medida que avanzar a través.
Debido a iso dividir e conquistar e as cousas dividindo á metade visión,
o tempo de execución do peor caso de busca binaria é
log n, que é substancialmente mellor que de busca linear n.
O mellor caso o tempo de execución aínda é un.
>> Podemos atopalo inmediatamente a primeira vez que facemos unha división, pero,
de novo, lembre que aínda busca binaria é
substancialmente mellor que a investigación lineal en virtude de ser log n contra n,
pode ter que ir a través do traballo de clasificar a matriz primeiro, que
pode facelo menos eficaz en función sobre o tamaño da iteración clasificados.
>> Eu son Doug Lloyd, este é CS50.