[Música tocando] 

DAVID J. Malan: Todo ben. Entón Benvido de volta. É dicir CS50, e é o o fin de semana tres. 

Entón, lembra nas últimas semanas, estamos gastan un pouco de tempo en C, en programación, en sintaxe. E é moi normal, se aínda está loitando co conxunto de problemas 2, para ser bater a súa cabeza contra a parede. É mensaxes de erro enigmáticas para o futuro e os erros que non pode perseguir. Porque, pode estar seguro, que en só un tempo de algunhas semanas vai ollar cara atrás cousas como César, e [? V-genair,?] quizais ata de crack, e entender o quão lonxe chegou nun curto período de tempo. Entón, se isto serve de consolo, colgar alí por un tempo. 

Hoxe, con todo, comezan a transición para cousas de máis alto nivel. E comezamos a dar por feito que Vostedes saben programar, ou polo menos o inicio que o nivel de confort. E imos comezar a considerar como podemos ir sobre a creación de programas máis eficaz. Como podemos ir sobre como optimizar o eficiencia dos algoritmos e adoita ser a solución máis problemas interesantes. E comezando a tomar por certo que, se quixésemos, poderiamos codificar calquera dos exemplos que temos en mente. Entón, hoxe, non tocar o teclado a calquera forma de código. Vai ser nivel moito máis elevado, e en última instancia, sobre a resolución de problemas. 

Entón, para chegar a ese punto, deixe-me propor que os seguintes sete rectángulos representan sete portas, detrás que son unha morea de números, entre os cales está o número 50. Déixeme proxectar este neste pantalla aquí tamén. E propoñer que necesitamos un voluntario para me axudar a atopar un número diante Internet aquí para ver. Imos para arriba, en cor rosa. Todo ben. Cal é o seu nome? 

Jennifer: [inaudível] 

DAVID J. Malan: Sentímolo? 

Jennifer: Jennifer. 

DAVID J. Malan: Jennifer. Todo ben, Jennifer. Pracer en coñece lo. Imos para arriba. Entón, eses aquí son sete portas, e que Quere facer para nós aquí, diante de todos os seus compañeiros, é atopar-nos o número, 50. Para atopar un número, pode espreitar detrás calquera destas portas simplemente tocando nunha das portas, e revela o seu número. E imos ver como rápido pode atopar-nos o número, 50. 

15. 16. 50. Ben feito. Todo ben. Salva de palmas para Jennifer. 

[Aplausos] 

Todo ben. Entón, cal foi a súa estratexia para atopar o número, o 50? 

Jennifer: Hum, eu penso que quizais se - [Inaudível] 

DAVID J. Malan: Oh Dele un segundo. Así foi a súa estratexia para atopar o número, o 50? 

Jennifer: Entón, eu só comezar no empezando a ver que o primeiro número era, e entón eu penso, se cadra se están clasificadas, vou seguir tocando máis alto? 

DAVID J. Malan: Aceptar. E parece ter atopado que sexa este o caso. Aínda que, imos pelar as capas só un pouco, e quere ir adiante e revelar as outras portas podería ter escollido? 

Jennifer: Oh, querida. 

DAVID J. Malan: Ah. 

Jennifer: Entón eu só teño sorte. 

DAVID J. Malan: Entón vostede tivo sorte. Todo ben. Entón, non é malo. Pero iso é un interesante insight, non? Se asumiu, e conseguiu, en realidade, un pouco de sorte alí. Pero se do principio de que as cifras eran clasificadas, pode ser máis preciso de como iso influenciou o seu comportamento? 

Jennifer: Entón, se eles foron ordenados, eu penso que quizais menor ao maior. 

DAVID J. Malan: Aceptar. 

Jennifer: Ou se iso acabou sendo realmente grande, entón maior a menor. 

DAVID J. Malan: Aceptar. Entón maior a menor, ou menor ao maior. Pero déixeme propoñer, supoñamos que tiña obtido de azar, e supoñer que non foron, de feito, clasificado, cantos aquelas portas que podería ter para espiar atrás en que o peor caso? 

Jennifer: Todos eles. 

David J. Malan: Todos eles. Entón imos xeneralizar que, como n. Non pasa a ser 7, pero imos máis xeralmente din que hai n portas no pantalla aquí. Así, no peor caso, que tería que para ollar cara atrás sete portas, ou n portas. E así, este realmente é, é un pouco de sorte hoxe, pero é realmente un lineal algoritmo do tipo, aínda que eran unha especie de saltar arredor. Iso é xusto? 

Jennifer: Yeah. 

DAVID J. Malan: Ben, deixe-me ver se o cambios de estratexia, se nos moven noso segundo exemplo aquí con 7 portas distintas. Os mesmos números, pero esta xa que son clasificados. Cal é a súa estratexia aquí vai ser, intentando borrar da súa mente o que os outros números foron - 

Jennifer: Aceptar. 

DAVID J. Malan - máis cedo? 

Jennifer: Imos comezar co primeiro. 

DAVID J. Malan: Todo ben. Comeza o primeiro. 4. Agora, onde vai pasar, e por que? 

Jennifer: 4 é moi pequeno. Entón, se son unha especie quizais menor a maior, que debería ser o dobre, e -. 

DAVID J. Malan: Aceptar. A ver, o que pensas? 

Jennifer: Proba a última. Niza. 

DAVID J. Malan: Moi ben feito. Todo ben. 

[Aplausos] 

DAVID J. Malan: Aceptar. Entón, en realidade está a facer iso horrible, porque é facelo moi ben. O que nos deixa sen poder facer determinados puntos. Entón, imos tratar de reverter aquí. 

Jennifer: Aceptar. 

DAVID J. Malan: Moi ben feito, con todo. Entón comezou o principio, viu que tiña 4 anos, entón desprazada cara ao final. Pero supoñamos que non ten sorte alí, e supoño que o 50 estaba noutro lugar. Cal é a súa terceira etapa ser? 

Jennifer: Voltar para o comezo. 

DAVID J. Malan: Volva ao principio. OK, entón tería tocado esta porta, o cal foi de 8. Todo ben. Entón, iso non é 50. Onde é que mirou ao lado? 

Jennifer: Se eu non fixen saben que clasificados. 

DAVID J. Malan: Correcto. Ben, se soubese foron clasificadas - 

Jennifer: Ah, sabía, si. 

DAVID J. Malan: - pero non fixo sabe onde 50 foi aínda? 

Jennifer: Só continuar. 

DAVID J. Malan: Todo ben. Aceptar. Continúe indo. OK, para que eu poida traballar. 

Jennifer: Aceptar. 

DAVID J. Malan: Agora, se está só continuará, o que é o seu algoritmo que recaen apoiado en. 

