Palestrante: Todo ben, esta é CS50. Isto é o fin de semana de tres, e, se non teña aproveitado xa, sei que haberá xantar este venres, como de costume, onde pode gozar dunha boa conversa e alimentos en Fire and Ice con algúns dos CS50 de funcionarios e compañeiros. Enfrontamento esta URL aquí. Agora podes lembrar, ou pode en breve estar familiarizado con, estas cousas aquí, que se dan ao final do semestre para moitas clases. O chamado exame de libros azuis, en que escribir as súas respostas para os exames. Agora eu teño aquí 26, tales libros azuis, en cada un deles está escrito un nome, de A a Z. E en realidade, os nomes son tan sinxelo, A a Z. E unha das os obxectivos en man hoxe será para seguir o que comezamos o luns, que non é tanto mirar o código, pero realmente mirando para ideas e resolución de problemas. Un dos obxectivos e promesas deste curso é ensinalo a pensar máis coidado, máis metodicamente, e para resolver os problemas de forma máis eficiente. E, de feito, podemos facer o que realmente sen sequera tocar unha liña de código. Entón, eu teño un par de elefantes aquí hoxe, laranxa e azul, se puidésemos obter un voluntario, quizais de máis atrás do que o habitual. Que tal alí mesmo, imos alí abaixo. O obxectivo do que será a axudar máis administrar este exame aquí. Cal é o seu nome? Audiencia: Mary Beth. Palestrante: Mary Beth, imos cara arriba. Déixeme incorporarse o micrófono aquí para vostede. Pracer en coñece-lo. Audiencia: Pracer en coñece-lo. Palestrante: Todo ben, entón eu teño aquí libros azul da a Z, e eu vou finxir que Eu teño un dos alumnos, e eles están benvida nun tanto aleatoriamente ao final dun bloque de exame tres horas, entón eles están acabando nalgúns orde semi-aleatoria así. Agora o seu traballo en só un momento que vai para ser-- este é realmente como se entregados ao final a clase, o máis probable. O seu traballo agora vai ser, moi simplemente, para clasificar estes libros azuis para nós de A a Z. Audiencia: Oh, iso é vai levar para sempre. Orador: E imos ver como fai iso, sen presión. Audiencia: Non, ningunha presión nin nada. Orador: E para divertirse, imos poñer un temporizador. Audiencia: moi divertido, moi divertido. Palestrante: podo soster o micrófono para ti. Todo ben, nós só dobrou a nosa velocidade. Entón, nese medio tempo, deixe-me poñer o que hai de será a pregunta de Mary Beth é o que se está facendo, como está vai sobre como solucionar isto? E, de feito, non pode ter Xa penso en algo tan sinxelo como cando escolle ata 26 libros como este, que ten un talento natural ordenando a eles. Cal é o proceso que realmente utiliza? É moi aleatorio só escoller o primeiro que ve e poñelas no seu lugar? Vostede primeiro mover as súas mans en torno Buscando un logo mirando B? Vostede dar un ollo a un par deles mosaico e só dicir, agarde un minuto, isto Non é certo, e, a continuación, cambiar a orde? Xa vimos o luns que hai unha serie de formas no que podemos facelo, e en realidade, como estamos preto do final aquí, Eu tomaría nota posible que Mary Beth está facendo. Temos algunhas pilas parecer, un maior, tres menores. Audiencia: Estou ordenándolles cando eu atopar dúas cartas que sei que están xuntos nunha secuencia, Eu poñer-los xuntos para que eu non ten que preocuparse en manter o control de unha liña enteira de libros. É só, oh, A é o primeiro, Eu teño esa pila aquí. Palestrante: Entón, case como de pezas de puzzle que ten a forma correcta para combinar-se un co outro. Audiencia: Moi bonito, si. Palestrante: OK, excelente. E agora cada un destes pilas é presuntamente ordenado? Audiencia: Yeah. Palestrante: Todo ben, de A a Z. Todos seguro, parabéns, fixo iso. Ten a súa elección. Azul? Todo ben, grazas por iso. Entón Mary Beth propúxose que a súa visión era, pero o que é outra visión como pode ir sobre como clasificar esas cousas? O que tería feito? A maior cantidade de bater sería un minuto e 50 segundos ou menos, máis os que eu esquezo de contar. O que tería feito? Si? Audiencia: Tome a pila. Comezar desde o principio. Comprobe os seus papeis. E se o de arriba é maior do que, quizais, son, o fondo é superior, a continuación, desactiva-los. Palestrante: OK, así que comezar na parte superior e na parte inferior, e, a continuación, traballar o seu camiño dentro dese xeito, cambiando-os? OK, entón un pouco semellante en espírito de bubble sort, pero escoller os extremos non os pares adxacentes. Pero o curto que é que hai certamente unha morea de formas diferentes poderíamos facelo, e francamente, creo que tipo de adoptou algunhas enfoques, non? Vostede fixo unha especie de catro pilas ordenadas, e entón efectivamente fundiuse los xuntos. E iso é, atrévome a dicir, outra técnica completamente. Non tratalo como unha gran pila, vostede divide o problema en catro quadriláteros, se o desexa, e despois de algunha maneira fundiuse los ao final. Entón, imos considerar, en definitiva, De que outra forma poderiamos facelo. Nós formalizou a noción de bubble sort última vez, e recordo bubble sort foi un algoritmo que visualizamos con oito dos seus compañeiros aquí enriba, aparentemente aleatoria clasificados en primeiro lugar. E nós, entón, decidiu pares, se dous elementos están fóra de orde, simplemente trocalos. Entón, catro e dous son obviamente, fóra de orde, entón eses dous compañeiros cambiar de posición. E, entón, repetido con catro e seis, logo, seis e oito, en cada iteración, movendo á dereita. Así, dado oito persoas, cantos pares comparacións que fixen durante a camiñada de esquerda a dereita nun tal iteración? Cantas comparacións? Sete, non? Porque se hai oito persoas, pero ten o par eles e continúa movéndose un salto cara á dereita, non vai ter oito comparacións, porque non pode comparar un elemento contra si, é que sería basta ser inútil, así que ten sete. Ou, máis xeralmente, se temos n persoas, nós facer N menos 1 comparacións con bubble sort. Entón, imos considerar agora como bo ou malo bubble sort realmente era, e intentar darnos vocabulario con que a algoritmos crítica como esta, e logo a nosa. Entón, o primeiro paso a través bubble sort, por primeira vez Eu andei a partir de esquerda a dereita na escenario, me n menos 1 comparacións tomou. E iso vai ser o meu unidade de medida, non? Eu era unha especie de falar e camiñar, un tanto rapidamente, un tanto lento, así contando meu número de segundos non é particularmente revelador, pero a conta do número de operacións que fixen o luns, comparando dúas persoas, que se sente como unha agradable unidade de medida. Entón n menos 1 pasos por primeira vez, Pero entón o que pasou despois diso? Cal é a única cabeza dunha soa vez a través dunha lista de outra forma non ordenada? Que me pode dicir sobre o elemento que foi todo o camiño ata alí? Si? Ese foi o maior elemento, non? O número oito, aínda que ela comezou aquí, cada vez que eu comparar a contra un veciño, ela mantivo burbullas-se para a dereita lado da lista. E, de feito, que é onde o algoritmo recibe o seu nome. Agora por esa lóxica, cantas comparacións eu vou facer o segundo tempo Fago que pase de esquerda a dereita? n menos 2, non? Sería só perdendo meu tempo se eu manter comparando oito contra alguén máis porque xa sabemos ela estaba no lugar seguro. Entón, iso é un pouco de un optimización, de xeito que o seguinte paso será máis n menos dúas etapas, onde n é o número de persoas. Agora podes tipo de extrapolar, mesmo se non é un científico da computación, como iso termina. Ao final deste algoritmo, presuntamente ten só unha comparación esquerda. Ten que tipo de resolver o inicio da lista, no caso de dous e un está fóra de orde e debe ser un e dous, de xeito que este encoste na ademais dunha comparación final. Agora, o punto, punto, punto tipo de ondas é mans en algúns dos detalles máis suculentas, pero imos só ir adiante e simplificar. Se se lembrar de alta escola, francamente, moitos de vostedes tiñan libros de matemáticas que tiñan unha folla de fraude pouco na portada ou a tapa traseira que mostre somatórios que series como Esta última análise, sumou. No caso xeral, se ten un variable como n, e de feito este, Se mirou para a súa libro de matemáticas vella escola, vería que iso realmente engádese a esta suma aquí, n veces n menos 1 todo dividido por 2. Entón, por agora, déixeme só estipular iso é verdade, entón nun acto de fe, iso é o que isto resume ata, e puidemos probar que, nun caso máis xeral. Pero agora imos ampliar iso. Entón, imos multiplicar tanto, o que se n ao cadrado, menos n, todo dividido por 2. Isto é realmente n ao cadrado, dividido por 2, menos n máis de 2, de xeito que é todo bo e interesante. Pero o que acontece se nós agora plugin un valor? Supoña que eu non tiña oito persoas, pero din que un millón. E un millón só porque que é un número moi grande, imos chamar iso e ver o que acontece. Entón, se eu chamar un millón para que a fórmula Eu estou indo a obter un millón de cadrado, dividido por 2, menos unha millóns, dividido por dous. Agora, o que é que isto vai ser igual? Así, 500 millóns, menos 500.000. E se eu realmente facer que a matemática, isto significa que que a clasificación dun millón persoas co tipo de burbulla me pode levar 499999500000 etapas ou comparacións, ao final, nós só estamos extrapolando. Que se sente moi lento, pero francamente medición dunha entrada especial así, non é tan revelador. Pero en realidade, ela suxire que como n convértese en maior e máis grande, este algoritmo tipo de sente peor e peor, é que realmente comezar a sentir a dor do que exponenciação, que n ao cadrado, que engade-se moi rápido. E este detalle non é perdido nas persoas, en realidade, hai uns anos, un certo senador que foi campaña, sentou-se a unha entrevista con Eric de Google Schmidt, CEO na época, e foi desafiado cunha pregunta así como nós estamos explorando actualmente. Imos dar un ollo. [REPRODUCIÓN] Senador, está aquí en Google, e eu gusto pensar na presidencia como unha entrevista de emprego. Agora, é difícil conseguir un traballo como presidente, e está pasando os rigores agora. Tamén é difícil conseguir un emprego en Google. Temos preguntas, e nós nosas preguntas candidatos, e este é de Larry Schwimmer. O que-- vostedes pensan que eu son broma, é aquí mesmo. Cal é o xeito máis eficiente de clasificar un millón de enteiros de 32 bits? -Well-- Estou moi, maybe-- Non, non, non. Eu creo que o bubble sort sería o camiño mal. Imos, que lle dixo iso? Eu non vin ordenador ciencia no seu fondo. -Temos Nosos espías dentro. -OK, Imos pedir un diferente pregunta da entrevista. [FIN REPRODUCIÓN DE VIDEO] Palestrante: Entón, falando números específicos, aínda que Non vai ser tan útil. Non é unha lección de vida que burbulla tipo, dado un millón de entradas, pode levar ata 500 millóns etapas. Realmente non pode xeneralizar moi eficaz sempre que e tomar boas decisións de deseño ao escribir programas. Entón, imos concentrar en como aínda podemos simplificar este resultado. Entón, eu teño resaltado en amarelo aquí o resultado n cadrado dividido por dous, así un millón cadrado dividido por dous, e despois Eu destacou que a resposta final foi xa que fóra subtraído n dividido por 2. E a alegación de que eu vou facer agora é, quen diaños lle importa se restar off un pouco máis de idade n 2 cando o primeiro parte desta fórmula é moi grande? El domina o outro prazo, n cadrado dividido por dous é moito maior, de xeito claro, como n se fai grande como un millóns, que hai realmente unha gran diferenza no Ao final do día entre 500 mil millóns e 499.999.500.000? Non é realmente. E entón o que imos facer o que os científicos da computación é ignorar estes termos de orde máis baixa e ter algo coma isto e realmente só para simplificar a termo que vai importar. Os maiores nosos conxuntos de datos comeza, o máis grande nosas bases de datos comeza, máis páxinas web temos que buscar, o máis amigos ten en Facebook. Como n queda maior, estamos moi vai se preocupar coa maior prazo en calquera análise de noso rendemento algoritmos. E eu vou dicir, xa sabe o que, bubble sort é da orde de O grande, na orde de n ao cadrado. Non é exactamente n cadrado, como vimos, pero quen realmente lle importa sobre estes termos menores, e, a verdade, que realmente importa se dividimos por 2? Isto é só un factor constante. E é de 500 millóns contra 250 millóns que realmente de un gran negocio? Podería só esperar un ano, deixar meu portátil literalmente obter dúas veces máis rápido en hardware, e este tipo de diferenza só desaparece naturalmente ao longo do tempo. O que nos interesa é a expresión, a peza da expresión que vai variar como a nosa entrada queda maior e máis grande. E, de feito, no mundo real, iso é o que está pasando cada vez máis é as entradas para os nosos problemas e algoritmos están quedando maiores. Entón, ó gran será a notación, a notación asintótica, que acabamos de usar como científicos da computación para describir o rendemento, ou o tempo de funcionamento, dun algoritmo. Para que poidamos comparar algoritmos en computadores diferentes escritos por persoas diferentes, utilizando algunha métrica fundamentalmente semellantes como o número de comparacións que se facendo, ou que o número de swaps está facendo. O que nós non imos conta é a cantidade de tempo que pasa no reloxo tipicamente na parede. O que nós non imos preocuparnos é a cantidade de memoria está a usar hoxe en menos importante, aínda que iso sexa outro recurso que pode medir. Nós imos tratar basear as nosas análises en só as operacións básicas, aquelas, francamente, que se pode ver máis visualmente. Así, con algo como gran O de n cadrado, eu afirmo que o de n ao cadrado é un límite superior sobre o chamado tempo de funcionamento do bubble sort. Noutras palabras, se quería dicir que hai este límite de cantos os pasos dun algoritmo pode levar, vai estar na gran O de n cadrado, neste caso, un límite superior. E se eu non cambiar o historia a non ser sobre bubble sort, pero sobre o límite superior. Pode pensar en un algoritmo que nós miramos xa cuxo límite superior, máximo medida de tempo ou de operacións, sería dicir ser limitado por n, dunha función lineal, non un cuadrática que é curvo? ¿Que é un algoritmo que sempre leva máis do que como n pasos, ou 2n pasos ou etapas 3N? Si? Audiencia: Buscar o maior número nunha lista? Palestrante: Perfecto, atopando o maior número nunha lista. Se eu estou con unha lista de persoas, por exemplo, cada un que está sostendo un número, o que é o número máximo de pasos que debe tomar de min, unha persoa bastante intelixente, para atopar o maior persoa nesa lista? n, non? Porque, no peor caso, en que quizais o maior valor que? Certo, todo o camiño ao final. Así, no peor caso límite superior, eu podería ten que ir todo o camiño ata aquí e ser como, oh, aquí está o número oito, ou o que quere que o valor é. Agora sería simplemente estúpido se eu continúe indo, non? Á procura de máis e máis elementos se o último deles é alí? Así, por suposto, n é un límite superior. Eu non teño de tomar máis etapas do que iso. Entón, o que se no canto propuxen que existen algoritmos neste mundo que ter un tempo de execución que se delimitada pola gran O de rexistro n, log n? Onde xa vimos isto antes? Si? Audiencia: O problema de lista telefónica? Palestrante: Como o problema axenda. Cal foi a medida de quão moito tempo ou cantas bágoas de TI me levou para atopar alguén como Mike Smith na lista telefónica? Nós alegou que era log n, e aínda que descoñecido ou que é algo nebuloso o que é un logaritmo ou expoñente foi, lembre que log n xeralmente refírese ao proceso, neste caso, a división algo en metade, e de novo, e de novo, e de novo, de tal modo que fica cada vez máis pequeno, como fai iso. Entón rexistro de n refírese, con certeza, a exemplo do libro de teléfono, a procura binaria, en teoría, cando tivo as portas virtuais no consello, ou cando se Sean buscando por algo. Se usase a procura binaria, rexistro n sería o límite superior da cantidade de tempo que leva. Pero os algoritmos que decorreu en log n asumiu o detalle chave? Que a lista resolveuse, non? O seu algoritmo está mal se súa entrada non se clasifica, e aínda así está a usar algo así como procura binaria porque pode ir dereito sobre o elemento sen entender que é de feito alí. Agora, o que iso pode significar, ó grande dun? Isto non quere dicir que o seu algoritmo toma unha e só unha etapa, significa só que é preciso unha número constante de pasos. Quizais sexa un, é posible que 10, é posible que 1000, pero é independente do o tamaño do problema. Non importa o grande é n, un algoritmo de tempo constante fai sempre o mesmo número de pasos. Entón, o que pode ser un algoritmo falamos ou só intuitivamente que vén a vostede que sempre é executado na chamada constante de tempo? Si? Audiencia: Engadir dous números. Palestrante: Engadir dous números, 2 máis 2 é igual a 4, feito. Para que poida funcionar, o que máis? Que tal mundo máis real, non? Audiencia: Buscar o primeiro nunha lista. Palestrante: Atopando-se o primeiro elemento nunha lista, con certeza. Fomos realmente falando sobre matrices xa, como facelo no primeiro elemento dunha matriz, non importa canto tempo a matriz está código C? Acaba de usar como o soporte notación cero, Bam, está alí. E, de feito matrices, como un aparte, soporte algo xeralmente coñecido como de acceso aleatorio, de acceso aleatorio memoria, porque pode literalmente ir a calquera só lugar. Podemos facelo aínda máis simple podemos retroceder a semana de cero cando fixemos cero. Canto tempo tardou para o dicir bloque en risco a realizar? Só tempo constante, non? Diga algo, dicir algo, non importa como grandes arañazos mundo é, sempre é terá a mesma cantidade de tempo simplemente dicir algo. Entón é tempo constante, pero o que é a outra cara? Se isto fose superior límites, o que se quere para describir os límites inferiores dos nosos algoritmos de tempo de execución? Case un mellor caso potencialmente, se quixeren, aínda que eses termos podería aplicarse a mellor casos peores casos, casos de media máis xeralmente, pero imos centrar en límites inferiores de forma máis xeral. ¿Que é un algoritmo que ten un límite inferior de n pasos, ou 2n pasos ou etapas 3N? Algúns factor de n pasos, Cal é o límite inferior. Si? Audiencia: Bubble sort? Palestrante: Bubble sort leva vostede minimamente n pasos, por que? Por que? Por que que comezan a chegar ata ti intuitivamente, mesmo se isto acontecer non só aínda? Si? Audiencia: [inaudível]. Palestrante: Exactamente. No mellor escenario posible de bubble sort, e unha morea de algoritmos, se eu entregar-lle oito persoas que xa son clasificadas, sería insensato para ti, o algoritmo, para ir e volver máis dunha vez, non? Porque así que camiñar a través da lista de novo, ten que entender, oh, eu non fixen ningún swaps, esta lista é ordenada, saia. Pero iso vai levar vostede n pasos. E, inversamente, o que é outra forma de pensar sobre iso? Bubble sort é un omega, por así dicir, de n, porque se ollar para menos de n elementos, o que é a cuestión fundamental non? Non sabe se está resolto, certo. Nós os humanos poidan mirar oito persoas e ser como, oh, é clasificado, que non me n pasos tomar, pero fixo. Os seus ollos, aínda que tipo de ter un gran campo de visión, mirou para oito elementos, mirou para oito persoas, iso é oito pasos de forma eficaz. E só se eu andase polo todo lista que eu entendo, si, clasificada. Se eu deixar no medio do camiño a pensar: todo dereito, é ben resolto, ata agora, cales son as posibilidades que non é ordenado? Iso non os dun algoritmo será correcta. Pode ser máis rápido, pero incorrecto. Entón, agora temos unha forma de describindo un límite inferior, E canto tempo constante? ¿Que é un algoritmo que ten unha menor grazas no seu tempo de execución de un? 1 paso, dous pasos, 10 pasos, pero constante, independente de n, o tamaño da entrada? Si, na parte de atrás. Audiencia: printf? Palestrante: ¿Que é iso? Audiencia: printf? COLUMNA: printf. OK, con certeza. Entón, é preciso un número fixo de pasos. E eu debería agora-- agora que estamos a falar de código C e non rabuñar, algo como din, con printf, debemos comezar a ter coidado. Porque printf leva entrada, é unha cadea, e as cordas que tecnicamente ten lonxitude. Entón, se nós agora quere escoller en ti, se non lle importa, tecnicamente poderiamos argumentar que printf toma unha entrada de lonxitude variable, e, por suposto, isto pode levar máis tempo para imprimir unha secuencia de tanto tempo, que este tempo. Entón, o que se consideramos só o clasificación e investigación exemplos? E sobre Mike Smith no teléfono libro, ou busca binaria máis xeral? No mellor dos casos, o que pode ocorrer? Abro o libro de teléfono e, Bam, hai número de Mike Smith. Podo chamalo de inmediato. Deu un paso, quizais dúas etapas, pero un número constante de etapas se eu teño sorte. E, francamente, nós vimos en Luns seu compañeiro de clase estar moi sorte dúas veces seguidas. E iso era realmente constante vez en límites inferiores no algoritmo en cuestión para atopar o número 50 atrás daqueles pechado portas. Agora, como un aparte, se descubrir Que tanto grande, o límite superior e omega, o límite inferior, son un na mesma, que é a mesma fórmula en parénteses, tamén se pode dicir, só que ser extravagante, que algo está theta de n ou teta dalgún outro valor. Isto significa só que cando gran O e omega son os mesmos. Agora o que pasa coa selección tipo? Imos usar este novo vocabulario. Na selección de clasificación, o que estabamos facendo de novo, e de novo, e de novo? Eu estaba indo cara atrás e cara adiante a través de da lista, buscando quen? O menor número. Así como moitos pasos, como moitas comparacións fixo I ten que facer, a fin de descubrir quen menor elemento na lista foi? n menos un, non? Porque se eu comezar co que eu son dada e comezar a comparar a el ou ela, a continuación, el ou ela, el ou ela, el ou ela, eu só pode vincular elementos xuntos n menos 1 veces. Así, a selección leva especie semellante n menos pasos 1 a primeira vez. Cantos pasos me levar a atopar o segundo menor elemento? n menos 2, porque eu estou sendo idiota se eu continuar mirando para as mesmas persoas de novo se eu xa o elixiu ou ela e poñer-los no seu lugar. E o terceiro paso, n menos 3, entón n menos 4. Vimos este estándar antes, e de feito selección especie semellante ten un límite superior de n ao cadrado, se facemos o que suma. Cal é o seu límite inferior, a selección tipo? Como mínimo, o tempo de verificación debe tipo tomar, como definido o luns? Propoñer dúas opcións. Quizais sexa n, como antes. Quizais sexa n ao cadrado, como é agora como o límite superior. Audiencia: n ao cadrado. Palestrante: n ao cadrado. Por que? Audiencia: Porque ten definir [inaudível]. Palestrante: Exactamente. Polo menos mentres eu definido selección especie era moi inxenuo, siga indo, atopar o menor elemento. Vaia unha vez máis, atopar o menor elemento. Vaia unha vez máis, atopar o menor elemento. Non hai ningún tipo de optimización alí que pode deixar-me abortar despois só n ou máis etapas. Así, de feito, a selección tipo, omega de n ao cadrado. Que tal tipo de inserción, onde tirei que me foi dado, e entón eu estatelou lo ou ela no lugar seguro? Entón eu continúe a segunda persoa, estatelou lle no lugar seguro. Entón, a próxima persoa, se estatelou el ou ela no lugar seguro. Teña en conta que isto é moi lineal, por así dicir. Eu son unha liña recta, eu son non indo e volvendo, Nunca mirar atrás, realmente, pero o que está pasando cando inserir-lo ou ela ao comezo do lista como fixemos o luns? O que está pasando? Si? Audiencia: [inaudível]. Palestrante: Si, iso foi a captura, non? Pode lembrar de seus compañeiros de clase, se eles estaban facendo calquera movemento con seus pés, que era unha operación. Polo tanto, se había tres persoas aquí e a nova persoa pertencía camiño ata alí, nunha longa fase como esta, con certeza, el ou podería só ir ata o final. Pero se estamos a pensar nun ordenador e unha matriz de memoria, esas persoas van ter para barallar máis para dar espazo para esa persoa. E así que n menos un shufflings, n menos 2 shufflings, n menos 3 shufflings é só unha especie de pasando detrás de min, non na miña fronte como antes, nalgún sentido. Agora, como unha banda, e como podes ver en liña se comezar a bisbilhotar sobre tipos, hai tantos diferentes aí, algúns deles mellor que os outros. De feito, é unha bogosort ese é o tipo de diversión para ollar cara arriba. Bogosort leva un conxunto de números ou dicir un baralla de cartas, embaralha-los aleatoriamente, e comproba se están ordenados. E se non, fai iso de novo. E se non, fai iso de novo. Se non, fai iso de novo. Incrible estúpido. E, de feito, se ler como o artigo da Wikipedia, seu apelido é medio parvo. Será finalmente traballar, espero que, co tempo, pero que a cantidade de tempo pode levar algún tempo. Entón, se eu puidese, imos acelerar as cousas -se co exemplo de Mary Beth anteriormente, por máis algúns elementos, pero dous procesadores. Dúas persoas, se non me importaría de me xuntar. Como preto de 1 por aquí, e imos vai-- ninguén alí? Ninguén alí? Está ben. Vostede co negro camisa, si, imos alí abaixo. Todo ben, cal é o seu nome? Audiencia: Peter. Palestrante: ¿Que é iso? Audiencia: Peter. Palestrante: Peter, David, pracer de coñece-lo. Todo ben, temos Peter aquí, se quere vir á mesa por aquí. E cal o seu nome? Audiencia: Elena. Palestrante: Elena. OK, pracer de coñece-lo. Elena atender Peter. Peter, Elena. E necesitamos Andrew aquí tamén, por favor. E o reto vai ser para ordenar un baralla de cartas. E se non familiar, deck de tarxetas debe finalmente ser clasificado un pouco algo como este, onde faremos os clubs, a continuación, as espadas, a continuación, os corazóns e diamantes, de ace como un, todo o camiño ata o rei. As cartas que eu estou indo darlle van ser 52 en cantidade. Imos semellante xa que, en só un momento. Imos xogar Andrew na pantalla aquí, , Co fin de ver como fai iso. E para que todo isto é aínda máis visible, Estes son as tarxetas que recibín na Amazonia. Entón, eles xa están aleatoriamente clasificado, e nós estamos indo ao tempo que. E nós imos mantelo real esta vez, entón imos tentar preme-lo porque se non isto vai ser entediante rapidamente. Se puidese proceder para clasificar 52 elementos entre si a través de algúns medios, agora. E unha vez máis, como podemos ver estes caras fan o que, ao final producirá un evidente resultado, pense realmente como están a facer iso cada, como pode describilo. Porque unha vez máis, estas son todos os procesos, algoritmos que nós tomamos para concedida como un ser humano. Pero xa debería ter tido por moito tempo intuición, moito antes de ti mesmo pensou en tomar un ciencia da computación clase ti podería ter a intuición con que para resolver problemas como este. Pero unha vez que recoñece os patróns e comezar para formalizar as medidas coas que está resolvendo estes problemas, vai descubrir que pode resolver moi máis interesante e máis complexo problemas rapidamente. Entón, alguén do público, o que é polo menos un elemento do algoritmo que están a usar aquí? Audiencia: [inaudível] Palestrante: ¿Que é iso? Audiencia: por exemplo. Palestrante: por exemplo. Entón, primeiro se aglomeram todos os diamantes xuntos Parece que todo corazóns xuntos parecer, e así por diante, sen respecto para os números sobre as tarxetas. E agora aparecen, por exemplo, sendo os por número. Moi bo. Todo ben, entón o que vai ser o paso final, entón aquí? Unha vez que temos catro naipes clasificadas, o que facer o que necesitamos facer para as catro pilas , A fin de alcanzar un clasificadas convén, pura e simplemente? Entón, necesitamos mesturar-los de novo. Polo tanto, hai unha idea interesante que de novo, atrévome a dicir, é moi intuitivo mesmo se nunca podería esbofeteado este tipo de etiqueta nel. Esta noción fundamental de división o problema non en metade deste tempo, pero, polo menos, en catro anacos. Resolvendo practicamente problemas fundamentalmente idénticos illadamente uns dos outros, e entón fundir os resultados. E, excelente, feito. Todo ben, unha gran rolda de aplausos, se puidésemos. [Aplausos] Palestrante: Eu non teño idea o que vai ver con iso, pero aquí vai. Moitas grazas. Entón imos ver, dous minutos e oito segundos; se desexa desafiar os seus amigos. O que entón vai ser un sacar este que podemos aproveitar de forma máis xeral? Ben, creo que volta a este conxunto de números, e creo que volta agora a algúns dos pseudocódigo escribimos no pasado, e este foi o pseudocódigo para resolver o problema da lista telefónica. Nestas circunstancias, en pseudocódigo I enumerou unha forma máis metódica de describir como eu fixen un moi intuitiva algoritmo humano de dividir o teléfono libro pola metade, repetir, repetir, repetir, ata eu atopar alguén como Mike Smith, se é de feito no libro de teléfono. Pero eu medio que usei o que eu vou chamar unha visión moi iterativo aquí, en particular aviso liña 8 e liña 11. Estas son evidencias dunha iterativo visión, unha visión looping, porque é exactamente o comportamento que inducen. Estas liñas tanto dicir ir liña de tres, e pode tipo de pensar que, na súa ollo da mente como un loop. Está dicindo a vostede para volverse para o paso tres e repetir, de novo, e de novo, e de novo. Pero o que se aproveitar unha idea clave aquí que non por última vez, e simplificar a liña 8 e liña 11 e os seus veciños como só iso, en amarelo. Non é, fundamentalmente, acurtando pseudocódigo moito, pero está cambiando fundamentalmente a natureza do meu algoritmo. O que eu digo agora no paso 7, no paso 10, é a procura de Mike do mesmo xeito exacta, pero só na parte esquerda metade ou metade dereita. Así, noutras palabras, se Eu comezar a partir dunha etapa, incorporarse libro de teléfono, aberto a través do libro de teléfono, ollar os nomes, Se Smith está entre O nome de, chamar Mike, o máis Se Smith é anterior no libro, paso sete buscar Mike na metade esquerda do libro. Pero este tipo de sente como iso está me deixando colgado, non? En amarelo, é unha instrución, pero como fago buscar o Mike no esquerdo metade do libro de teléfono? Onde é que eu teño unha algoritmo co que eu Pode procurar por alguén como Mike Smith? Ben, iso está nos mirando na cara. Podo literalmente usar exactamente o mesmo programa vai efectivamente ata o cumio de novo e re-execución as mesmas liñas de código. Así, aínda que este debe sentir-se como un pouco de unha definición cíclico onde está a responder a alguén é Pregunta por só unha especie de preguntar a mesma pregunta de novo, por que, por que, por que? A realidade é porque temos codificado un par de liñas especiais, rango 4, que é un caso, e paso 12, que é efectivamente outro ramo, porque temos esas medidas paliativas, este algoritmo pode rematar se atopar Mike, ou se non o facemos. Pero no paso 7 e 10 agora temos o que imos chamar de un algoritmo recursivo. E recursão é de feito unha idea poderosa iso é un pouco de mente dobra en principio, que agora podemos aplicar a seguinte. Merge sort será o último tipo que miramos, polo menos na clase formalmente. E é fundamentalmente diferente daqueles tres últimos, e, por suposto, catro últimos se inclúen bogosort. Aquí está o pseudocódigo para merge sort. Cando a entrada de n elementos, entón dado unha matriz de tamaño n, se n é inferior a 2, volver. Entón, por que eu teño que verificación de sanidade en primeiro lugar? Cal é a implicación se eu entregar-lle unha matriz cuxa lonxitude n sexa inferior a 2? El xa está clasificado, obviamente, non é? Como a lista ten tanto un elemento, o que é trivial clasificadas por que é o único que existe. Ou, é de tamaño cero, o que significa non hai nada para resolver, por iso, natureza el é clasificado. Só hai nada de malo alí. Entón, ese é o noso chamado caso base. Isto é semellante en espírito ao que fixemos con Mike. Se Mike no libro de teléfono, chame el. Se non está alí, renuncia. É un chamado proceso de base, para asegurarse este algoritmo, ao final do día deixará en determinadas circunstancias. Pero aquí está o salto de fe agora, máis, ordenar a metade esquerda dos elementos, logo clasificar o dereito metade dos elementos, e logo mesturar as metades clasificados. E aquí é onde se sente como estamos amarelando. Pedinlle para clasificar n elementos, e eu son dicindo: OK, faino por clasificación á esquerda e á selección da dereita. Pero eu digo unha outra cousa, e esta é o tema central parece na intuición, ata agora, hai esta terceira etapa de fusión. Que aínda Parece tan burro en espírito, como só mesturar cousas xuntos, parece ser un paso fundamental para o reasemblaxe de dous problemas que foron divididos en última instancia, á metade. Entón, merge sort, imos facelo, se humor me, con máis dunha demostración, só para que teñamos algunha números de traballar. Podo cambiar oito estrés bolas para oito persoas? Todo ben, que tal vos tres, vostedes catro nesta sección, cinco, seis, e imos non 7, 8, imos cara arriba. OK, si Aceptar. Minus 8, alí imos nós, máis 1. Excelente. Todos veñen a dereita enriba, imos rapidamente darlle números. O número dous, número tres, número catro, número cinco, seis, sete, e oito. Eu fixen oito correctamente esta vez. OK, entón vai adiante se puidese, e imos clasificar en orde orixinal que tivemos onte que parecía así, se non se importar. E imos facelo diante da táboa. Todo ben, entón merge sort. Este é o lugar onde vai para chegar ben interesante, porque parece que estou me dando moito menos información hoxe. Así fundir tipo en primeiro lugar na entrada de n elementos, e é, obviamente, non inferior a dous, é oito, entón eu teño un pouco máis de traballo para facer. Entón, agora nós mentalmente como unha clase están na outra filial, o que significa que tres pasos. En primeiro lugar, teño que resolver o metade esquerda dos elementos. Entón como é que eu vou facer iso? Ben, eu estou indo para o tipo de dividir mentalmente a lista aquí, non ten que mover fisicamente, e estou vai centrar-se só na metade esquerda dos elementos aquí. Entón, como fago para clasificar unha lista agora do tamaño de catro? Cal é o meu algoritmo? Primeiro eu verifico é n inferior a dous, non, para que eu continúe para o bloque máis novo. Ordenar deixou metade de elementos. Polo tanto, agora de novo, mental, e é aí onde ten que acumular unha morea de historia mental, se quere. Agora estou clasificando á esquerda a metade do lado esquerdo. Todo ben, entón agora eu chamo o meu mesmo merge algoritmo de clasificación, é n inferior a dous? Non, é dous, entón eu teño que clasificar a metade da esquerda, e á metade dereita. Entón, imos alí, ordenar a metade esquerda. Por que non só dar un paso adiante. Cal é o seu nome? Audiencia: Darren. Palestrante: Dan. Dan deu un paso á fronte. Audiencia: Darren. Palestrante: Darren, feito. Vostede dixo Darren ou Dan? Audiencia: Darren. Palestrante: Darren. OK, Darren ten intensificado adiante e que é agora clasificada. E iso é case unha reivindicación inane, non? Realmente non parece estar a acadar nada, pero imos seguir. Agora déixeme ordenar a dereita metade dos elementos. Cal é o seu nome? Audiencia: Lucas. Palestrante: Lucas. Imos, un paso adiante. Feito, eu classifiquei Lucas. A metade esquerda é agora clasificado e a metade da dereita é agora clasificada, pero, de novo, hai un paso clave aquí. O que eu teño que facer o próximo? Unir as metades clasificados. Agora imos ter só todo atrás e para adiante deste xeito, porque eu medio que teño un espazo de borrador. É case como se estes caras están sobre unha mesa, e eu teño un espazo para mover los en. Entón eu vou para mesturar vostedes mirando na metade esquerda e o da metade dereita. E que, obviamente, ven en primeiro lugar, metade esquerda ou metade dereita? Entón metade dereita, entón imos mover Lucas sobre aquí a posición orixinal de Darren. E agora fundir a súa metade esquerda en, Darren vai mover á dereita alí. Entón, parece que case un efecto bubble sort, pero o meu algoritmo fundamental moi diferente esta vez. Pero agora é onde as cousas están un pouco aburrido, porque ten que rebobinar mental onde foi que eu parei. Acaba fundiu as metades ordenada, o que significa que eu estou onde no meu algoritmo? Teño que clasificar a metade dereita, non? Se volver, literalmente no vídeo, vai ver que chegamos a este punto de Luke e Darren clasificando á esquerda a metade do lado esquerdo. Logo, fundiu os metades ordenadas, que significa que o seguinte paso é o tipo metade dereita da metade esquerda. Todo ben, entón imos facelo máis rápido. Todo ben, seis, eu vou reclamar está agora resolto, imos para adiante. Cal é o seu nome? Audiencia: Adriano. Palestrante: Adriano. Adriano está clasificada. E cal o seu nome? Audiencia: Alex. Palestrante: Alex está clasificada. Media esquerda, media dereita, cal é o paso final? Unir. Moi trivial, polo que estou vai fundir en seis, dar un paso atrás, oito, dar un paso atrás. E agora entender iso é un takeaway útil, o que é agora feito sobre a metade esquerda da lista, independentemente de como empezamos? Está clasificada. Agora non está clasificada en o gran esquema das cousas, pero ela é ordenada independentemente da outra metade. Agora, o que paso son eu en manterse rebobinar como a historia comezou? Agora eu teño que clasificar a metade dereita. Polo tanto, agora estamos no camiño de volta o comezo da historia, e imos facelo máis rápido. Entón eu vou para clasificar a metade dereita da lista enteira. Cal é o seguinte paso? Ordena a metade esquerda da metade dereita. Ordena a metade esquerda da a metade esquerda da metade dereita. E cal o seu nome? Audiencia: Omar. Palestrante: Omar, un paso adiante, feito. A metade esquerda está clasificada. E cal o seu nome? Audiencia: Chris. Palestrante: Chris, dar un paso á fronte, está agora clasificada. Cal é a clave paso agora? Unir. Entón, un vai fusionarse en lugar aquí, se puidese dar un paso atrás, e tres vai dar un paso atrás, se funden. Así, a metade esquerda da metade dereita, agora está resolto. Francamente, este algoritmo se sente como nós están gastan moito máis tempo do que antes, pero se non o fixo en tempo real, imos ver o que os delivery será. Agora estou aquí, non a metade do lado dereito, déixeme ir adiante e resolver a metade esquerda. Paso adiante, o que é o seu nome? Audiencia: Ramsey. Palestrante: Ramsey está clasificada. Cal é o seu nome? Audiencia: Marina. Palestrante: Marina está clasificada como Ben, se der un paso á fronte. Clave paso aquí agora é fundir, eu son vai arrincar das miñas dúas listas, esquerda e dereita. Cinco vai vir en primeiro lugar, e sete vai vir axiña. E, de novo, iso é proposital. O feito de que están levando pasos para adiante e cara atrás emprégase para representar que non podemos facer ese algoritmo no lugar coa mesma facilidade como bubble sort, e selección de tipo, e inserción tipo en que só mantivo cambiando persoas. Eu literalmente ten que un tipo de papel de borrador en que para poñer esas persoas mentres fago a fusión, e entón eu podo poñer-los de volta no lugar. E iso é fundamental, porque eu estou usando un nova función, o espazo, non só tempo. OK, iso é incrible. A metade esquerda é clasificado, a metade dereita é , Agora que a clave fusión etapa de clasificación. Como é que eu vou mesturar esa? Entón, se seguir o meu man esquerda e man dereita, Vou apuntar a miña man esquerda na metade esquerda, man dereita na metade dereita, e agora eu teño que decidir paso a paso que se fundir en. Que, por suposto, ven en primeiro lugar? Número un. Entón veña para aquí, aquí está o noso bloque de borrador. Entón, agora o número un, e previo o que vou facer coa miña man dereita, Vou pasar a miña man dereita pasar por riba ao punto número tres, e agora eu teño que facer a mesma decisión. E, de feito, estar ben na cabeza de Luke aquí se puidese, porque este é o noso bloque de borrador. Entón, quen vén a continuación? Temos Luke co número dous ou Chris co número tres. Obviamente Luke, número dous, para que veña aquí. Pero a miña man esquerda agora vai ser incrementado para ligar a Darren, e aquí está a clave aproveitar con fusión, eu vou continuar a facer iso, Obviamente, se tipo de seguir a lóxica. Pero as mans nunca son indo a ir cara atrás, o que significa que eu estou sempre só movendo-se a esquerda co meu proceso de fusión, e que será a clave para nosa análise en só un momento. Entón agora imos rematar isto rapidamente. Entón, tres vén a seguir, despois catro vén a seguir, e agora vén a continuación cinco, despois seis, e sete, e finalmente oito. Parece que o algoritmo máis lento aínda, pero non se realmente executa-lo, ao mesmo tipo de velocidade de reloxo, por así dicir, coa mesma tique-taque do reloxo como antes. Por que? Ben, Imos dar un mirar para o resultado final. Imos volver aquí, déixeme puxe unha demostración visual que acabamos de facer. Achegar-se aquí, neste páxina aquí, dicindo Firefox que queremos cola ata neste campo, imos dicir bubble sort, co cal agora estamos ben familiarizados, tipo de selección, que é outra bastante un simple, e agora merge sort de hoxe, que será o noso clímax final. A razón que levou moito máis tempo aquí cos seres humanos e me verbalmente é, obviamente, eu estou explicando cada paso. Pero se simplemente executar este, moi como fixemos bubble sort e selección tipo, non só visualmente, reloxo o que de forma máis eficiente esta alavancagem de división e conquista se pode, cando aplicado a un conxunto de datos que é nin mesmo tamaño oito, pero aínda moito, moito maior. Eu doulle merge sort, lado a lado con estes outros algoritmos. Isto vai estar doloroso rapidamente, eo final non é particularmente climático, eles simplemente acabar ordenados. Pero a clave sacar é que Mira o que máis rápido merge sort era, a menos que pensas que eu son só unha especie de xogar con vostede. Se facemos iso unha última vez, Imos actualizar isto, imos volver e escolle bubble sort, e só por diversión, Imos escoller a inserción tipo, só para unha boa medida. E esta vez, unha vez máis, imos escoller merge sort e imos realmente realizar estes mosaico. E non é, en realidade, un golpe de sorte. O que eu fixen de forma eficaz é que eu teño repartiron a miña entrada no medio, unha vez máis, e de novo, e de novo. E hai só tantas veces pode partir a entrada en metades, esquerda e á dereita. Cal é a fórmula que sigo vendo que describe a división en metade de novo, e de novo, e de novo, e de novo? Audiencia: Log n. Palestrante: Log n. Pero despois hai outro gran paso, este algoritmo non é log n pasos. Se só foron log n pasos, estariamos no mesmo problema como antes, onde non podemos ser Asegúrese de que está todo resolto. Ten que ollar minimamente n elementos para estar seguro de n elementos son ordenados, pola contra, é un salto de fe. Entón é rexistro minimamente n pasos, pero o que pasa con este paso clave fusión onde fundiu miña metade esquerda e dereita medio e atravesou o escenario? Cantos pasos é que fundirse? É n, pero non o fixen só mesturar o tempo final. En cada unha destas chamadas noutras citas, en cada destas fusións aniñados, eu aínda clasificadas. Eu fundiuse eses dúas caras, entón estes dous caras, entón eses dous caras e así por diante. Entón eu fixen a fusión de novo, e de novo. Cantas veces? Entón cada vez que eu dividía o lista pola metade, eu fixen unha mesclagem. Débeda a lista ao medio, facer unha mesclagem. Polo tanto, se a división Árbore se pode facer de rexistro n veces, e en definitiva, a fusión ten n etapas, o que se pode agora o superior Encadernado pola execución tempo do noso algoritmo? n log n. E, de feito, é o que nós conseguimos aquí. Entón, a sensación que ve cando visualmente estas tres cousas corren mosaico n é cadrado contra n cadrado contra o rexistro n n. Que fundamentalmente nos veremos, Non só, pero hoxe en día, no futuro, é moito máis rápido. Unha salva de palmas para estes faces, Vou recompensa-los con bolas de estrés. Imos pechar aquí hoxe, e imos velo na luns.