1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> DOUG LLOYD: Así que en CS50 aprendimos acerca una variedad de clasificación y búsqueda 3 00:00:08,900 --> 00:00:09,442 algoritmos. 4 00:00:09,442 --> 00:00:11,400 Y a veces puede ser un poco difícil de mantener 5 00:00:11,400 --> 00:00:14,161 la pista de lo algoritmo hace qué. 6 00:00:14,161 --> 00:00:15,910 Tenemos realmente sólo rozado la superficie también, 7 00:00:15,910 --> 00:00:18,740 hay muchas otras búsqueda y algoritmos de ordenación. 8 00:00:18,740 --> 00:00:21,780 Así que en este video vamos a simplemente tomar un par de minutos 9 00:00:21,780 --> 00:00:24,980 para tratar de destilar cada algoritmo hasta en sus elementos básicos 10 00:00:24,980 --> 00:00:27,810 para que pueda recordar más información importante acerca de ellos 11 00:00:27,810 --> 00:00:31,970 y ser capaz de articular el diferencias, si es necesario. 12 00:00:31,970 --> 00:00:34,220 >> La primera es la ordenación por selección. 13 00:00:34,220 --> 00:00:38,210 La idea básica de ordenación por selección se encuentra el elemento más pequeño sin clasificar 14 00:00:38,210 --> 00:00:42,890 en una matriz y cambiar con el primer elemento sin clasificar de esa matriz. 15 00:00:42,890 --> 00:00:46,620 Hemos dicho que el peor de los casos tiempo de ejecución de que se n al cuadrado. 16 00:00:46,620 --> 00:00:50,060 Y si quieres recordar por qué, toma un vistazo al vídeo ordenación por selección. 17 00:00:50,060 --> 00:00:54,560 El tiempo de ejecución mejor de los casos También está n al cuadrado. 18 00:00:54,560 --> 00:00:58,910 >> Burbuja especie, la idea detrás de esa uno es para intercambiar pares adyacentes. 19 00:00:58,910 --> 00:01:01,730 Así que esa es la clave que le ayuda recordar la diferencia aquí. 20 00:01:01,730 --> 00:01:04,920 Selección especie, es decir, hasta el momento, encontrar la burbuja smallest-- 21 00:01:04,920 --> 00:01:06,790 es un género intercambiar pares adyacentes. 22 00:01:06,790 --> 00:01:08,710 Intercambiamos pares adyacentes de elementos si 23 00:01:08,710 --> 00:01:12,530 están fuera de servicio, lo que efectivamente burbujas elementos más grandes a la derecha, 24 00:01:12,530 --> 00:01:17,060 y, al mismo tiempo, también comienza para mover elementos más pequeños a la izquierda. 25 00:01:17,060 --> 00:01:20,180 El peor de los casos el tiempo de ejecución caso de ordenamiento de burbuja está n al cuadrado. 26 00:01:20,180 --> 00:01:23,476 El tiempo de ejecución mejor de los casos de ordenamiento de burbuja es n. 27 00:01:23,476 --> 00:01:25,350 Porque en esa situación no actually-- 28 00:01:25,350 --> 00:01:27,141 puede ser que no tenga que hacer los canjes en absoluto. 29 00:01:27,141 --> 00:01:31,026 Sólo tenemos que hacer uno pasar a través de todos los elementos n. 30 00:01:31,026 --> 00:01:34,600 >> En la ordenación por inserción, la idea básica que aquí se está desplazando. 31 00:01:34,600 --> 00:01:36,630 Esa es la palabra clave para la ordenación por inserción. 32 00:01:36,630 --> 00:01:39,630 Vamos a entrar una vez a través la matriz de izquierda a derecha. 33 00:01:39,630 --> 00:01:41,670 Y mientras lo hacemos, estamos va a cambiar los elementos 34 00:01:41,670 --> 00:01:46,260 ya hemos visto para hacer espacio para más pequeños que necesitan para encajar en alguna parte 35 00:01:46,260 --> 00:01:48,080 de vuelta en esa porción ordenados. 36 00:01:48,080 --> 00:01:51,600 Así construimos la matriz ordenada de un elemento a la vez, de izquierda a derecha, 37 00:01:51,600 --> 00:01:54,740 y cambiamos las cosas para hacer espacio. 38 00:01:54,740 --> 00:01:58,650 El tiempo de ejecución del peor caso de ordenación por inserción está n al cuadrado. 39 00:01:58,650 --> 00:02:02,380 El tiempo mejor de los casos de gestión es n. 40 00:02:02,380 --> 00:02:05,380 >> Combinar sort-- la palabra clave aquí es dividir y combinar. 41 00:02:05,380 --> 00:02:08,949 Dividimos la gama, ya sea es seis elementos, ocho elementos, 42 00:02:08,949 --> 00:02:13,790 10000 elements-- lo dividimos por medio, por medio, por medio, 43 00:02:13,790 --> 00:02:17,720 hasta que tengamos bajo array de n conjuntos de elementos de uno. 44 00:02:17,720 --> 00:02:19,470 Un conjunto de n uno conjuntos de elementos. 45 00:02:19,470 --> 00:02:22,640 Así que empezamos con un solo 1000-elemento de la matriz, 46 00:02:22,640 --> 00:02:26,550 y llegamos al punto en el que tiene 1.000 matrices de un elemento. 47 00:02:26,550 --> 00:02:30,990 Entonces empezamos a combinar esas matrices sub de nuevo juntos en el orden correcto. 48 00:02:30,990 --> 00:02:34,860 Así que tomamos dos conjuntos de un solo elemento y crear un array de dos elementos. 49 00:02:34,860 --> 00:02:38,180 Tomamos dos matrices de dos elementos y crear una matriz de cuatro elementos 50 00:02:38,180 --> 00:02:43,900 y así sucesivamente y así sucesivamente hasta que hayamos nuevamente reconstruido una matriz n elemento. 51 00:02:43,900 --> 00:02:48,410 >> El tiempo de ejecución del peor caso de fusionan especie es n veces log n. 52 00:02:48,410 --> 00:02:52,390 Tenemos n elementos, pero este proceso recombinación 53 00:02:52,390 --> 00:02:56,960 toma log n pasos para llegar copia de un arsenal completo. 54 00:02:56,960 --> 00:03:01,160 El mejor de los casos el tiempo de ejecución es también n log n porque este proceso en realidad no 55 00:03:01,160 --> 00:03:04,090 importa si la matriz era ordenados o no, para empezar. 56 00:03:04,090 --> 00:03:07,590 El proceso es el mismo, no hay no hay manera de cosas de cortocircuito. 57 00:03:07,590 --> 00:03:11,610 Así n log n en el peor de los casos, n log n en el mejor de los casos. 58 00:03:11,610 --> 00:03:13,960 >> Hablamos de dos buscar algoritmos. 59 00:03:13,960 --> 00:03:16,230 Así que la búsqueda lineal es sobre la iteración. 60 00:03:16,230 --> 00:03:19,500 Procedemos a través de la matriz una vez, de izquierda a derecha, 61 00:03:19,500 --> 00:03:21,950 tratando de encontrar el número que estamos buscando. 62 00:03:21,950 --> 00:03:24,550 El tiempo en el peor caso es ejecutar gran O de n. 63 00:03:24,550 --> 00:03:27,610 Nos podría tomar la iteración a través de cada elemento 64 00:03:27,610 --> 00:03:30,660 para encontrar el elemento que estamos buscando para, ya sea en la última posición, 65 00:03:30,660 --> 00:03:31,630 o nada en absoluto. 66 00:03:31,630 --> 00:03:34,720 Pero no podemos confirmar que hasta hemos visto todo. 67 00:03:34,720 --> 00:03:36,730 soy el mejor de los casos, nos encontramos de inmediato. 68 00:03:36,730 --> 00:03:41,060 El tiempo de ejecución mejor de los casos de búsqueda lineal es el omega de 1. 69 00:03:41,060 --> 00:03:43,689 >> Por último, hubo de búsqueda binaria, que requiere gama variada. 70 00:03:43,689 --> 00:03:45,605 Recuerde que es una muy consideración importante 71 00:03:45,605 --> 00:03:47,155 cuando se trabaja con búsqueda binaria. 72 00:03:47,155 --> 00:03:50,180 Es un requisito previo para el uso de it-- la matriz que está mirando a través de 73 00:03:50,180 --> 00:03:52,160 deben ser ordenados. 74 00:03:52,160 --> 00:03:54,500 De lo contrario, la palabra clave es divide y vencerás. 75 00:03:54,500 --> 00:03:58,310 Dividir la matriz en la mitad y eliminar la mitad de los elementos 76 00:03:58,310 --> 00:04:00,780 cada vez que a medida que avance a través. 77 00:04:00,780 --> 00:04:04,330 Debido a esto divide y vencerás y las cosas de división en medio enfoque, 78 00:04:04,330 --> 00:04:07,450 el tiempo de ejecución del peor caso de búsqueda binaria es 79 00:04:07,450 --> 00:04:11,730 log n, que es sustancialmente mejor que la búsqueda lineal n. 80 00:04:11,730 --> 00:04:13,570 El tiempo mejor de los casos de gestión sigue siendo uno. 81 00:04:13,570 --> 00:04:17,010 >> Podríamos encontrar inmediatamente el primera vez que hacemos una división, pero, 82 00:04:17,010 --> 00:04:19,339 de nuevo, recordar que aunque la búsqueda binaria es 83 00:04:19,339 --> 00:04:24,030 sustancialmente mejor que la búsqueda lineal en virtud de ser log n frente a n, 84 00:04:24,030 --> 00:04:27,110 es posible que tenga que pasar por el trabajo de ordenar la matriz primera, que 85 00:04:27,110 --> 00:04:32,010 podría hacer que sea menos eficaz dependiendo en el tamaño de la iteración ordenados. 86 00:04:32,010 --> 00:04:35,250 >> Soy Doug Lloyd, esto es CS50. 87 00:04:35,250 --> 00:04:36,757