Jennifer: o lineal -. 

DAVID J. Malan: É unha especie de lineal. Pero déixeme propoñer, imos me poñer no lugar. Déixeme actualizar a páxina. mesmo número, o mesmo arranxo, mesmas portas. Pero creo que volver a aquel primeiro día en clase cando resgou un libro de teléfono en metade, máis ou menos, eo que era nosa estratexia alí? 

Jennifer: Comezar polo medio. 

DAVID J. Malan: Aceptar. Polo tanto, comece no medio. Entón, imos adiante e simular iso. Comezar polo medio por revelando que porta. Polo tanto, o número 16. Entón, o que a cara forte fixeron, que resgou o libro de teléfono pola metade, para chegar ao seguinte palpite? 

Jennifer: Vai no semestre. 

DAVID J. Malan: E por que a dereita? 

Jennifer: No caso de que eran unha especie de menor para o maior, entón debe ser 50 nesa extrema. 

DAVID J. Malan: Xenial. Totalmente razoable. Así como un libro de teléfono, vai a dereita, por oposición á esquerda, pero aquí é o principal argumento. Agora podes xogar fóra, ou arrincar, semestre deste problema, deixando o non con 7 portas, pero realmente con só 3. Que é preto de metade da dimensión do problema. Todo ben. Polo tanto, agora que tería feito despois de que vai á dereita? 

Jennifer: So 16 aínda é moi pequeno, en relación a 50, quizais por iso eu vou probar, como, un agasallo. 

DAVID J. Malan: Todo ben. 42. Todo ben, entón agora o que é o seu instinto dicindo a vostede? 

Jennifer: Eu podo xogar fóra isto e, a continuación, só - 

DAVID J. Malan: Aceptar. Bo, pode xogar fóra a metade esquerda alí. 

Jennifer: - escoller un. 

DAVID J. Malan: E a dereita. 

Jennifer: Yeah. 

DAVID J. Malan: Entón, aínda que sexa difícil ver se cadra, cando hai só Sete portas, pensar, agora, a consistencia do algoritmo que acaba de aplicar. No caso anterior, o que fixo ter sorte, o que foi xenial. Pero fixo utilizar unha heurística, Eu diría. Usou unha especie de seus instintos, e saber ordenado, se é moi pequena en principio, obviamente, temos ten que ir máis á dereita. Pero, en certo sentido, tes sorte, porque quizais este foi o número 100, e quizais 50 foi máis no medio. Quizais 50 fose o mesmo por aquí. 

Pero o que fixo un pouco diferente esta vez foi, fixo o mesmo unha e outra vez. E eu diría que o que acaba se, aínda influenciado por teléfono libro exemplo, é algo moi máis algorítmica, e moito menos especial casetonado. Moito menos instintivo. Así, ao final do día, como sería que describe a eficacia do primeiro algoritmo, onde se esquerda a dereita, contra o segundo algoritmo aquí? 

Jennifer: Isto débese, como, quizais reducir á metade o tempo, ou máis, si. 

DAVID J. Malan: OK, quizais ata máis. Imos empurrar un pouco máis sobre iso. O que realmente si continuar esta lóxica, nós sempre reduciu á metade o tempo de carreira con este segundo algoritmo xogando fóra a metade do números, pero o que imos facer o próximo iteración, cando Jennifer revelou o segundo número? 

Nós á metade o número de portas de novo. E entón o que fixemos tras o que, se había máis portas para xogar? Queremos metade deles, e unha vez máis, e de novo, e de novo. E iso era exactamente como vostedes todos pé na primeira semana de clase, a metade do que sentir-se, a metade de sentir, a metade de vós sentir-se, ata que un solitario alma estaba de pé. E nós dixemos que o tempo de execución tanto, o número de pasos Bastou na orde de que? 

COLUMNA 1: [inaudível] 

DAVID J. Malan: Entón rexistro base 2 de n, ou só máis sinxelo, faga o login do n. Polo tanto, algo logarítmica. E a gráfica non é unha liña recta que quedou peor e peor, foi interesante que esta curva non fixo ir tan mal ao longo do tempo. Entón, imos manter esa idea. Imos dar as grazas a Jennifer. Moitas grazas por teren benvida enriba. E, un segundo. Non hai mesa lámpadas hoxe, pero nós ten CS50 bolas de estrés. 

Jennifer: Yay. 

DAVID J. Malan: Todo ben, aquí. Grazas por incorrer o estrés aquí. Todo ben. Entón, imos ver se non podemos agora formalizar esta un pouco máis. Entón, de novo, o que fixemos foi esencialmente o mesmo que fixemos en que a primeira semana. Pero en vez de final con só un lineal algoritmo, que representado anteriormente como esa liña recta, polo que, se colocarmos unha porta pantalla, logo Jennifer tería tiveron que mirar, potencialmente, detrás de unha porta. Se colocarmos dúas portas, un pode ter para ollar cara atrás dúas portas. 

E así, houbo esa lineal relación entre o tamaño da problema en, por exemplo, o eixe x, e a cantidade de tempo que leva a resolver na y. Pero a imaxe que eu estaba aludindo anterior era esta liña verde. Verde deliberadamente, porque el só me sentín mellor. En teoría, o algoritmo, cando fixemos co libro de teléfono, cando fixemos convosco contando os uns aos outros, e no segundo caso, cando só Jennifer fixen iso aquí enriba, que era unha especie de fundamentalmente mellor. Porque non foi só dúas veces máis rápido. Non era ata catro veces máis rápido. Foi totalmente dependente do que a tamaño da entrada foi, de cantas pasos que finalmente levou. 

E así esta idea simple que todos tomamos adquirido co libro de teléfono, semellante pode ser aplicado para algo así. E iso pode ser máis informal coñecida como, como pode imaxinar, dividir e conquistar. Non ao contrario do que fixemos, claro, co libro de teléfono. 

Pero o pseudocódigo, aviso, foi iso. Polo tanto, non imos facelo de novo, pero recordar esta primeira semana, todos nós se levantou e logo, a metade do que sentou-se, a metade dos que sentou-se, a metade do que sentou. Este algoritmo implementado nun pouco de unha forma de trapaça, en que, el Non foi só unha das me contando, fundamentalmente, de forma máis eficiente. Nese caso, eu estaba panca unha característica secundaria. Máis ou menos, CPUs múltiple, cerebros, varias persoas intelixentes no sala estaban me axudando a comezar a partir de algo lineal para algo logarítmica, de algo vermello para algo verde. 

