>> [Música tocando]
DAVID Malan: Todo ben.
Todo ben, benvido de volta.
Polo tanto, esta é a Semana 4, o inicio º, xa.
E vai lembrar que, a semana pasada, poñemos código de lado por un pouco
e comezamos a falar un pouco máis de alto nivel, sobre cousas como
investigación e clasificación, que aínda ideas son simples, pouco
representativo dunha clase de problemas vai comezar a resolver particularmente
como comezar a pensar en último proxectos e solucións interesantes que
pode ter de problemas do mundo real.
Agora bubble sort é un dos máis simple tales algoritmos, e
Traballou por estes pequenos números nunha lista ou nun tipo conxunto de
burbulla seu camiño ata o cumio, eo grandes números mover o seu camiño ata
o final da lista.
>> E lembrar que puidésemos ver bubble sort algo
algo así.
Entón deixe-me ir adiante e prema en Inicio.
Eu xa pre-seleccionado bubble sort.
E se lembrar que o azul máis alto liñas representan números grandes, pequenas
liñas azuis representan pequenos números, como pasamos por iso de novo e de novo e
unha vez máis, comparando dúas barras de mosaico outra en vermello, imos cambiar o
maior eo menor se están fóra de orde.
>> Entón, que vai continuar e ir , E podes ver que a maior
elementos están facendo o seu camiño cara ao dereito, e os elementos menores son
facendo o seu camiño cara á esquerda.
Pero empezamos a cuantificar a eficiencia, a
calidade deste algoritmo.
E nós dixemos que, no peor caso, este algoritmo levou
aproximadamente cantos pasos?
>> Entón n ao cadrado.
E o que era n?
>> Audiencia: Número de elementos.
>> DAVID Malan: Entón n foi o número de elementos.
E así imos facelo moitas veces.
Cada vez que quero falar sobre o tamaño dun problema ou o tamaño dun
entrada, ou a cantidade de tempo que leva para producir unha saída, imos
xeneralizada o que a entrada é como n.
Entón, de volta na Semana 0, o número de páxinas na lista telefónica foi n.
O número de estudantes na sala foi n.
Entón, aquí, tamén, que estamos seguindo ese estándar.
>> Agora n ao cadrado non é especialmente rápido, entón intentamos facer mellor.
E así, nós miramos un par de outros algoritmos, entre os que
foron selección especie.
Así, a selección especie foi un pouco diferente.
Era case máis sinxelo, atrévome a dicir, cal I iniciada o comezo do
Lista dos nosos voluntarios e eu de novo e outra vez pasou por
Na lista, arrincar a menor elemento de cada vez e poñelas ou
ela no comezo da lista.
>> Pero iso, tamén, xa que empezamos a pensar a través da matemática e maior
imaxe, penso en cantas veces Eu estaba indo cara atrás e cara adiante e cara atrás
e cara atrás, nós dixemos, no peor caso, selección especie, tamén, era o que?
n ao cadrado.
Agora, no mundo real, pode en realidade, ser lixeiramente máis rápido.
Porque unha vez máis, eu non teño que manter retroceso, xa que eu ordenara a
pequenos elementos.
Pero se pensamos moi grande n, e se tipo de facer a matemática como
Eu fixen no taboleiro, co n ao cadrado menos algo, o resto
ademais do n ao cadrado, xa que non queda moi grande, non
realmente importa tanto.
Así como os científicos da computación, que especie de pechar os ollos a menor
factores e concentrarse só no factor de unha expresión que vai facer
a maior diferenza.
>> Ben, finalmente, nós miramos a ordenación por inserción.
E este foi semellante en espírito, pero en vez de pasar por iterativa e
seleccionar o menor elemento dun tempo, en vez tomou a man que me
foi tratado, e eu decidimos, o único seguro, vostede pertence aquí.
Logo, mudei-me para o seguinte elemento e decidiu que el ou
ela pertencía aquí.
E entón seguín adiante e continuar.
E eu podería para, ao longo do camiño, cambiar estes faces, a fin de
dar espazo para eles.
Así, foi unha especie de troco mentais de selección tipo que
chamado ordenación por inserción.
>> Entón, eses temas para ocorrer no mundo real.
Só uns anos, cando un determinado senador estaba concorrendo á presidencia,
Eric Schmidt, no momento en que o CEO de Google, en realidade, tiven a oportunidade
entrevistalo.
E nós pensamos en compartir ese YouTube clip para vostede aquí, se puidésemos transformar-se
o volume.
>> [REPRODUCIÓN]
>> -Agora, o senador, está aquí en Google, e me gusta de pensar na presidencia
como unha entrevista de emprego.
>> [Risas]
>> -Agora é difícil conseguir un posto como presidente.
E está pasando os rigores agora.
Tamén é difícil conseguir un emprego en Google.
Temos preguntas e pedimos Os nosos candidatos preguntas.
E este é de Larry Schwimmer.
>> [Risas]
-Vostedes pensan que eu estou a xogar?
É aquí mesmo.
Cal é o xeito máis eficaz para ordenar un millón de números enteiros de dous bits?
>> [Risas]
>> -Ben, uh -
>> -Sinto moito.
Quizais devêssemos -
>> -Non, non, non, non, non.
>> -Iso non é unha -
Aceptar.
>> -Creo que o bubble sort sería ser o camiño mal.
>> [Risas]
>> [Aclamacións e aplausos]
>> -Imos, que lle dixo iso?
Aceptar.
>> [FIN reprodución de vídeo]
>> DAVID Malan: Entón tes iso.
Entón comezamos a cuantificar estes execución veces, por así dicir, con algo
chamado notación asintótica, que é só referíndose a nosa especie de transformar
os ollos para estes factores menores e só mirando para o tempo de execución,
a actuación destes algoritmos, como n queda moi grande co paso do tempo.
E así, nós introducimos gran O. e Big O representaba algo que pensabamos
como un límite superior.
E, de feito, Barry, podemos diminuír que o micrófono un pouco?
>> Pensamos que isto é un límite superior.
Tan grande S de n significa que, en cadrado peor dos casos, algo así como
selección tipo levaría n pasos cadrado.
Ou algo parecido a ordenación por inserción sería n pasos cadrado.
Agora, para algo así como a inserción tipo, cal foi o peor caso?
Dado un array, que é o peor escenario posible, que se pode atopar
se depara con?
>> É completamente para atrás, non?
Porque si é totalmente cara atrás, ten que facer unha chea de traballo.
Porque se está totalmente cara atrás, vai atopar o
maior elemento aquí, aínda que pertence alí.
Entón vai dicir, todo ben, a Neste momento, vostede pertence aquí,
así que deixar só.
>> Entón entende, oh, droga, eu teño que mover este elemento lixeiramente menor para
á esquerda de ti.
Entón eu teño que facelo de novo e de novo e de novo.
E se eu andei para atrás e para adiante, vostede clasificar de sentir o rendemento dos
que o algoritmo, xa que constantemente son barallar todos os outros para abaixo na
matriz para facer o cuarto para el.
Entón ese é o peor caso.
>> Por outra banda -
e iso foi un cliffhanger última vez -
dixemos que a ordenación por inserción era un omega de que?
Cal é o mellor caso running momento da inserción do tipo?
Entón, en realidade é n.
Ese era o baleiro que deixou no marco da última vez.
>> E é omega de n por por que?
Pois ben, no mellor caso, o que se ordenación por inserción será entregado?
Ben, a lista que está completamente resolto xa, o mínimo de traballo para facer.
Pero o que é interesante sobre a ordenación por inserción é que, xa que comeza aquí e
decide, oh, que é o número un, vostede pertence aquí.
Oh, o que unha boa fortuna.
>> Vostede é o número dous.
Tamén pertenzo aquí.
Número tres, mellor aínda, vostede pertence aquí.
Así que se chega ao final da pseudocódigo lista, por inserción de tipo
que atravesou verbalmente última vez, está feito.
Pero a selección tipo, pola contra, continúe a facer o que?
>> Continúe a lista novo e de novo e de novo.
Porque o coñecemento clave que só había unha vez que mirou para todo o camiño para a
final da lista pode estar seguro que o elemento que foi seleccionado
de feito o menor elemento actualmente.
Entón, estas diferentes modelos mentais final cedendo algúns moi real-world
diferenzas para nós, así como estes diferenzas asintótica teóricas.
>> Entón, só para recapitular, entón, gran O de n cadrado, vimos algúns como
algoritmos ata agora.
Big O de n?
¿Que é un algoritmo que podería pode dicir para ser grande de n?
No peor dos casos, leva unha serie lineal de pasos.
>> OK, procura lineal.
E no peor caso, onde está o elemento que está a buscar cando
aplicación de busca lineal?
>> OK, no peor caso, non o é alí.
Ou o segundo peor caso é todo o camiño ao final, o que é
máis-ou-menos unha diferenza dunha etapa.
Así, ao final do día, podemos dicir que é lineal.
Big O de n sería de procura lineal, porque, no peor caso, o
elemento non está alí ou é todo o camiño ao final.
>> Ben, O gran de rexistro de n.
Nós non falamos en detalles sobre isto, pero xa vin iso antes.
Que é executado no chamado logarítmica tempo, no peor dos casos?
>> Si, investigación de modo binario.
E busca binaria no peor caso Pode que o elemento en algún lugar
no medio, ou nalgún lugar no interior da matriz.
Pero só atopalo xa que dividir a lista pola metade, en
metade, pola metade, pola metade.
E, a continuación, listo, el está alí.
Ou aínda, peor caso, non o é alí.
Pero non sabe que el non está alí ata que especie de chegar a ese último
baixo para a maioría dos elementos de reducir á metade e reducir á metade e reducir á metade.
>> Big O de 1.
Para que puidésemos gran O de 2, O gran de 3.
Sempre que sexa só un número constante, Nós só unha especie de só simplificar
que tan grande de unha.
Aínda que se realista, hai que 2 ou ata 100 pasos, se é un
número constante de pasos, que acabamos de dicir gran O de 1.
¿Que é un algoritmo que se en gran O de 1?
>> Audiencia: Atopar a lonxitude dunha variable.
>> DAVID Malan: Buscar o lonxitude dunha variable?
>> Audiencia: Non, a lonxitude se xa está clasificada.
>> DAVID Malan: Xenial.
OK, así que atopar a lonxitude de algo O longo de que algo, como
unha matriz, é almacenada algunha variable.
Porque pode só ler a variable, ou imprimir a variable, ou
xeralmente só acceder a esta variable.
E listo, que leva tempo constante.
>> Por outra banda, creo que volve a cero.
Debería na primeira semana de C, chamando só printf e impresión
algo na pantalla é sen dúbida constante de tempo, porque só leva
un certo número de ciclos de CPU para amosar que o texto na pantalla.
Ou esperar - non é?
De que outra forma poderiamos modelar o desempeño do printf?
Será que alguén quere desacordo, que quizais non sexa o tempo realmente constante?
En que sentido pode printf funciona tempo, en realidade, a impresión dunha corda
pantalla, ser algo agás constante.
>> Audiencia: [inaudível].
>> DAVID Malan: Yeah.
Por iso, depende da nosa perspectiva.
Se nós realmente creo que a entrada printf como a cadea, e
polo tanto, podemos medir o tamaño dese entrada pola súa lonxitude - entón imos chamarlle
que a lonxitude n, así como -
sen dúbida printf é a propia gran O de n porque vai levalo n pasos
para imprimir cada unha das n caracteres, probabelmente.
Polo menos na medida en que asumimos que quizais está usando un lazo for
debaixo do capó.
>> Pero teriamos que mirar para iso Código para entender mellor.
E, de feito, xa que vostedes empecen analizar os seus propios algoritmos, vai
literalmente facer exactamente isto.
Especie de globo ocular seu código e pensar sobre - todo ben, eu teño ese lazo
aquí ou eu teño lazos aniñados aquí, que vai facer n cousas n veces,
e pode clasificar de razón o seu camiño a través do código, aínda que sexa
pseudocódigo e non o código real.
>> Así que sobre omega de n ao cadrado?
O que era un algoritmo que no mellor caso, aínda levou n pasos cadrados?
Si?
>> Audiencia: [inaudível].
>> DAVID Malan: Entón selección especie.
Debido a este problema moi reducida ao feito de que unha vez máis, eu non sei
Eu atopei o actual máis pequena ata Eu chequei todos os elementos danado.
Así omega de, digamos, n, só veu con un.
Ordenación por inserción.
Se a lista pasa a ser clasificada xa, no mellor dos casos, só temos
para facer un paso a través dela, ao momento en que ten por seguro.
E, a continuación, que se pode dicir ser lineal, con certeza.
>> Que tal omega de 1?
O que, no mellor dos casos, pode levar un número constante de pasos?
Busca de xeito lineal, se só ter sorte eo elemento que está a buscar
é ao comezo da lista, se este é o lugar onde está comezando o seu
lineal transversal desta lista.
>> E iso é verdade dun serie de cousas.
Por exemplo, aínda binario investigación é omega de 1.
Porque se queda moi danado sorte e smack-DAB no medio
súa matriz é o número estás buscando?
Así, pode ter sorte alí, tamén.
>> Este, por último, omega de n log n.
Entón n log n, nós realmente non falar aínda, pero -
>> Audiencia: merge sort?
>> DAVID Malan: merge sort.
Ese foi o gancho da última vez, onde propuxemos, e nós amosamos
visual, que existen algoritmos.
E unha especie de só un deses fundir algoritmo que é fundamentalmente máis rápido
que algúns deses outros caras.
De feito, fundir curto é non só no mellor caso n log n, no peor
caso n log n.
E cando ten esa coincidencia de omega e grandes O ser a mesma cousa?
De feito, podemos describir isto como o que é chamado theta, aínda que sexa un
pouco menos común.
Pero iso significa só que os dous límites, neste caso, son as mesmas.
>> Entón, merge sort, o que iso realmente se resumen a para nós?
Ben, lembre a motivación.
Déixame sacar-se outra animación que non mirar por última vez.
Este, mesma idea, pero é un pouco máis grande.
E eu estou indo a ir adiante e apuntar primeiro - temos ordenación por inserción en
esquina superior esquerda, a continuación, a selección de clasificación, bubble sort, a par doutros tipos -
shell e rápidos - que non falamos aproximadamente, e heap e merge sort.
>> Así, polo menos, tratar de centrar os seus ollos en os tres principais da esquerda e logo
merge sort cando clic esta frecha verde.
Pero eu vou deixar todos eles executados, só para darlle un sentido da diversidade de
algoritmos que existen no mundo.
Vou deixar esta carreira por só uns segundos.
E se concentrar os seus ollos - seleccione un algoritmo, centrar-lo por só un
segundo - vai comezar a ver o estándar que é de execución.
>> Merge sort, previo aviso, está feito.
Heap especie, tipo rápido, shell -
así parece que introduciu a tres peores algoritmos a semana pasada.
Pero iso é bo que estamos aquí hoxe para mirar merge sort, que é un dos
o máis fácil é mirar, aínda aínda que probablemente ha dobrar túa mente
só un pouquiño.
Aquí podemos ver o que selección especie é unha merda.
>> Pero, por outra banda, é moi fácil de aplicar.
E quizais a I Set 3, que é un dos algoritmos que escolleu para aplicar
para a edición estándar.
Perfectamente ben, perfectamente correcto.
>> Pero, de novo, como n se fai grande, se decide aplicar un algoritmo máis rápido
como merge sort, as probabilidades son en grande e insumos maiores, o código é só
vai executar máis rápido.
O seu sitio vai funcionar mellor.
Os seus usuarios están indo a ser feliz.
E por iso hai estes efectos de que realmente dar
nos algún pensamento máis profundo.
>> Entón, imos dar un ollo ao que funden especie é realmente todo.
O legal é que a fusión tipo é só iso.
É dicir, unha vez máis, o que chamamos pseudocódigo, ser pseudocódigo
Inglés-como sintaxe.
E a simplicidade é especie de fascinante.
>> Entón, na entrada de n elementos - para que significa só que, aquí está un array.
Ten cousas n nel.
Isto é todo o que estamos dicindo aquí.
>> Se n é menor que 2, o regreso.
Entón, iso é só o caso trivial.
Se n é menor que 2, a continuación, é obviamente 1 ou 0, caso en que a cousa
xa está clasificado ou non existe, polo que só volver.
Non hai nada que facer.
Entón, iso é un caso sinxelo de arrincar fóra.
>> En caso contrario, temos tres etapas.
Ordenar a metade esquerda dos elementos, tipo a metade dereita dos elementos,
e logo mesturar as dúas metades ordenada.
O que é interesante aquí é que Eu son o tipo de punting, non?
Hai unha especie de definición circular para ese algoritmo.
En que sentido é este algoritmo circular definición?
>> Audiencia: [inaudível].
>> DAVID Malan: Si, o meu algoritmo de ordenación, dous dos seus pasos son "especie
algo. "E así que levanta a cuestión, ben, o que vou usar
para clasificar a metade esquerda ea metade dereita?
E a beleza aquí é que, a pesar de unha vez máis, esta é a alucinante
parte potencialmente, pode utilizar mesmo algoritmo para clasificar a metade esquerda.
>> Pero agarde un minuto.
Cando dixo para clasificar a metade esquerda, cales son os dous
pasos será o próximo?
Imos resolver a metade esquerda da media esquerda e á dereita
a metade da metade esquerda.
Caramba, como fago para clasificar os dous metades, ou en cuartos, agora?
>> Pero iso é OK.
Temos un algoritmo de clasificación aquí.
E aínda que se pode preocuparse en por primeira vez esta é unha especie de infinito
loop, é un ciclo que nunca vai acabar - que vai
acabar dunha vez o que pasa?
Xa que non é inferior a 2.
Que finalmente vai pasar, porque se continúa e reducir á metade
reducir á metade en reducir á metade destas metades, con certeza finalmente, vai acabar
con só 1 ou 0 elementos.
En que punto, este algoritmo di que está feito.
>> Polo tanto, a verdadeira maxia neste algoritmo parece estar en
ese paso final, a fusión.
Esta idea simple, só fusión de dous cousas, que é o que finalmente vai
que nos permiten clasificar unha matriz de, digamos, oito elementos.
Entón, eu teño oito bolas de estrés up aquí, oito anacos de papel, e unha
Google Glass -
que eu teño que manter.
>> [Risas]
>> DAVID Malan: Se puidésemos ter oito voluntarios, e imos ver se podemos
xogar iso, entón.
Guau, Aceptar.
Ciencia da computación está quedando divertido.
Todo ben.
Entón, que tal lle tres, maior man alí enriba.
Catro na parte de atrás.
E como a nós imos facer tres nesa liña?
E catro diante.
Entón oito, imos para arriba.
>> [Risas]
>> DAVID Malan: En realidade eu son Non sei o que é.
Son as bolas de estrés?
As lámpadas de mesa?
O material?
Internet?
>> Aceptar.
Entón imos para arriba.
Quen quere -
seguen aparecendo.
Imos ver.
E iso pon vostede no lugar -
está nunha situación.
Uh-oh, agarde un minuto.
1, 2, 3, 4, 5, 6, 7 - Oh, bo.
Todo ben, estamos ben.
Todo ben, entón todos teñen asento, pero non no vidro de Google.
Deixe-me facer cola estes anteriormente.
Cal é o seu nome?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Todo ben, comeza a ollar como o geek, se está todo OK.
Ben, eu tamén, supoño, só por un momento.
Todo ben, espera.
Estamos tentando chegar a un caso de uso a Google de vidro, e nós
penso que sería divertido facer só iso cando a xente está no escenario.
Imos gravar o mundo a partir da súa perspectiva.
Todo ben.
Non probablemente Google pretendía.
Todo ben, se non me importa de empregar tanto para os próximos minutos difíciles,
que sería marabilloso.
>> Todo ben, entón temos aquí un conxunto de elementos, e que a matriz, segundo a
anacos de papel nesas persoas ' mans, está actualmente sen clasificación.
>> MICHELLE: Oh, isto é tan estraño.
>> DAVID Malan: É practicamente aleatoria.
E, en só un momento, imos tratar para aplicar especie se funden
e ver onde ese insight clave.
E o truco aquí con merge sort é algo que non asumiron aínda.
Nós realmente necesita dalgún espazo adicional.
Entón, o que será especialmente interesante sobre iso é que estes
caras van moverse un pouco pouco, porque eu estou indo supor que
hai un conxunto extra de espazo, dicir, detrás deles.
>> Entón, se eles están detrás da súa cadeira, que é a matriz secundaria.
Se eles están sentados aquí, iso é a matriz primaria.
Pero este é un recurso que temos non aproveitados ata agora, coa burbulla
tipo, coa selección de tipo, coa ordenación por inserción.
Teña en conta que, a semana pasada, todo o mundo tipo de embaralhar no lugar.
Eles non usan calquera memoria adicional.
Fixemos espazo para a xente por movemento de persoas en todo.
>> Polo tanto, esta é unha visión de clave, tamén.
Hai ese trade-off, en xeral, en informática, de recursos.
Se quere acelerar algo como o tempo, vai
ten que pagar un prezo.
E un destes prezos é moitas veces espazo, a cantidade de memoria ou disco
espazo en disco que está a usar.
Ou, francamente, a cantidade programador de tempo.
Canto tempo lle leva, o ser humano, para realmente implementar un pouco máis
algoritmo complicado.
Pero, polo de hoxe, o trade-off é tempo e espazo.
>> Entón, se vostedes puidesen só soster o seu números para que poidamos ver que é
de feito correspondente 4, 2, 6, 1, 3, 7, 8.
Excelente.
Entón eu vou tentar orquestrar cousas, se vostedes poden só
seguir miña liderado aquí.
>> Entón, eu estou indo a aplicar, en primeiro lugar, o primeiro paso do pseudocódigo, que é
na entrada de n elementos, se non for inferior a 2, despois de volver.
Obviamente, que non fai aplica-se, polo tanto, seguir adiante.
Así clasificar a metade esquerda dos elementos.
Entón iso significa que eu vou centrar a miña atención por un momento sobre estes
catro caras aquí.
Todo ben, o que podo facer no próximo?
>> Audiencia: clasificar a metade esquerda.
>> DAVID Malan: Entón agora eu teño que clasificar a metade dereita destes caras.
Porque unha vez máis, asumir para si a obxectivo é clasificar a metade esquerda.
Como fai iso?
Só ten que seguir as instrucións, mesmo que estamos a facer iso de novo.
Así clasificar a metade esquerda.
Agora estou clasificando estas dúas caras.
O que vén a continuación?
>> Audiencia: clasificar a metade esquerda.
>> DAVID Malan: clasificar a metade esquerda.
Entón, agora estes, este lugar aquí, é unha lista de tamaño 1.
E cal é o seu nome?
>> PRINCESA Daisy: Princesa Daisy.
>> DAVID Malan: Princesa Daisy está aquí.
E así ela xa está clasificado porque a lista é de tamaño 1.
¿Que podo facer na seguinte?
OK, volver, porque esa lista é de tamaño 1, que é inferior a 2.
Entón cal é o seguinte paso?
E agora ten que tipo de volver atrás na súa mente.
>> Ordenar a metade dereita, o que é -
cal é o seu nome?
>> LINDA: Linda.
>> DAVID Malan: Linda.
E entón, o que facemos agora que temos unha lista de tamaño 1?
>> Audiencia: Return.
>> DAVID Malan: Coidado.
Volvemos primeiro, e agora o terceiro etapa - e se eu tipo de representa-lo por
asumindo os dous asentos agora, agora eu ten que xuntar estes dous elementos.
Entón, agora, por desgraza, os elementos están fóra de orde.
Pero é aí que o proceso de fusión comeza a ser atractivo.
>> Entón, se vostedes poderían erguer-se para só un momento, eu vou ter que vostede, nun
momento, para o paso detrás da súa cadeira.
E si Linda, porque é 2 menor que 4, polo que non
chega preto en primeiro lugar?
Quede aí.
Entón, Linda, que chega preto por primeira vez.
>> Agora, en realidade, se é só unha matriz poderiamos levala en tempo real
dende esta materia a este punto.
Entón, imaxine que tomou algunha constante un número de pasos.
E agora -
pero precisamos poñelas o primeiro lugar aquí.
>> E agora, se puidese vir por aí, así, imos
estar no lugar dous.
E aínda que este se sente como se fose tomando un tempo, o que é bo é agora
que a metade esquerda da metade esquerda agora está clasificada.
Entón, cal foi o seguinte paso, agora retroceder aínda máis na historia?
>> Audiencia: A metade dereita.
>> DAVID Malan: clasificar a metade dereita.
Entón, vós ten que facelo, tamén.
Entón, se pode erguer-se só por un momento?
E cal é o seu nome?
>> Jess: Jess.
>> DAVID Malan: Jess.
OK, entón Jess é agora a esquerda a metade da metade dereita.
E así é unha lista de tamaño 1.
Está claro clasificados.
E o seu nome?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle é, obviamente, unha lista de tamaño 1.
Ela xa está clasificada.
Entón, agora a maxia acontece, o proceso de fusión.
Entón, quen vai vir en primeiro lugar?
Obviamente, a Michelle.
Entón, se podería vir en torno de volta.
O espazo que temos dispoñible para ela agora está ben atrás nesta materia aquí.
E agora, se puidese volver, así como, temos agora, para ser claro, dous
metades, cada unha de tamaño 2 -
e só por mor da representación, se podería facer un pouco de espazo -
un deixou metade aquí, un metade aquí.
>> Retroceder aínda máis na historia.
Cal é o seguinte paso?
>> Audiencia: Unir.
>> DAVID Malan: Polo tanto, agora temos que mesturar.
Entón, OK, entón agora, por sorte, nos só liberou catro cadeiras.
Entón, usei o dobre da memoria, pero podemos dar flip-flop entre
dúas matrices.
Entón, cal é o número que vir primeiro?
Entón, Michelle, obviamente.
Entón, volve cara o seu lugar aquí.
E, a continuación, o número 2 é obviamente Logo, así que vir aquí.
Número 4, número 6.
E unha vez máis, aínda que non haxa unha pouco de andar implicado,
realmente, estas poderían ocorrer inmediatamente, , Movendo unha -
OK, así xogado.
>> [Risas]
>> DAVID Malan: E agora estamos en moi boa forma.
A metade esquerda da totalidade entrada xa foi resolto.
Todo ben, entón estes faces tiñan a vantaxe de que a miña -
como se rematar todas as nenas na á esquerda e todos os nenos do lado dereito?
>> OK, entón caras "virar agora.
Entón eu non vou levalo a través estes pasos.
A ver se podemos reaplicar mesmo pseudocódigo.
Se quere ir adiante e levantarse, e vós, déixeme darlle o micrófono.
Vexa se non pode replicar o que que fixemos aquí en
outro extremo da lista.
Quen precisa falar primeiro, baseado no algoritmo?
Entón explique o que está facendo antes de de facer calquera movementos do pé.
>> COLUMNA 1: Todo ben, entón desde Eu son a metade esquerda da
metade esquerda, eu volvo.
Non?
>> DAVID Malan: Xenial.
>> COLUMNA 1: E entón -
>> DAVID Malan: Quen fai o micrófono ir ao seguinte?
>> COLUMNA 1: número seguinte.
>> COLUMNA 2: Entón, eu son a metade dereita da metade esquerda do
metade esquerda, e eu atrás.
>> DAVID Malan: Xenial.
Atrás.
Entón, agora, cal é o próximo a vostedes dous?
>> COLUMNA 2: Queremos ver quen é máis pequeno.
>> DAVID Malan: Exactamente.
Queremos fundir.
O espazo que imos usar para fundir vostede, aínda que sexan
obviamente, xa clasificado, imos a continuación o mesmo algoritmo.
Entón, quen vai primeiro?
Entón, 3, e logo, 7.
E agora o micrófono vai para estes faces, OK?
>> COLUMNA 3: Entón, eu son a metade dereita do metade esquerda e meu n é inferior a
1, entón eu só vou pasar -
>> DAVID Malan: Xenial.
>> COLUMNA 4: Eu son a metade dereita do metade dereita do lado dereito, e eu son
tamén unha persoa, polo que estou vai volver.
Entón, agora que se funden.
>> COLUMNA 3: Entón imos voltar.
>> DAVID Malan: Entón vai para a parte de atrás.
Entón, 5 vai en primeiro lugar, a continuación, 8.
E agora público, que é o paso temos que volver agora
voltar en nosas mentes?
>> Audiencia: Unir.
>> DAVID Malan: Fusión media esquerda e dereita a metade da metade esquerda inicio.
Entón, agora -
e só para deixar isto claro, facer un pouco de espazo
entre vostedes dous.
Polo tanto, agora que é as dúas listas, esquerda e dereita.
Entón, como imos agora unirse a vostedes en a primeira fila de asentos de novo?
>> 3 vai por primeira vez.
Entón, 5, obviamente.
Logo, 7, e agora 8.
OK, e agora estamos?
>> Audiencia: Non fixo.
>> DAVID Malan: Non fixo, porque Obviamente, hai unha única etapa restante.
Pero, de novo, a razón que eu estou usando esta xerga como "retroceder na súa mente"
é por iso é realmente o que está pasando.
Estamos pasando por todas esas etapas, pero nós somos unha especie de pausa para un
momento, o mergullo máis profundo na algoritmo, parando por un momento,
mergullo máis fondo no algoritmo, e agora temos a sorte de retroceso na nosa
mentes e desfacer todas esas capas que temos unha especie de poñer en espera.
>> Polo tanto, agora temos dúas listas de tamaño 4.
Se vós puidesen erguer-se unha última vez e facer un pouco de espazo aquí para
facer claro que esta é a esquerda metade do orixinal, o
metade dereita do orixinal.
Quen é o primeiro número que cómpre tirar na parte de atrás?
Michelle, claro.
>> Entón poñemos Michelle aquí.
E quen ten o número 2?
Número 2 vén na parte de atrás tamén.
Número 3?
Excelente.
Número 4, número 5, número 6, o número 7, e o número 8.
>> OK, polo que parecía moi de pasos, con certeza.
Pero agora imos ver se non podemos confirmar tipo de intuitivamente que este
algoritmo fundamental, especialmente no que n queda moi grande, como xa vimos
coas animacións, é fundamentalmente máis rápido.
Entón, eu reivindico este algoritmo, no peor caso, e mesmo no mellor dos casos,
é grande de n log n veces.
É dicir, hai algún aspecto deste algoritmo que leva n pasos, pero
hai outro aspecto en algún lugar iteración, que Looping, que
leva log n pasos.
Podemos poñer o dedo sobre o que os dous números están referindo?
Ben, onde -
o micrófono para onde ir?
>> COLUMNA 1: Será que o rexistro n ser rompendo connosco en dous -
dividindo por dous, esencialmente.
>> DAVID Malan: Exactamente.
Cada vez que podemos ver en calquera algoritmo, polo tanto, agora, non foi ese patrón de
divisoria, dividindo, dividindo.
E é normalmente reducida a algo que é
logarítmica, base 2 log.
Pero realmente pode ser calquera cousa, pero log base 2.
>> Agora, o que dicir do n?
Podo ver que tipo de dividido ti homes - divididos ti, divididos ti,
divididos ti, divididos ti.
Onde é que o fin vén?
>> Polo tanto, é a fusión.
Porque pensar niso.
Cando mestura oito persoas en conxunto, en que a metade deles son un conxunto de catro
ea outra metade é outra conxunto de catro, como vai
sobre como facer a fusión?
Ben, vostedes fixeron iso moi intuitiva.
>> Pero se en vez fixen un pouco máis metodicamente, eu podería ter apuntado para
a persoa máis á esquerda por primeira vez coa miña esquerda man, sinalou a persoa máis á esquerda
de que a metade coa miña man dereita, e só posteriormente pasou pola
lista, apuntando a menor elemento cada vez, movendo o dedo sobre e
sobre cando sexa necesario ao longo da lista.
Pero o que é importante sobre esta fusión proceso é que eu estou comparando estes pares
de elementos.
A partir da metade da dereita e da esquerda metade, estou nunca xa retroceso.
>> Así, o propio merge está tomando non máis que n pasos.
E cantas veces eu tiven para facer que a fusión?
Ben, non máis que n, e nós só viu que, coa fusión final.
E por iso, se fai algo que leva rexistro veces n pasos n, ou viceversa,
que vai nos n log n veces dar.
>> E por que é mellor?
Ben, se xa coñecemos rexistro n é mellor que n - non?
Vimos en busca binaria, o libro de teléfono exemplo, log n foi definitivamente
mellor que o lineal.
Entón iso significa que n log n veces é sempre mellor que n veces outro
n, aka n ao cadrado.
E iso é o que finalmente se sente.
>> Tan grande salva de palmas, se puidésemos, para estes faces.
>> [Aplausos]
>> DAVID Malan: E os seus regalos de despedida - pode manter os números,
se desexa.
E o seu agasallo de despedida, como de costume.
Ah, e nós enviarémosche a metragem, Michelle.
Grazas.
Todo ben.
Sirva-se dunha pelota de estrés.
>> E déixeme puxar arriba, con todo, noso amigo Rob Bowden para ofrecer
perspectiva un pouco diferente deste, sempre que pode pensar sobre estes
etapas que acontecen en algo xeito diferente.
En realidade, o set-up para o que Rob está a piques para amosar asume que temos
feito a división do gran lista en oito pequenas listas,
cada un de tamaño 1.
>> Entón, nós estamos cambiando o pseudocódigo a pouco só a sorte de chegar ao
idea central de como a fusión obras.
Pero o tempo de funcionamento do que está a piques de facer aínda é
será o mesmo.
E, de novo, o set-up aquí é que é iniciado con oito listas de tamaño 1.
Entón perdeu a parte onde el é realmente fixo o rexistro n, n log, log n
división da entrada.
>> [REPRODUCIÓN]
>> -Iso é todo por un paso.
Para a segunda etapa, de xeito repetido pares de listas de mala directa.
>> DAVID Malan: Hm.
Só audio está chegando fóra do meu ordenador.
Imos tentar iso de novo.
>> -Just arbitrariamente escoller cal - agora temos catro listas.
Saber antes.
>> DAVID Malan: Alí imos nós.
>> Mesclando-108 e 15, terminais coa lista de 15, 108.
Fundir 50 e 4, temos acabar con 4, 50.
Mesclando 8 e 42, que acabar con 8, 42.
E fusión 23 e 16, nos acabar con 16, 23.
>> Agora todas as nosas listas son de tamaño 2.
Observe-se que cada un dos catro listas é clasificado.
Así, podemos comezar a fundirse pares de listas de novo.
Mesclando 15 e 108 e 4 e 50, que tire primeiro a 4, logo a 15, logo
a 50, logo a 108.
Mesclando 8, 42 e 16, 23, primeiro tomar a 8, a continuación, a 16, logo a 23,
logo a 42.
>> Polo tanto, agora temos só dúas listas de tamaño 4, cada un dos cales é clasificado.
Entón, agora nós mesturar estas dúas listas.
En primeiro lugar, tomamos a 4, despois tomamos o 8, así que tomamos o 15, entón con 16 anos, logo
23, despois 42, despois 50, despois 108.
>> [FIN reprodución de vídeo]
>> DAVID Malan: Unha vez máis, o aviso previo, nunca tocado un determinado vaso máis do que xa
tras avanzar alén dela.
Así, el nunca repetir.
Polo que sempre está movendo cara ao lado, e é aí onde temos o noso n.
>> Por que non deixar me puxar arriba unha animación que vimos anteriormente, pero esta vez
incidir só sobre merge sort.
Déixeme ir adiante e facer zoom en nesta aquí.
Primeiro déixeme escoller unha entrada aleatoria, ampliar iso, e pode clasificar de ver
o que nós tomamos para concedida, anteriormente, merge sort está realmente facendo.
>> Entón, teña en conta que obter esas metades ou estes cuartos ou estes oitavos de
problema que, de súpeto, comezar a tomar boa forma.
E entón, finalmente, ve a o fin que Bam,
todo é mezclado xuntos.
>> Entón, estas son só tres diferentes asume a mesma idea.
Pero o insight clave, así como dividir e conquistar na primeira clase,
foi que decidimos dividir dalgún xeito o problema en algo grande, en
algo tipo de idéntico en espírito, pero máis pequenos e pequenas
e menores.
>> Agora outra forma divertida de clasificar de pensar sobre estes, a pesar de que non é
vai darlle o mesmo intuitiva entendemento, é
a seguinte animación.
Polo tanto, este é un vídeo de alguén xuntos que asociado distinto
sons coas varias operacións para ordenación por inserción, por merge sort, e
por un par de outros.
Entón, nun momento, eu vou bater Play.
Trátase de un minuto de duración.
E aínda que aínda pode ver a patróns pasando, neste momento pode
tamén escoitar como estes algoritmos son realizar de xeito diferente e con
un pouco diferentes patróns.
>> Esta é a ordenación por inserción.
>> [Tons XOGO]
>> DAVID Malan: El novo está intentando para introducir cada elemento
para onde ela pertence.
Este é bubble sort.
>> [Tons XOGO]
>> DAVID Malan: E pode clasificar de sensación como relativamente pouco traballo que está a facer
en cada paso.
Isto é o aburrimento parece.
>> [Tons XOGO]
>> DAVID Malan: Esta é a selección de tipo, onde se selecciona o elemento que queremos por
pasando por unha e outra vez e outra vez e poñelas no inicio.
>> [Tons XOGO]
>> DAVID Malan: Este é o merge sort, que realmente pode comezar a sentir-se.
>> [Tons XOGO]
>> [Risas]
>> DAVID Malan: Algo chamado gnome tipo, que non mirei.
>> [Tons XOGO]
>> DAVID Malan: Entón déixeme ver, agora, distraído como espera, segundo a
música, se podo escorregar algo pouco de matemáticas aquí.
Polo tanto, hai unha cuarta forma que pudermos pensar sobre o que quere dicir que estes
funcións para ser máis rápido que os que xa vimos antes.
E se está a benvida para o curso de un fondo de matemáticas,
realmente sabe, se cadra, xa que pode bater un termo sobre esta técnica -
ou sexa, a recursividade, unha función que dalgún xeito se autodenomina.
>> E unha vez máis, recordar que merge sort pseudocódigo foi recursivo no sentido
que unha das etapas do merge sort foi chamar especie -
que é, en si.
Pero, por sorte, xa mantivemos chamando tipo, ou merge sort,
En concreto, nunha menor e menor e unha lista pequena, finalmente
ao fondo do pozo grazas ao que chamaremos un caso base, o caso hard-Coded que
dixo que se a lista é pequena, menos de 2 Neste caso, só tes que volver inmediatamente.
Se non tivésemos ese caso especial, a algoritmo sería nunca inferior para fóra,
e realmente entrar nun loop infinito verdadeiramente para sempre.
>> Pero supoñamos que queremos agora poñer algúns números no presente, de novo, utilizando n
medida que o tamaño da entrada.
E eu quería preguntar, o que é o tempo total involucrado
execución merge sort?
Ou, máis xeralmente, o que é o custo do mesmo no tempo?
>> Ben, é moi fácil de medir isto.
Se n é menor que 2, o tempo envolto na clasificación de n elementos,
onde n é 2, é 0.
Porque só retornar.
Non hai traballo a ser feito.
Agora, sen dúbida, é posible que un paso ou dous pasos para descubrir a cantidade de
traballar, pero é preto o suficiente para que 0 Eu só vou dicir que non traballo é
necesario se a lista é tan pequena para ser desinteressante.
>> Pero, neste caso, é interesante.
O caso recursivo foi o sector de o pseudocódigo que dixo outra cousa, tipo
a metade esquerda, clasificar o dereito metade, unir as dúas metades.
Agora, por que esta expresión representar esa gasto?
Ben, T de n significa só que o tempo para ordenar n elementos.
E, a continuación, no lado dereito da signo igual alí, o T de n dividido
por 2 refírese ao custo de que?
Clasificando a metade esquerda.
O outro T de n dividido por 2 é presuntamente, referíndose ao custo
clasificar a metade dereita.
>> E entón o máis n?
É a fusión.
Porque se ten dúas listas, unha de tamaño n superior a 2 e outra de tamaño n
máis de 2, ten que tocar esencialmente cada un destes elementos, así como Rob
tocou cada un dos vasos, e só como se sinalou para cada un dos
voluntarios no escenario.
Así, n é á custa de fusión.
>> Agora, desgraciadamente, esta fórmula é tamén propio recursiva.
Así se fixo a pregunta, se non é, digamos, 16, se hai 16 persoas no escenario
ou 16 cuncas no vídeo, cantos total de pasos que é necesario para clasificalos los
con merge sort?
En realidade non é unha resposta obvia, porque agora ten a sorte de
recursivamente responder a esta fórmula.
>> Pero todo ben, porque déixeme propoñer que faga o seguinte.
O tempo implicado para clasificar ou 16 persoas 16 cuncas será representado
xeralmente como T de 16.
Pero o que é igual a, segundo o noso fórmula anterior, dúas veces a cantidade
de tempo que leva para clasificar 8 vasos máis 16.
E, de novo, máis 16 é o momento de fusión, E as dúas veces T de 8 é o
tempo para resolver a metade esquerda e metade dereita.
>> Pero, de novo, iso non é suficiente.
Temos que mergullar máis fondo.
Isto significa que temos que responder á pregunta, o que é T de 8?
Ben T de 8 está só a 2 t de 4 veces máis de 8.
Ben, o que é T de 4?
T de 4 está a só 2 veces T de 2 + 4.
Ben, o que é T de 2?
T de 2 é só 2 veces T de 1 máis 2.
>> E, de novo, somos o tipo de conseguir preso neste ciclo.
Pero iso está a piques de bater ese o chamado caso base.
Porque o que é T 1, non podemos reclamar?
0.
Entón, agora, por fin, podemos traballar para tras.
>> Se T 1 é 0, agora podo volver a subir un aliñar con este cara aquí, e podo
Póñase 0 para T de 1.
Entón, iso significa que é igual a 2 veces a cero, tamén coñecido como 0, acrescido de 2.
E, de xeito que toda a expresión é 2.
>> Agora, se eu incorporarse o T de 2, cuxa resposta é 2, liga-lo na liña do medio, T
de 4, que me dá dúas veces 2 + 4, de modo 8.
Agora ben, se eu conectar 8 a anterior liña, que me dá dúas veces 8, 16.
E se, a continuación, continuar co que 24, engadindo o 16 de finalmente obter un
valor de 64.
>> Agora que en si mesmo tipo de fala nada para a notación n, o
O gran, o omega que temos falando.
Pero verifícase que 64 é de feito 16, o tamaño da entrada,
rexistro base 2, de 16.
E se isto é un pouco raro, só creo que volta, e el vai volver
para que eventualmente.
Se este é o rexistro base 2, é como 2 elevado para o que lle dá 16?
Oh, iso é 4, polo que é 16 veces 4.
>> E unha vez máis, non é un gran negocio se este é unha especie de memoria nebulosa agora.
Pero, polo de agora, asumir a fe que 16 log 16 é 64.
E así, de feito, con esta sinxela sanidade comprobar, temos confirmada -
pero non demostrou formalmente -
que o tempo de execución de fusión especie é realmente n log n.
>> Entón, non é malo.
É sempre mellor que o algoritmos que vimos ata agora, e
é porque temos panca, un, unha técnica chamada de recursão.
Pero o máis interesante do que iso, que noción de dividir e conquistar.
Unha vez máis, verdadeiramente semana 0 cousas que ata agora é recorrente en
forma máis convincente.
>> Agora, un pouco de exercicio divertido, se ten nunca fixen iso - e probablemente
non tería porque tipo do normal a xente non pensa para facelo.
Pero se eu for a google.com e se Quero aprender algo sobre
recursão, Intro.
>> [Risas]
[Máis risas]
DAVID Malan: Bad broma estendendo lentamente.
[Risas]
DAVID Malan: Só no caso, el está alí.
Non deletrear mal, e hai a broma.
Todo ben.
Explique-os persoas próximas a vostede se el non ten moito premendo aínda.
Pero recursão, de xeito máis xeral, refírese a para o proceso de unha función de chamadas
si só, ou, máis xeralmente, a división dun problema en algo que se pode
resoltos aos poucos, resolvendo o mesmo problemas de representación.
>> Ben, imos engrenaxes de cambio só por un momento.
Gústanos de rematar en certos cliffhangers, entón imos comezar a definir
a fase, durante varios minutos, nunha idea moi simple -
que o intercambio de dous elementos, non?
Todos estes algoritmos que estivemos falando sobre o último par de
conferencias implica algún tipo de cambio.
Hoxe foi vistos por eles recibido -Se das súas materias e
camiñando por aí, pero o código, fariamos pode ter un elemento dunha matriz
e plop-lo noutro.
>> Entón, como imos facelo?
Ben, deixe-me ir adiante e escribir un programa rápido aquí.
Eu estou indo a ir adiante e facer isto como a continuación.
Imos chamar iso -
o que queremos chamar este?
>> En realidade, non.
Déixeme volver atrás.
Non quero facelo suspense aínda.
Vai romper a diversión.
Imos facelo no seu lugar.
>> Supoñamos que quero escribir un pouco programa e que agora abraza este
idea de recursão.
Eu medio que teño diante de min alí.
Vou facer o seguinte.
>> En primeiro lugar, un rápido inclúen estándar de io.h, , Así como unha inclusión cs50.h.
E entón eu estou indo a ir adiante e declarar int void main
do xeito habitual.
Podo entender que eu teño chamado erroneamente o ficheiro, así déixeme engadir unha extensión c. aquí para
que podemos recompila-lo correctamente.
Comeza esta función.
>> E a función que quero escribir, moito simplemente, é o que fai a
usuario a un número e, a continuación, engade-se todos os números entre ese
número e, por exemplo, 0.
Entón, primeiro eu vou seguir adiante e declarar int n.
Entón eu copiar un código que usamos por un tempo.
Mentres algo é certo.
Eu vou volver a iso nun momento.
>> O que quero facer?
Quero dicir printf positivo enteiro por favor.
E entón eu vou din que non recibe obter int.
Entón, de novo, algún código cliché que usei antes.
E eu vou facer iso mentres n sexa menor que 1.
Así, isto pode asegurar que o usuario dáme un enteiro positivo.
>> E agora eu vou facer o seguinte.
Quero sumar todos os números e entre 1 e n, ou 0 e n,
equivalentemente, para obter a suma total.
Así, o símbolo gran sigma que pode lembrar.
Entón, eu vou facelo por primeira convocatoria unha función chamada Sigma,
pasalo en n, e entón eu vou printf dicir, a resposta está logo alí.
>> Así, en breve, eu recibín e int do usuario.
I garantir que é positivo.
Eu declaro unha variable chamada resposta de tipo int e almacenar no que o retorno
valor de Sigma, pasando n como entrada.
E entón eu imprimir esa resposta.
>> Por desgraza, aínda sigma soa como algo que pode estar en
o ficheiro math.h, a súa declaración, iso non é certo.
Entón, iso é OK.
Podo aplicar iso mesmo.
Vou aplicar unha función chamada sigma, e iso vai levar un
parámetro -
imos chamalo m, só polo que é diferente.
E, a continuación, ata aquí, eu vou dicir, así, se m é menor que 1 - Este é un
programa moi desinteressante.
Entón, eu estou indo a ir adiante e inmediatamente devolver 0.
El simplemente non ten sentido sumar todos os números entre 1 e n se m
0 é el mesmo ou negativo.
>> E entón eu estou indo a ir adiante e facelo moi iterativa.
Vou facer este tipo de old-school, e eu estou indo a ir adiante
e dicir que eu vou declarar unha cantidade a ser 0.
Entón eu vou ter un loop de int -
e deixe-me facelo para coincidir co noso Código de distribución, para que teña unha copia
na casa. int i recibe 1 en ata i é inferior ou igual a m.
i plus plus.
E, a continuación, dentro deste loop -
estamos case alí -
suma queda suma máis 1.
E entón eu vou volver a suma.
>> Entón eu fixen iso axiña, reconhecidamente bastante.
Pero, de novo, a principal función é moi simple, baseado no código temos
escrito ata agora.
Utiliza o loop dobre para obter unha positiva int do usuario.
Eu, entón, pasar esa int a unha nova función chamado Sigma, chamando-o, unha vez máis, n.
E eu almacenar o valor de retorno, a resposta da caixa negra actualmente
coñecido como Sigma, nunha variable chamada de resposta.
Entón eu imprimir lo.
>> Se agora continuar a historia, como Sigma aplicado?
Propoño para aplicar o seguinte.
En primeiro lugar, un pouco de verificación de erros para asegurarse de que o usuario non é
xogar comigo e pasando algún valor negativo ou 0.
Así que declarar unha variable chamada En resumo e configuralo para 0.
>> E agora eu comezo a pasar de i é igual a 1 todo o camiño ata e incluíndo m,
porque quero incluír todos os números de un a m, incluso.
E dentro deste loop for, eu só fago suma recibe o que é agora, máis
valor de i.
Ademais, o valor de i.
>> Como un aparte, se non vin isto antes, hai un pouco de azucre sintático
para esta liña.
Podo ter que volver escribir isto como máis iguais i, só para me salvar algunhas teclas
e mirar un pouco máis frío.
Pero iso é todo.
É funcionalmente o mesmo.
>> Desafortunadamente, este código de non vai compilar aínda.
Se eu executar o make sigma 0, como son I será chamado?
O que está indo a non gustar?
>> Audiencia: [inaudível].
>> DAVID Malan: Si, eu non declarar a función encima, non?
C é unha especie de estúpida, só na medida en que fai o que diga a el para facer, e
ten que facelo nesa orde.
E entón se eu prema Intro aquí, eu vou recibir un aviso sobre sigma implícita
declaración.
>> Oh, non é un problema.
Eu podo ir ata o cumio, e podo dicir, todo ben, agarde un minuto.
Sigma é unha función que devolve un int e espera un
int como entrada, punto e coma.
Ou eu podería poñer toda a función anterior principal, mais en xeral, eu
Recomendo contra iso, porque é bo ter sempre inicio na parte superior de xeito
pode mergullo na dereita e sabe o que é un programa está facendo lendo principal por primeira vez.
>> Entón, agora déixeme limpar a pantalla.
Remake sigma 0.
Todo parece check-out.
Déixeme executar sigma 0.
Entre positiva.
Vou darlle o número 3 para mantelo simple.
De xeito que debería darme 3 máis 2 máis 1, entón 6.
Enter, e de feito eu fico 6.
>> Podo facer algo grande -
50, 12, 75.
Así como a tanxente, eu vou facer algo ridículo como realmente un gran
número, Oh, que realmente funciona -
eh, eu non creo que iso é certo.
Imos ver.
Imos realmente xogar con el.
>> Isto é un problema.
Que está pasando?
O código non é tan malo así.
Aínda é lineal.
Asubiar é un bo efecto, a pesar de todo.
Que está pasando?
>> Non estou seguro se oín-lo.
Así, verifica-se - e é dicir como un aparte.
Isto non é esencial para o idea de recursão.
Acontece que, por que eu estou tratando de representan un número tan grande, a maioría
Probablemente está a ser mal interpretado por C, como un número non positivo,
pero número negativo.
>> Nós non falamos sobre iso, pero Acontece que hai números negativos
no mundo máis aló a números positivos.
E os medios polos que se pode representar un número negativo
esencialmente é, pode utilizar un bit especial para indicar
positivo sobre negativo.
É un pouco máis complexo do que iso, pero esa é a idea básica.
>> Entón, por desgraza, se C é confuso unha deses bits como de feito o que significa,
Oh, este é un número negativo, o meu lazo aquí, por exemplo, é, en realidade nunca
vai rematar.
Entón, se eu fose realmente a impresión de algo novo e de novo, fariamos
ver moita cousa.
Pero, de novo, iso é cousa do punto.
Isto é realmente só unha especie de curiosidade intelectual que nós viremos
voltar eventualmente.
Pero, por agora, esta é a correcta implantación se asumirmos que o
usuario pode fornecer ints que se encaixan dentro ints.
>> Pero eu afirmo que este código, a verdade, podería facerse moito máis simple.
O obxectivo en cuestión é ter un número como m e sumar todos os
números entre el e 1, ou, inversamente entre 1 e el, eu afirmo
que podo pedir esa idea de que funden especie tiña, que estaba tomando un problema
deste tamaño e dividíndose o en algo máis pequeno.
Quizais nin a metade, pero menor, pero representativamente o mesmo.
A mesma idea, pero un problema menor.
>> Entón, eu estou en realidade - déixeme salve este ficheiro cun número de versión diferente.
Imos chamar esta versión 1 no canto de 0.
E eu afirmo que eu poida realmente reimplementar esta neste tipo de
alucinante camiño.
>> Vou deixar parte dela só.
Vou dicir se m é menor que ou mesmo igual a 0 -
Eu só vou ser un pouco esta vez máis anal
coa miña comprobación de erros -
Eu estou indo a ir adiante e voltar 0.
Este é arbitraria.
Estou simplemente decidir se o usuario dáme un número negativo, eu son
retornando 0, e eles deben ler a documentación máis de preto.
>> Else -
entender o que eu vou facer.
Máis eu vou volver m plus -
o que é de sigma m?
Ben, sigma de m máis m menos 1, m menos dous, ademais de menos de 3 m.
Non quero escribir todo isto para fóra.
Por que non só punto?
Recursively me chamar con algo problema menor, punto e coma,
e chamalo un día?
>> Non?
Agora, aquí, tamén, que pode sentir ou preocuparse que este é un loop infinito que eu son
inducindo, polo cal estou aplicando sigma chamando Sigma.
Pero iso é perfectamente normal, porque eu pensou en fronte unha agregou que falas?
>> Audiencia: [inaudível].
>> DAVID Malan: 23 a 26, que é o meu caso condición.
Porque o que é bo sobre o subtracción aquí, porque eu teño
entregando sigma problemas menores, menor problemas menores - non é
a metade do tamaño.
É só un pequeno paso máis pequeno, pero iso é OK.
Porque, finalmente, imos traballar noso camiño ata a 1 ou 0.
E xa que se loita 0, Sigma non é vai chamar-se máis.
Devolverá inmediatamente 0.
>> Así, o efecto, se este tipo de vento na súa mente, é engadir máis m
menos 1 m, máis M menos 2, máis M menos 3, ademais de punto, punto, punto, m menos
m, acabou dándolle 0, eo efecto é en definitiva, para engadir todos
esas cousas xuntas.
Entón, nós non temos, co recursão, resolveu o problema que
non podería resolver antes.
Efectivamente, esta versión de 0, e todo problema ata a data, foi resoltas
con só usando loops ou mentres loops ou construcións semellantes.
>> Pero recursão, atrévome a dicir, ofrécenos unha forma diferente de pensar
problemas, na que se pode tomar un problema, división lo de algo
un tanto grande para algo un tanto máis pequeno, eu afirmo que podemos resolver-lo
quizais un pouco máis elegante en termos do deseño, con menos código,
e quizais mesmo resolver problemas que ser máis difícil, a medida que vai finalmente
ver, a solución puramente iterativa.
>> Pero o suspense que fixen quero deixar-nos o foi tanto.
Déixeme ir adiante e abrir un arquivo dende -
De feito, déixeme ir e facelo moi rápido.
Déixeme ir adiante e propoñer a continuación.
Entre o código de hoxe é esta imaxe aquí.
Este aquí, noswap.
>> Polo tanto, este é un pequeno programa estúpido que Eu chicoteado ata que as demandas a facer
a continuación.
Na principal, declara por primeira vez un int chamada xe atribúe a el
o valor de 1.
A continuación, el declara un int y e atribúe o valor 2.
A continuación, el amosa o que x e y é.
A continuación, el di, troco, dot dot dot.
>> A continuación, el di ser chamado dunha función chamado intercambio, pasando en xe
y, a idea de que é o que esperamos x e y volverá
diferente, o contrario.
A continuación, el trocou reclamar!
cun signo de admiración.
A continuación, el imprime xe y.
>> Pero resulta que esa mesma demostración simple abaixo
aquí é realmente buggy.
Aínda que eu estou declarando unha temporal variable e, temporalmente, poñendo un en
, Entón eu estou reafectação un valor de b -
que se sente razoable, porque eu teño salva unha copia dun de temperatura.
Entón eu actualizar b a igual o que estaba na temperatura.
Este tipo de xogo shell de mover un en b eb nun empregando esta
medio-home chamado temperatura sente perfectamente razoable.
>> Pero eu afirmo que cando executar este código, como eu vou facer agora -
déixeme ir adiante e pegalo aquí.
Vou chamar esta noswap.c.
E, como o nome suxire, este non é Será un programa correcto.
Fai noswap. / Con intercambio.
x é 1, y é 2, troco, trocados.
x é 1, y é 2.
É fundamentalmente mal, aínda aínda que isto parece perfectamente
razoable para min.
E hai unha razón, pero non estamos vai revelar a razón aínda.
>> De momento, a segunda suspense que eu quería para deixar con iso, un
anuncio das sortes sobre os códigos de cupón.
A nosa innovación con días de atraso este ano provocou un número non-trivial
de preguntas, o que se non a nosa intención.
A intención destes códigos de cupón, en que, se fai parte do problema
establecer cedo, obtendo así un día extra, Foi realmente para axudar vostedes axudan
se comezar cedo, tipo de por animar ti.
Nos axuda a distribuír a carga en toda o horario de oficina, para que mellor
é unha especie de gaña-gañou.
>> Desafortunadamente, creo que as miñas instrucións non ser, ata a data, moi clara, de xeito
Volvín esta semana e actualizada especificación no máis grande, máis ousado texto para
explicar balas como estas.
E só para dicir iso máis publicamente, por estándar, conxuntos de problemas son debidos xoves
ao mediodía, segundo o programa.
Se comezar cedo, terminando en parte o problema de definir ata o mércores ás 12:00
PM, a parte que se relaciona cun cupón código, a idea é que pode estenderse
O prazo para a P definido ata o venres.
Ou sexa, pouco fóra unha pequena parte do P definida en relación ao que normalmente é o
maior problema, e compra se un día extra.
Unha vez máis, queda pensar o conxunto de problemas, fai que
o expediente máis cedo.
Pero o problema aínda é o código de cupón obrigados, mesmo se non envialo.
>> Pero o máis convincente é este.
(Sussurro) E esas persoas deixando pronto van arrepentir.
Como son as persoas na terraza.
Pido desculpas por adiantado para as persoas en a terraza, por razóns que serán
claro en só un momento.
>> Entón, temos a sorte de ter un dos Ex xefe compañeiros de ensino do CS50 en
unha empresa chamada dropbox.com.
Teñen moi xenerosamente doou un código de cupón aquí para iso moito espazo,
que é a partir do usuais 2 gigabytes.
Entón o que eu penso que estaba a facer nesta nota final é facer un pouco de unha oferta,
polo cal, en só un momento, imos revelar o gañador e que ten un cupón
código que pode, entón, ir ao seu sitio web, escriba-a, e listo, obter un
moito máis espazo para a súa Dropbox aparello e para os seus arquivos persoais.
>> E en primeiro lugar, que quere participar neste deseño?
OK, agora que o fai aínda máis divertido.
A persoa que recibe este 25 gigabytes código de cupón - o que está lonxe
máis atractivo do que o falecido días de hoxe, se cadra -
é aquel que está sentado enriba dun asento do banco baixo a cal existe
que o código do cupón.
Agora podes ollar por baixo seu asento.
>> [REPRODUCIÓN]
>> -Un, dous, tres.
>> [Gritando]
>> -Vostede gañou un coche!
Vostede gañou un coche!
>> DAVID Malan: Veremos vostede na Mércores.
>> -Vostede gañou un coche!
Vostede gañou un coche!
>> DAVID Malan: persoas Terraza, veñen aquí abaixo para adiante,
onde temos extras.
>> -Todo o mundo ten un coche!
Todo o mundo queda un coche!
>> [FIN reprodución de vídeo]
>> Narrador: Na seguinte CS50 -
>> COLUMNA 5: Oh meu Deus caramba caramba caramba caramba caramba caramba caramba caramba caramba -
>> [XOGOS ukelele]