Pero, neste caso, Jennifer só pode fundamentalmente mellorar a desempeño do seu primeiro algoritmo, unha vez máis, só de pensar un pouco máis. E agora, cando chega a hora de aplicar isto, descubrir que as liñas de código que se pode escribir como que se pode repetir-los de novo, e de novo, e de novo, unha especie de nunha forma de looping. Porque non vai ter a luxo, como Jennifer fixo nun primeiro momento, a só ten unha morea de IFS e dicir: hmm, se este primeiro número é 4, déixeme ir todo o camiño ata o final. Ooh, se ese número é moi grande, déixeme pasar cara atrás de forma arbitraria ao segundo elemento. Verá que vai ser moi máis difícil de formalizar o que nós, seres humanos tomar para concedida como moi razoable heurística, pero un ordenador é só vai facer o que diga a el para facer. 

Agora, isto ten moi interesante implicacións. Esta gráfica é unha especie de significado para clasificar de sobrecargar visualmente, aínda que o aviso previo, onde é a recta neste gráfico? Onde está o gráfico lineal que chamamos n? Ben, é unha especie de para o fondo da imaxe, non? Entón, todo o que fixemos é que teño a sorte de zoom out para o eixo x ea eixo-y para tratar de obter unha noción do que outros tipos de curvas parecen. 

E as particularidades da matemática expresións, hoxe, non importa a moito, pero entender que hai unha gran cantidade de algoritmos que son moito peores que algo que é lineal. En realidade, n cubos parece moi malo. 2 ao n parece moi malo. n ao cadrado parece moi malo. E imos ver o que algúns deses se pode, na realidade de hoxe. E log n non se sente tan mal, pero mellor que n é o rexistro de base 2 do n. Pero vostede sabe, el sería aínda máis sorprendente se Jennifer, ou se, esta primeira semana, xurdiu con algo que é rexistro de rexistro de n. 

Polo tanto, noutras palabras, non hai toda esta gama de posibles solucións para problemas, pero, mesmo aquí, o aviso o que vai ocorrer. Cando diminuír o zoom, cal destas curvas vai probar ser o absoluto peor os que están na pantalla agora? Entón n cubos parece moi mal no momento. Pero se diminuír o zoom para ver máis xe eixo-y, que vai dominar en última instancia? Entón, el realmente se que 2 a n, e pode descubrir que só por conectar nalgún cada vez maior números, e verás que 2 ao n, de feito, moito máis rápido se fai maior. Se realmente diminuír o zoom, a 2 ao n algoritmo absolutamente unha merda. Quero dicir que iso vai levar un pouco de tempo para a ordenador para axitar completamente. 

Pero vai ver ao longo do tempo, sobre todo con conxuntos de problemas futuros, e mesmo proxectos finais, e os seus datos conxunto se fai grande, non? Mesmo na primeira versión de Facebook, como o número de amigos, eo número de usuarios rexistrados ten gran pode clasificar de teléfono-lo e aplicar algo con procura lineal, ou unha clasificación moi sinxelo algoritmo, como veremos hoxe. Ten que comezar a pensar máis e máis sobre estes problemas. E os tipos de problemas locais como Facebook e Google e Microsoft, e outros, traballar é exactamente estes tipo de datos gran tipo de preguntas cada vez máis nos días de hoxe. 

Todo ben. Así, o éxito de Jennifer, en que a segunda algoritmo, a verdade, ela fixo incrible ben o primeiro tempo, pero imos escribilo como sorte, para que pode facer neste momento. No segundo caso, ela panca un algoritmo que repetiu de novo e de novo, pero ela levou para concedida unha correcta suposición de que permitimos , Pero explotado algún detalle o segunda vez que ela non ten o primeira vez. Que era o que? 

Que a lista foi clasificada. Así, logo que a lista foi resolto, nós afirman que Jennifer era capaz de facer fundamentalmente mellor. Sete portas, si, non é tan interesante, pero creo que estamos 7.000.000 portas. Sesión de n está indo definitivamente para realizar moi, moi máis rápido no longo prazo. Pero ela tiña que ter a portas clasificadas para ela. Agora, eu tomei a liberdade de facer o que con antelación na pantalla do ordenador aquí, pero creo que Jennifer tiven que facelo soa? Supoñamos que as portas se trate datos representados nunha base de datos, ou amigos rexistrados para Facebook, ou todas as páxinas web en internet que varios sitios pode ter ao índice ou investigación sobre. 

Supoña que acaba de ter un conxunto de datos en bruto definir e se deixou para ti, ou para Jennifer facelo de selección? Que, ao contrario, esixe que nós respondemos o tema, así como, canto tempo levaría Jennifer, ou mesmo de min, para ordenar os números con antelación para que podería sacar proveito diso? Non? Porque a implicación, claro, é se me leva moito tempo para clasificar as cifras, quen diaños lle importa que pode atopar un número como 50 tan rápido, como no caso de Jennifer, máis de esmagada a cantidade de tempo total tardou, clasificando as cousas con antelación? 

Entón, imos ver se a xente non pode pintar a imaxe aquí. Eu teño unha morea máis estrés esfera, se iso axuda romper o xeo aquí. E se non se importar, nós precisa sete voluntarios - on, Aceptar. Guau. Entón, non ten que gastar en lámpadas de mesa, ao parecer. Todo ben. Así como sobre vostedes dous diante. Que tal vostedes dous nas costas. Entón, iso é catro. Como sobre ti diante cinco, seis e sete. Ben alí. O seu amigo está a apuntar para fóra, co fin de obter o premio. 

Todo ben. Imos para arriba. E por que non telo caras vén aquí. Vou darlle cada un número. E vai adiante e organizar-se de forma idéntica ao que está representado na pantalla. 

[Interpondo voces] 

DAVID J. Malan: Oop, sorry. Bug Todo ben. Ben, aquí imos nós. Número cinco. Número seis. Un, dous, tres, catro, cinco, seis, sete. Oh, iso é raro. 

COLUMNA 2: Vou coller un -. 

DAVID J. Malan: Bo negocio. Todo ben. Grazas por participar. 

[Aplausos] 

Aceptar. Todo ben. Polo tanto, temos catro, dous, seis, un, tres, sete, cinco. Mellorar iso temos sete voluntarios aquí que son iguais á anchura do matriz que estamos xogando co anterior. E eu escollín sete por razóns que será só conveniente un pouco. E eu vou propor por primeira vez que nós clasificar estes sete voluntarios. Se quere, en primeiro lugar, para dicir Ola aínda. Xa que este será un embaraçosas varios minutos. Apresente-se. 

GRACE: Ola, eu son Grace. Eu son un estudante de segundo ano en Leverett House. 

Branson: Hi Estou Branson. Eu son un calouro na Weld. 

Gabe: Oi Estou Gabe. Eu son un Júnior na Cabot. 

NEIL: Eu son Neil. Eu son un calouro na Matthews. 

Jason: Eu son Jason. Eu son un calouro na Greenough. 

MIKE: Eu son Mike. Eu son un calouro na Grays. 

Jess: Eu son Jess. Eu son un estudante de segundo ano en Leverett. 

DAVID J. Malan: Excelente. Todo ben. Ben, grazas a todos os nosos voluntarios aquí ata agora. E o reto na man agora vai ser a de clasificar estes faces, pero, a continuación, imos ter que pensar un pouco moito sobre como realmente eficiente clasificou. Entón, imos primeiro tentar iso. Podedes ver os números uns dos outros só por poñer en torno aos cantos. Dalle levar varios segundos, e tipo-vos do menor na esquerda a maior da dereita. Ir 

Aceptar. Bo Iso foi moi danado rápido. Agora, alguén aquí, cal foi o algoritmo que estes faces aplicada? 

COLUMNA 1: Polo menos a máis grande. 

DAVID J. Malan: Aceptar. Polo menos a máis grande é realmente unha especie de obxectivo, pero eu non estou seguro que é realmente un algoritmo. Polo menos a maior non di me paso a paso o que facer. Si? 

COLUMNA 1: [inaudível] 

DAVID J. Malan: Aceptar. Entón, se ve unha persoa menor que seu número, entón moverse para o dereito deles. Así que agora está quedando cada vez máis significativo, máis como un algoritmo, porque pódese dicir, se iso, entón aquilo. Entón temos algún tipo de construción condicional. E eses caras parecían facer que algúns veces, porque algúns de vós cambiaron un pouco dunha distancia. Entón, houbo presuntamente algún tipo de Looping suceder nas súas mentes. 

Pero imos intentar formalizar isto. Se vós puidesen recuperar a este arranxo. A ver se non podemos formalizar esta unha pouco, e, a continuación, facer a pregunta, só quão eficiente é esa? Claro que, cando facemos iso de forma máis lenta, vai se sentir tan ben de un algoritmo, pero imos ver se podemos poñer os dedos sobre os pasos precisos. 

Entón, vostedes dous son catro e dous. Ou orde correcta ou incorrecta? Obviamente incorrecta. Entón nós trocamos. Agora estou indo a mover de lado aquí e dicir: 4-6. Está correcta ou incorrecta? 

Gabe: Correcto. 

DAVID J. Malan: Correcto. Seis e un? Non. Intercambia. Entón, iso é dous swaps. Seis e tres anos? Non. Intercambia. Seis e sete? Parece bo. Sete e cinco? 

Jess: [inaudível] 

DAVID J. Malan: OK, troque. E clasificados. Todo ben. Entón, obviamente, non, non? Entón alí estaba máis a suceder. Pero, en realidade, eses faces, aínda só instintivamente. continuou movendo. Eles non parar, xa que corrixido un problema. Así. En realidade, eu vou ter para facer o mesmo. Vou ter a sorte de retroceder cara atrás para o inicio deste problema, ou no inicio da presente de matriz persoal, imos comezar a chamalos. 

E agora, o que debe o meu algoritmo na segunda pasaxe será? 

COLUMNA 1: o mesmo. 

DAVID J. Malan: Mesma cousa. E iso, eu estou empezando a gustar, non? Así que pode atopar-se facendo o mesmo unha e outra vez, iso é tornándose máis como un algoritmo, instinto e menos humana. 

Entón, agora, aquí imos nós de novo. Dous e catro? Non Catro e un? Ah, houbo de feito algunhas traballo aínda por facer. Por e tres? Bo Catro e seis? Seis e cinco? Seis e sete? OK, agora, feito. OK, non. Teño que volver. 

Entón, agora, unha vez máis, estamos a facer iso algo máis deliberadamente. E agora, hai só un cerebro executar este algoritmo. Unha CPU, se quere. E, francamente, este é o único recurso imos ter acceso. E unha vez que voltar a un teclado e ter algo así como C no noso disposición, estamos só escribindo un programa que pode facer unha cousa de cada vez. Considerando que, estes faces hai un momento, nos panca a súa intelixencia colectiva como vostedes fixeron a semana cero. Entón, imos seguir facendo iso. 

Dous e un. Dous e tres. Tres e catro. Catro e cinco. Cinco e seis. Seis e sete. Feito? Entón, eu estou, pero deixe-me xogar avogado do diaño. Eu, o tipo de ordenador que só fixo un pase por este conxunto de persoas, sabe que eu son feito? 

COLUMNA 1: Non 

DAVID J. Malan: Entón por que? O que eu teño que facer, a fin de completar decisivamente que estou facendo? Probablemente unha pasaxe. Non? Por todo o que sei de que anterior pase é que resolve un erro. E isto significa, é posible que haxa aínda outro erro que eu teño corrixir. Entón eu só podo estar seguro de rebobinagem, e logo, alomenos, 1-2, e dous tres, tres e catro, catro e cinco, cinco e seis, seis e sete. OK, agora eu fixen ningún traballo. 

Podo certamente me lembro que fixen non traballar con algo así como unha variable, como un int. Chamalo swaps, e swaps é 0 xa que eu chegar ata aquí, e empezou a 0, entón Quere só de ser estúpido para continuar adiante e cara atrás, comprobando de novo, e de novo, e de novo, non? Porque queda preso en algún especie de loop infinito. Así, logo que hai 0 swaps, podemos afirmar que esta algoritmo é realmente completa. 

Agora, imos poñer un nome sobre o tema. O algoritmo que propoño nós só aplicado é unha cousa chamada burbulla tipo, coñecida como tal na medida en que os números que son maiores do tipo de burbulla seu camiño ata o cumio, ou para o fin da serie de números. Pero quão eficaz foi ese algoritmo? Cantos pasos que teño físicamente para ter, por exemplo, para clasificar estas sete seres humanos? 

De catro a cinco anos? OK, moitos é en última instancia será a resposta. Pero, aínda así, o número específico non é tan interesante. Imos xeneralizar como n. Entón, se eu tivese n persoas aquí enriba, e foron, dalgún xeito, en orde aleatoria no comezando, en que orde orixinal. Ben, cantos pasos eu tiña para asumir a primeira paso? Era un, dous, tres, catro, cinco, seis, e son sete persoas, de xeito que é sete, seis -, de xeito que non menos os pasos dunha primeira vez. 

Agora, cantos pasos eu tiña tomando cando rebobinado? Ben, poderíamos dobrar este se Nós realmente queriamos, pero por agora, estou só vou dicir, todo ben, outro n menos 1. Así, o n menos un se ve irritante para seguir, así que imos só redondear lixeiramente. Entón 2n pasos. Entón, 14 etapas, máis ou menos. 

Cantas veces eu tomo un paso da seguinte visita? Ben, é 3N. realmente. E agora, no peor dos casos, por exemplo, cantas veces eu tería ir para atrás e cara adiante, cara atrás e cara adiante, executar este algoritmo, cambiando persoas en cada paso, máis ou menos? Realmente n ao cadrado, non? 

Porque, no peor dos casos, pode tipo de pensar sobre iso de forma intuitiva, aínda que levar un pouco pouco de tempo para afundir-se dentro No peor dos casos, o que sería iso sete persoas parecía, en termos do acordo dos seus números? Totalmente para atrás, non? E só para simular que, cal era o seu nome? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, pode simplemente engadir-me ao longo aquí por só un segundo? En realidade, non. Sentímolo Mike, imos retroceder. Cal é o seu nome? 

NEIL: Neil. 

DAVID J. Malan: Neil. OK, Neil, que vén con me, se non lle importa. Entón eu vou propoñer, só para simplicidade, que Neil está agora no seu peor caso posible. Pero lembre-se como eu apliquei meu algoritmo. Estou comparando, comparando, comparando, comparando, comparando, oh. Agora, estes faces están fóra de orde, así que eu resolver. Entón vós trocar. Pero considere agora, canto máis lonxe Neil Non ten que ir? É máis ou menos n. Vostede sabe, non é, en realidade, n. É como se, n menos 1, pero estou quedando irritado manter o control do pequeno número, entón imos chamalo de n. 

Entón, se Neil move un paso máximo de cada tempo, e para desprazarse Neil un paso, Eu teño que facer este paso realmente tedioso e cara atrás, é dicir máis ou menos Facendo isto, n pasos, dun total de n veces, porque me vai levar que moitos pasos para chegar Neil todo o camiño cara a onde el pertence. Deixade todo o mundo se vostedes foron todos mis-ordenada, ben. 

Entón, imos chamar bubble sort n ao cadrado. O tempo de execución deste algoritmo, o desempeño deste algoritmo, o eficiencia deste algoritmo, imos só describir máis xeralmente como n ao cadrado. Que é bo, porque eu podería facer o mesmo exemplo, con oito persoas, nove persoas, un millón de persoas, e iso resposta non vai cambiar. 

Entón, se vostedes non lle importaría, imos axustar-lo para onde comezou. E imos tratar outras dúas enfoques e ver se non podemos facer fundamentalmente mellor que este. Entón, esta vez, vou propoñer unha especie de algoritmo diferente. Iso foi moi intelixente de nós a última vez, e vostedes estaban certos de ter a instintos seguros de só unha especie de intercambio de parellas. Pero se realmente quería abordar este simplemente, e meu obxectivo é mover-se todos os números de pequenos deste xeito, e empurrar todos os grandes números que Así, por que non podo facer iso só no máis inxenua maneira posible e ver se eu pode facer mellor que o que era un algoritmo bastante complexo? 

Entón imos ver. Catro é un número moi pequeno, polo que estou vai deixar lo alí momento. Ooh, o número dous é aínda mellor. Entón podes só un paso adiante por un momento? Este é actualmente o meu menor numerado solicitante, e eu vou lembrar que con, tipo, unha variable. Pero eu vou manter a verificación. Hai alguén cuxa número é menor? Seis, non. Oh, hai Neil novo. 

Entón eu vou empurra-lo de volta tipo de conceptualmente. Neil virá para adiante. E agora, a variable que eu estou a usar para seguir o que ten o menor número é actualizado para conter Localización de Neil. Ben, imos ver. Tres, sete, cinco. OK, sei que Neil era menor. Cal é a cousa máis sinxela para eu facer agora? Non vou perder o meu tempo por só Neil burbulla un lugar cara á esquerda. Por que non podo simplemente poñer Neil onde pertence, o que é, por suposto, onde? 

Todo o camiño no inicio. Entón Neil, veña comigo. E cal era o seu nome? 

GRACE: Grace. 

DAVID J. Malan: Grace. Aceptar. Entón, Graza, por desgraza, está tipo de no camiño. Entón, como imos solucionar este problema? Non? Se esta é unha matriz, non hai só sete localidades. Lembre que, con Rob, falamos de declarando as idades, e que só tiña un número finito de idades? A mesma idea aquí. Temos só un número finito de enteiros. Graza é unha especie de no noso xeito, entón como é que imos resolver? 

O xeito máis sinxelo é así, Graza, desculpe. Vai ter que pasar por riba de alí para que poidamos facer o cuarto. Agora, se pensar sobre iso, é posible que nós só empeorou o problema. E quizais nós fixemos, xa que o que se Graza estaban no lugar seguro? Pero sabemos que non é porque se non, ela sería pé á fronte en vez de Neil neste momento, non? Xa checo o número para fóra. 

Todo ben. Entón, agora, Neil está no lugar seguro, e Podo facer unha pequena optimización. Ao seguinte minuto, eu vou pasar por alto Neil todos xuntos, co fin de non desperdiçar seu tempo, ou accidentalmente troca-lo para o lugar incorrecto. Entón, agora, como fago para o seguinte elemento que é menor? Dous. Isto é un número moi bo, se quere dar un paso adiante e Vou lembrar de ti. Seis, non é bo. Catro, tres, sete, cinco, non é bo. Entón deixe-me leva-lo para o seu lugar seguro. E nós só temos sorte esta vez. 

Agora, eu vou pasar por alto estes dúas caras, e agora facer unha pasar por iso. Six, que un número moi pequeno. Imos adiante. Oh, desculpe. Número de Grace é mellor, para pisar para adiante. Four. Sentímolo, Grace. Volver de novo. O número tres é mellor. Sete. Cinco. E agora, cal é o seu nome? 

Jason: Jason. 

DAVID J. Malan: Jason. Así Jason é agora menor elemento que seleccionei. Onde está indo? Entón, onde seis é. E o seu nome é novo? 

Gabe: Gabe. 

DAVID J. Malan: Gabe. Gabe é o camiño. Cal é a cousa máis fácil de facer? Intercambia estes dous caras e continuar. Entón, agora imos ver. Quen é o máis pequeno? Four. Déixeme só un tipo de fraude. Cinco será menor. Creo que o próximo si, quere pisar á fronte, o que eu teño que ver coa estes faces, con Gabe? Intercambia novo. Entón, agora, aínda un pouco fóra de orde. Eu atopei Gabe a ser menor, entón Eu pop-lo, movelo máis caras. E feito. 

Así resposta é a mesma. O resultado final é o mesmo. Cal destes dous algoritmos é mellor? A segunda, escoitei. Por que? 

COLUMNA 3: é n pasos [inaudível]. 

DAVID J. Malan: É n pasos, como máximo. Interesante. Así é que? Así como eu atopar o menor elemento? Cantos pasos que eu teño que tomar a atopar o menor elemento? Eu tiña un ollar todo o camiño ao final, non? Porque en que o peor caso, o que Neil se foron por aquí? Entón, só tes que atopar o menor elemento me n pasos, ou non menos 1 leva. Pero Aceptar. Entón resolver Neil. Lembre que, aproximadamente un minuto. 

Pero como é que o seguinte menor elemento? É n menos 1, ou n menos 2 realmente, a partir do número de pasos. Entón Aceptar. Entón eu fixen n menos 2. Todo ben. Así que se sente un pouco mellor. Todo ben. Cantos pasos a próxima vez atopar o número tres? Así, n menos 4. Entón está diminuíndo, unha a menos pisar en cada iteración. Polo tanto, este non se sentir mellor, non? Se a última vez que foi máis ou menos n veces n, esta vez é menos n 1, máis n menos 2, ademais de n menos 3, máis n menos 4, punto, punto, punto. Pero se se lembra da súa escola libros de texto, a pequena fraude folla na parte de atrás que ten fórmulas, se sumar esta serie de números, que é o número total de pasos será que eu levo aquí? 

Este é un destes, tipo, n menos 1, n veces, divididos por 2. Entón deixe-me ver se podo tirar isto por só un momento. E de novo, eu son o tipo de redondeo algúns números só para manter a nosa vida simple, pero se ben me lembra, é algo así como se Eu n menos unha cousas, entón n menos 2, entón n menos 3, é máis ou menos algo parecido con iso máis de 2, e se eu multiplicar tanto, é realmente praza n. Que non está sentindo moi ben. n n menos dous. 

Pero aquí está a cousa. En ciencia da computación, cando os problemas comezan a estar interesantes é cando n queda moi grande. E cando n queda moi grande, o que de estes valores vai dominar todo dos outros? El é o tipo de n ao cadrado, non? Si, dividíndose por dous é moi bo. Pero se está a falar de millóns de anacos de datos, ou billóns de anacos de datos, ok, entón está dúas veces máis rápido. Pero quen realmente lle importa se ese gran número, Se ese factor é o que recibe cada vez maior. E, por suposto, fai máis de unha diferenza que este cara. Así, aínda que vostedes están certos, o segundo algoritmo, imos chamalo selección de tipo, é, no mundo real, un pouco máis rápido, potencialmente, porque eu son tomando cada vez menos pasos de cada vez. 

Realmente non é fundamentalmente máis rápido. Porque se realmente xogar isto para grandes valores de n, a finais do o día, grande abondo para n, aínda é vai sentir-se moi lento. Ben, deixe-me tirar unha último paso por aí. Iso é o que eu chamaría selección especie. Podedes reiniciar-se unha última vez? E neste último caso, eu vou propoñer algo chamado ordenación por inserción. Ordenación por inserción ser, conceptualmente, un pouco diferente. 

En vez de ir cara atrás e cara adiante e seleccionar o menor elemento, eu son só indo para tratar con cada unha delas caras como eu atopalos, e insira los no seu lugar correcto. Entón, eu só vou comezar con Graza, e eu vexo que é o número catro. Onde é que o número catro pertence? Non comece nada de selección, entón Grace comeza a estar alí. E agora vou reclamar, se puidese dar un paso á dereita, este miña lista ordenada, esa é a miña lista resto indiferenciados. Entón agora eu vou continuar a seguir, e cal é o seu nome? 

Branson:. 

DAVID J. Malan: Branson. Entón Branson é o número dous. Entón, eu vou leva-lo por un momento. E agora, onde pertence neste array? Así, para o dereito de gracia. Entón, de novo, somos o tipo de facer Graza facer unha chea de traballo aquí. Onde é que imos poñer-lo? Entón, nós estamos indo para desprazar-lo para o á esquerda, e introducir Branson alí. Pero agora eu afirmo que vostedes están feitos. Mais repare, eu non estou a usar o espazo extra. É aínda dous elementos aquí, cinco alí. Tamaño total do conxunto é de 7, polo que estou non enganar, todo ben? 

Polo tanto, agora temos, con Gabe aquí, o número seis, onde pertence? Tivo sorte de novo. Entón, comeza a estar alí. Só un lixeiro paso cara á dereita só para deixar claro que está clasificado. E agora temos Neil de novo, o número de un, onde vai? E agora é o lugar onde nós imos comezar a ver que este algoritmo, que en primeiro vista, séntese moi intelixente, asista que está a piques de acontecer. Se puidese avanzar. 

Onde queremos poñer Neil? Entón, obviamente, aquí, así como obtemos Neil alí? Imos facelo paso a paso. Gabe, onde ten que ir? Si, así que tomar un gran paso, ou dúas medias-medidas para facer un paso por alí. Graza, onde vai? Bo Así, outra etapa. E, finalmente, Branson? Outro paso. E agora podemos poñer Neil no lugar. 

Entón, agora, seguir esa lóxica. Aínda que non están cambiando Neil máis, e máis, e máis, para poñelas onde pasa, no peor caso, o seguinte número podemos atopar podería ser o número, por exemplo, houbo un número cero, entón imos cambiar todo estes faces. Supoñamos que hai un número negativo un, entón temos que cambiar todos estes caras. Entón, nós estamos realmente só unha especie de inversión o problema ao redor, de xeito que estamos transferir o gasto do de xeito que o proceso de selección de inserción proceso, de xeito que vostedes só tiña para mover uns n menos algo número de pasos. E ese número de pasos é só ir aumentar a medida que eu escoller máis números, se eu tivera que estar empurrando vostedes cara atrás, e volta, e volta. 

Entón, a cousa máis triste é agora todo isto algoritmos son n ao cadrado. Imos adiante e, grazas a estes caras, e visualiza-las un pouco diferente. Moi ben feito. 

[Aplausos] 

Todo ben. Alí vai. Grazas por - 

Branson: [inaudível] manter os números. 

DAVID J. Malan: Non, pode manter os números así. Todo ben. Ben feito. Todo ben. Entón imos ver se non podemos agora resumir máis rápido e máis visual exactamente o que pasou aquí como segue. Eu estou indo a ir adiante tire superior Firefox. Imos chamar esa demostración na páxina web do curso. Java é un pouco aburrido para comezar a traballar nalgúns navegadores estes días. Entón, se xogar con iso na casa, entender que pode ter usar Firefox para facelo funcionar. E o que eu vou facer con este demostración é o seguinte. 

No fondo, eu teño unha morea de opcións de menú, incluíndo un comezo e un botón de parar. Ademais, como unha banda, parece haber un erro nestes programas, no que non pode realmente ver o partido ou parada botón, a menos que manteña Mando ou Alt máis e zoom in, que curiosamente mostra máis botóns. Polo tanto, só FYI, se xogar con iso na casa. Agora eu vou facer clic en Inicio, en só un momento, despois dun atraso de especificar, como, a 200 milésimas de segundo aquí, só para que poidamos ver o que acontece. 

Entón, eu afirmo que esta é unha vista do primeiro algoritmo estes faces fixeron, bubble sort, no que nós trocamos persoas por pares. O insight fundamental para esta visualización é que a altura das barras representa o tamaño do número. Así, o máis alto do bar, o Canto maior sexa o número. Máis curto da barra, menor o número. E se observar, estamos pasando por a primeira iteración do algoritmo, cambio de pequenos e grandes números, de xeito que o número pequeno ven en primeiro lugar e o gran número vai á dereita. 

E así chegamos ao final dun array de moitos máis números que sete, estamos vai volver ao principio. E anticipar iso. Na extrema esquerda, que o rapaz está a suceder para cambiar para o lado, e isto proceso se repite. Agora esa visualización fica rapidamente aburrido, entón deixe-me ir adiante e deixar , Cambie o atraso algo moi máis rápido só para comezar agora, unha sensación de este algoritmo. 

Así, aínda que eu aceleraba-se, este é como actualizar meu procesador, a mercar un novo ordenador. Non cambiaron fundamentalmente a miña algoritmo, pero realmente pode ver máis claramente do que cos humanos, que a gran números están burbullas ata o cumio, e os números pequenos están burbulla cara á parte inferior. E agora esta cousa aquí clasificados. E, como un aparte, nas prazas, hai só algunhas Escrituração alí para axudar a contar cantas comparacións, ou cantos swaps teñen realmente se fixo. 

Ben, imos tentar unha das os outros que vimos. Déixeme prema o bubble sort aquí, e déixeme escoller, e esta páxina enteira é un pouco buggy. Imos aceptar o risco e executa-lo de novo. Alí imos nós. Entón imos facer a selección tipo. Non sei por que o menú aparece por alí. Imos zoom para solucionar isto erro, cambiar isto para 50. Ah, imos realmente facer moito máis rápido. Cinco milisegundos ou menos, e comezar. 

Polo tanto, esta é a selección de tipo. Entón, de novo, pensar sobre o que fixo os seres humanos aquí. Nós fomos a través da matriz e seleccionados o elemento máis pequeno, de novo, e de novo, e de novo. Agora eu afirmo que aínda era moi malo. Foi aínda n ao cadrado, máis ou menos, pero foi, no mundo real, un pouco máis rápido, por que eu estaba realmente tomando algo menos pasos de cada vez. Pero estamos só falando o que? Quizais 40 ou máis bares aquí? Non estamos a falar de 40 millóns. Polo tanto, non é totalmente claro para min que era de feito unha ganancia significativo. 

Déixeme agora volver atrás e cambiar a nosa terceiro algoritmo, que foi seleccionado ordenación por inserción. E agora é realmente de buggy, xa que o menú non debería estar alí. Entón, agora imos rolar para atrás ata aquí e iniciar este algoritmo. Whoopi, comezar e parar. Así, este tipo de ten un estándar moi a ela, no que estamos unha vez máis inserindo os seres humanos, ou en Neste caso, as barras en a súa situación axeitada. E el xa fixo antes Eu me virei. Pero este, tamén, en teoría, aínda n ao cadrado. 

Entón imos ver se non podemos resumir estes como segue. Eu estou indo a ir adiante e só para dar nós tipo de un xeito común de falar sobre isto, deixe-me presentar só un pouco de notación aquí. Está a piques de ver unha cousa chamada gran Ó, por que é, literalmente, unha gran O. e esta é unha forma que un ordenador científico ou un matemático aínda usa para describir o tempo de execución dun algoritmo. Cantos pasos realmente tomar? 

Agora eu vou avergoñar con miña carta aquí en só un momento. Pero déixeme ir adiante e dicir que iso vai ser gran por aquí ó. E deixe-me presentar outro símbolo, un omega capital. Omega será o contrario, esencialmente, de gran O. Considerando que a gran O significa, no peor dos casos, a cantidade de tempo pode levar algún algoritmo, en termos de n, omega vai ser canto tempo podería tomar no mellor dos casos. E imos ver o que se entende por mellor dos casos, en só un momento. 

Entón, imos comezar algo sinxelo. Déixeme comezar por unha procura linear. Polo tanto, non a clasificación. Imos chamar esa procura lineal. E agora, facer un pouco de mesa de fóra desa. E agora, no caso da investigación lineal, no peor caso, cantos pasos se vai me levar para atopar unha número de elección arbitraria? E hai n portas totais ou n cifras totais. Peor caso. Cantos pasos vou ter que tomar para atopar o número 50 en unha matriz de n portas? E por que? Porque pode ser o único camiño para o final. Tanto como Jennifer atopa, o número 50 foi todo o camiño, polo que, o peor procura lineal caso é grande de n, imos dicir. 

E canto mellor dos casos, se ten moita sorte? Só vai dar un paso, ou un número constante de pasos. Entón, imos describir isto como un. Entón, iso é moi bo. Agora o que se fixo algo como busca binária? Investigación de modo binario, no peor caso, levou canto tempo? 

[Interpondo voces] 

DAVID J. Malan: Entón, en realidade, eu escoitei nalgúns lugares. Entón, é realmente entrar n, máis ou menos, porque, coma nós dividimos a lista ao medio de novo, e de novo, e de novo, somos capaces para atopar, por fin, o valor, se el está aí, pero hai unha pegadinha. Cal é a suposición de que temos que ter concedido para a procura binaria? Ten que ser resolto. Non está resolto, pode dividir a cousa polo medio de novo e de novo, e pode ir á esquerda, e pode ir á dereita, e pode ir á esquerda e á dereita, pero é Non vai atopar o elemento que a lista non está ordenada porque pode perde-la. Porque a súa heurística, para ir á esquerda ou á dereita será fallo, se é en realidade, non clasificados. Polo tanto, hai unha especie de custo oculto para usar algo así. 

Agora, imos para a nosa clasificación algoritmos non busca - Oh, realmente imos entrar en branco. Busca binaria no mellor dos casos? É tamén un caso só pasa de ser ben no medio da matriz, ou no medio da lista telefónica. Agora imos facer o bubble sort. Entón, de novo, agora estamos entrando na tipo, e non as enquisas. 

No peor dos casos, cantos pasos que fixemos reivindicación bubble sort vai levar? n ao cadrado. Entón eu vou aproveitar iso. Ooh, miña letra parece aínda peor cando está previsto que grande. Todo ben. Entón iso n ao cadrado. E, no mellor dos casos de bubble sort, cantos pasos é que vai tomar? 1, escoitei. 

COLUMNA 1: n. 

DAVID J. Malan: n, eu oín. 

COLUMNA 1: 2. 

DAVID J. Malan: 2, escoitei. Escoito 3? Todo ben. Entón escoitei 1, n, 2, pero imos escoller ademais de polo menos a primeira desas suxestións, 1. Non é un mal instinto, porque tipo de segue un estándar aquí. Pero se só ten un paso, como no o mundo que eu podería reclamar que a lista é ordenada, porque se eu estou só permitida tomar un paso, cantos elementos En realidade, eu podería comprobar a estar seguro? Ben, só un, o que significa que hai n menos un elementos que poderían estar fóra de orde, e eu só vou na fe despois mirando para un elemento que o cousa está clasificada. Entón 1 non é correcto aquí. Así, minimamente, cantos que eu teño que mirar? 

[Interpondo voces] 

DAVID J. Malan: n menos 1, ou realmente, n, porque eu preciso ollar para cada elemento para asegurarse de que non está fóra de orde. Pero, de novo, nós imos resolver de onda nosa mans en números menores e supoñer que, a medida que n se fai grande, son desinteressante calquera maneira. Entón, iso é bubble sort. E agora, imos facer estes dous últimos. Tipo de selección, e despois imos facer ordenación por inserción. E entón vai explotar a súa mente con algo moi mellor que todos estes. Todo ben. 

Cal é o peor caso en execución momento da selección tipo? 

COLUMNA 4: n ao cadrado. 

DAVID J. Malan: n cadrado, estou escoitando. Pero por que non ao cadrado, intuitivamente? 

COLUMNA 4: Porque só fixen iso. 

DAVID J. Malan: Por nós só fixen iso. Aceptar. Boa resposta. Pero intuitivamente, por que é a selección tipo n ao cadrado? O que temos que facer unha e outra vez? Tivemos que manter a dixitalización a través, son vostede o máis pequeno, é o máis pequeno, é o máis pequeno. E concedido, fomos capaces de tomar n pasos, entón n menos 1, entón n menos 2. Pero se especie de engadir todos aqueles por riba, ou leva-la na fe que eu engade Los con antelación, temos preto de n cadrado menos algúns números menores. Entón, eu vou chamar a este n ao cadrado. Pero, coa selección de tipo no mellor caso, cantos pasos se me vai levar? 

COLUMNA 5: [inaudível] 

DAVID J. Malan: É, por desgraza, aínda n ao cadrado, non? Porque se eu estou escollendo menor elemento, e tivemos sete persoas aquí, Eu só sei que, cando chegar ao moi final, que eu atope a menor número, onde queira ela pode ser. Pero como fago para o seguinte menor número? Teño que facer outra pasaxe. Así, no mellor dos casos, o que é o de entrada para a selección tipo? É unha lista xa especie, número un, número dous, número tres, número catro. Pero eu son un ordenador. Só podo ollar a un cousa de cada vez. Non podo clasificar de dar un paso de volta como un ser humano e dicir: Ooh, iso parece correcto. 

Só podo xulgar correcto en selección especie, seleccionando o menor número. Pero aínda que eu atopar o número un en primeiro lugar, se eu non sei nada sobre os outros números, o que eu non fago, todo o que eu sei que teño sido entregada unha matriz ou un conxunto de portas de atrás, que son números, o único xeito que sei que un foi o máis pequeno? Se eu chegar ata aquí e entender, caramba, unha era de feito o máis pequeno. 

Pero como fago para, entón, determinar que dous é a seguinte menor? Ao facer o mesmo ineficiencia unha e outra vez. Entón, finalmente, coa ordenación por inserción, como, no peor dos casos, se dicimos que el executa? Tamén é n ao cadrado. E que tal co mellor caso? Imos deixar isto como un cliffhanger. Imos encher ese baleiro a próxima vez, pero primeiro deixe-me propor que fundamentalmente facer mellor que todo isto, non? 

Entón, pense por si mesmo que a inserción tipo vai ser. Ben, iso non era moi dramática, porque eu son o único que viu o cambio. Guau. Aceptar. Entón aquí temos algo demostración diferente. Se eu aumentar o zoom aquí, vai ver que en Á esquerda temos bubble sort, no medio temos a selección de clasificación, e en a extrema dereita, temos algo que non mirei aínda chamado merge sort. Pero considerada o que fomos facendo aquí, ata agora, hoxe. Cando Jennifer veu por primeira vez enriba do escenario, pasamos a matriz de números de novo, e de novo, coa procura lineal, e temos tempo de execución lineal, grande de n, por así dicir. 

Cando consideramos agora a primeira semana de clase cando tiñamos dividir e conquistar, e nós tiñamos o libro de teléfono lacrimejamento, e Jennifer, e colectivamente panca ese insight fundamental, que era repetirse unha e outra vez por algunha forma de xogar fóra, xogando fóra, xogar fora, a metade do problema, ou Xeralmente, dividindo-se un problema no medio, e despois tratar o anaco menor de o problema como conceptualmente equivalente a outra, que dalgún xeito fixo fundamentalmente mellor. Pero co bubble sort, coa selección tipo, con ordenación por inserción, temos pode ningún destes insights que Jennifer fixo. Nós practicamente só andou cara atrás e ante un grupo enteiro de veces, e nós cousas revolto un pouco, cambiando por esta orde, quizais inserir ou seleccionar. Pero ao final do día, eu fixen unha morea de andar torpe e cara atrás. Non realmente aproveitar algo intelixente como Jennifer gusta dividindo e conquistador. 

Así tipo fundir, pola contra, que non vai ver ata a próxima semana, que vai para alavancar a idea clave, dividindo de entrada e, a continuación, reducir á metade e logo reducir á metade, a continuación, reducir á metade. E, en cada iteración do bucle de que, clasificando a metade esquerda e á dereita a metade, a continuación, a metade esquerda da metade esquerda, ea metade dereita da esquerda e logo a metade esquerda da metade dereita, e a metade dereita da metade dereita. E repetindo unha e outra vez. 

Entón, vai ver que visualmente, pero esta é o que nos espera a próxima semana. E, en xeral, cando pensamos un pouco pouco máis difícil en calquera problema deste tipo. Nós n ao cadrado da esquerda, n cadrado no medio, e n log n da dereita. Polo tanto, non hai o suspenso real. Vemo-nos o luns. 

[Aplausos]