>> [Música tocando]
>> David J. Malan: Este é CS50.
E este é o inicio da semana tres.
Entón, nós temos unha morea de emocionante cousas para cubrir hoxe.
Unha morea de oportunidades para voluntarios enriba do escenario.
E, finalmente, é hoxe non sobre o código en todo.
Pero é sobre ideas e trátase de algoritmos,
e, de feito, traendo de volta algúns dos as leccións aprendidas a partir da semana cero,
onde recall, nós introduciu esta monstruosidade.
E préstamos inspiración sempre que, para comezar
para resolver cada vez máis sofisticados problemas mediante algoritmos.
Pero, primeiro, un par de anuncios.
Entón un, se quere unirse Funcionarios e compañeiros de CS50 no xantar
este venres, tanto aquí como no Cambridge, e en New Haven,
por favor visita o curso de web, no que un URL se pode atopar.
Charla este mércores non estar aquí en Sanders.
Será en liña, de xeito sintonizar na web da CS50,
aquí en Cambridge ou New Haven tamén.
>> E, a continuación, axustar dous problema xa está nas súas mans.
Se aínda non dicir aínda, permítame para ofrecer a suxestión de palabras fortes
que, sobre todo agora, como o problema define anticipadamente,
realmente quere comezar agora, se non borrifar un pouco a fin de semana ou antes
cando por primeira vez saír Venres, porque vai
descubrir que eles non son necesariamente quedando máis longos ou máis reto por
SE.
Eu creo que vai descubrir que, en xeral, tenden a levar máis ou menos
en torno mesma cantidade de tempo.
Pero é certamente depende no alumno, e
depende da mentalidade co que se achega a el.
Pero, invariablemente, está indo para realizar-se contra algunha parede,
e está indo bater algún erro, e que é só
non vai ser capaz de superar isto nalgún momento.
E é moi valiosa para poder afastarse, volver ao día seguinte,
ir ao horario de oficina, no post CS50 Discutir ou similar, para comezar realmente desbloqueado.
Polo tanto, manter isto presente.
Comezando canto antes é o mellor que podes facer.
Entón, aquí é onde comezan a clase, máis a semana cero.
E podemos obter un voluntario aquí para me axudar a atopar micrófonos?
Aceptar.
Levantando-se xa.
Imos cara arriba.
Creo que é como vai funcionar.
Cal é o teu nome?
ALAN ESTRADA: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Imos cara arriba.
Encantado de coñecerte.
ALAN ESTRADA: Pracer en coñece-lo.
DAVID J. Malan: E estaba aquí coa xente a semana cero, por suposto.
ALAN ESTRADA: eu era.
Eu era.
>> DAVID J. Malan: Entón podería ir adiante e atopar a nós Mike Smith,
tan rápido como pode?
Tan rápido como se poida.
Literalmente rasgando o problema en metade do que precisa.
>> ALAN ESTRADA: Hum.
DAVID J. Malan: Literalmente rasgando o problema á metade.
>> ALAN ESTRADA: Oh.
Mm.
Moi bo.
>> DAVID J. Malan: Aceptar.
Bo.
Grazas.
ALAN ESTRADA: Moi bo.
Aceptar.
>> DAVID J. Malan: E agora, vostede whittled abaixo
a metade do tamaño do problema.
Agora, estamos reducidos a un cuarto.
Está pagando a atención sobre de que lado estamos mantendo?
>> [Risas]
>> ALAN ESTRADA: Si, eu penso--
>> DAVID J. Malan: Cal sección estamos?
ALAN ESTRADA: silenciosa, entón.
>> DAVID J. Malan: Aceptar.
Pero Mike Smith vai para ser logo silenciosa.
Assim--
>> [Risas]
>> Todo ben.
ALAN ESTRADA: Onde estamos buscando?
DAVID J. Malan: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Malan: Agora estamos en cirúrxico.
Agora, os médicos.
Agora--
>> ALAN ESTRADA: Let's- imos con real.
Real.
>> DAVID J. Malan: Real.
Aceptar.
Se precisa de Real.
Agora, o camiño que é Mike Smith?
>> ALAN ESTRADA: Desta forma.
>> DAVID J. Malan: Que xeito?
ALAN ESTRADA: Espera.
M é-- non?
Comezamos com--
>> DAVID J. Malan: Yeah.
Son deixados.
Seu dereito.
>> ALAN ESTRADA: Yeah.
>> DAVID J. Malan: Entón Mike está aquí.
ALAN ESTRADA: O que?
>> [Risas]
>> Mal exemplo, rapaces.
Desculpe.
DAVID J. Malan: Isto vai ensinar saltar para fóra da súa cadeira.
>> ALAN ESTRADA: Oh.
Oh.
Teño ti.
Oh.
Isto é-- OK, eu teño ti.
Smith aquí?
>> DAVID J. Malan: Smith, grazas.
Polo tanto, vou seguir mirando cara arriba Smith?
>> ALAN ESTRADA: Ah, si.
Non, non, non.
Oh, non.
Iso é o meu.
>> DAVID J. Malan: Oh, ten Smith.
Aceptar.
>> ALAN ESTRADA: Si, eu Smith ten aquí.
Sentímolo, persoal.
Eu penso que nós Michael-- Michael busca.
Desculpe.
>> DAVID J. Malan: É Aceptar.
Todo ben, agora estamos en Paccini e Sons.
>> ALAN ESTRADA: Paccini e fillos.
DAVID J. Malan: Só e eu estamos en sobre este asunto.
Aceptar.
Atopar-nos Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. Malan: Smith.
Estamos en R para lixo.
ALAN ESTRADA: Mala.
Oh.
Isto vai levar un pouco.
>> [Risas]
DAVID J. Malan: Shoes.
Estamos en zapatos.
>> ALAN ESTRADA: Agora estamos gonna--
>> DAVID J. Malan: Nice.
ALAN ESTRADA: Which--
[Risas]
Oh, iso é gran.
[Risas]
>> DAVID J. Malan: É Aceptar.
>> ALAN ESTRADA: Oh, iso é bo.
Eu non creo que eu vou ter amigos PSAT tras este.
DAVID J. Malan: Good.
Sporting.
ALAN ESTRADA: Sporting.
Hum, L, M, N, O, P.
DAVID J. Malan: Aceptar.
Entón, imos destruír o ao medio.
Está ben.
Iso acaba mal de ningún xeito, porque Mike Smith non será nas páxinas amarelas.
>> ALAN ESTRADA: Aw.
>> DAVID J. Malan: Non, é OK.
Pero imos finxir que está nesta páxina.
Entón, agora, tallou o problema abaixo a unha páxina, e atopamos Mike Smith.
>> [Cheering]
Vale grazas.
Aceptar.
Iso foi extraordinario.
Pero aínda era máis rápido que busca lineal,
en que comezan no inicio do libro,
e pasamos o noso camiño de esquerda a dereita, finalmente, á procura de Mike Smith.
E así, o libro de teléfono tiña quizais 1.000 páxinas,
quizais levaría nos 10 ou máis bágoas páxina.
>> Pero pode que panca tocou unha suposición
durante toda a iso, o que é dicir que o libro de teléfono con antelación o que era?
Audiencia: Ordenado.
DAVID J. Malan: É clasificada.
Non?
É clasificados en orde alfabética, por iso, que todos eses nomes e números
son clasificadas a partir da de un para o Z de, e en orde alfabética no medio.
Pero hoxe, nós agora pedir a cuestión, ben,
como fixo Verizon ou o teléfono empresa obtelo naquel estado?
>> Porque é unha cousa para alavancar esa suposición, e, polo tanto,
resolver un problema con un algoritmo de forma máis eficiente.
Pero nunca realmente pediu a semana cero, así,
canto custou Verizon ou outra persoa
para obter esta lista telefónica na orde de clasificación?
>> Non?
Non importa se mirando cara arriba Mike Smith
é super rápido, se leva un ano para clasificar as páxinas inicialmente.
Non?
Pode moi ben peneirar a través dun libro de teléfono ao azar,
se vai ser super caro para clasificalos lo.
Entón, se podemos ter outro voluntario.
Imos dar un ollo aquí enriba como nós might-- veña up-- como
poderiamos ir sobre a clasificación destes.
>> E se, de feito, podería Jordan unirse a nós aquí enriba do escenario.
Veña-se só por un momento.
Cal é o teu nome?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, imos cara arriba.
E vai ser uniuse por min e Xordán aquí.
Caroline, grazas.
Todo ben.
Entón o que temos aquí para Caroline ten 26 libros azuis
FAS que utiliza para administrar certos exames finais.
Estes están quedando difíciles de atopar, pero o que fixemos con antelación
é que poñemos o nome de alguén na parte de diante de cada unha delas,
pero mantivemos lo simple, a continuación, pór para fóra os nomes completos.
Por iso, sería poñer a persoa co nome G, D, J, B, todo o camiño da a Z,
pero eles están en orde aleatoria.
E por iso, se faría, falando seu camiño a través do problema como
facelo, pode ir adiante e Ordenar estes para nós, da a Z.
>> Audiencia: OK, entón L é como, no medio.
C está comezando.
B. J antes L. B, Q.
>> DAVID J. Malan: Manteña esa penso por un segundo.
Porque doutra forma, esta é só interesante para ti, eu, e Jordan.
Alí imos nós.
Audiencia: [inaudível].
R.
DAVID J. Malan: Aceptar.
Que estás facendo?
>> CAROLINE: M vén despois O.
>> DAVID J. Malan: Aceptar.
>> CAROLINE: O.
DAVID J. Malan: O, Bo.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Si.
>> CAROLINE: T, U, V
>> DAVID J. Malan: V, T, U, V. Polo tanto, parece que está making-- continuar.
Parece que está facendo unha gran pila aquí,
e tipo de unha gran pila de alí.
Así, a primeira parte do alfabeto, segunda metade do alfabeto.
Aceptar.
Bo.
Tipo de dividir o problema en dúas partes.
M, N, X. Si.
CAROLINE: K.
DAVID J. Malan: Aceptar.
K. Entón está tipo de selección Los un despois do outro,
poñelas á esquerda ou dereita, ou Z está pasando no chan.
Aceptar.
>> CAROLINE: Z está pasando no chan.
>> DAVID J. Malan: Aceptar.
Y pasa no chan.
Agora podemos poñer X.
>> CAROLINE: G.
DAVID J. Malan: G de ir á esquerda.
S está indo ben.
Todo ben, un vai todo o camiño á esquerda.
>> Caroline: A, B, C, D.
>> DAVID J. Malan: Agora é bo.
Temos A, B, C. W de ir alí en baixo.
Todo ben, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Boa.
CAROLINE: No centro, estou gonna--
DAVID J. Malan: Aceptar.
Entón, agora, imos tipo de mesturar estas varias pilas.
Entón, da a C, entón eu vexo D, e E, e F, e G, e H, I e agradable.
J, K. E entón, esa pila é de cabeza para abaixo, pero iso é OK.
Claro.
Podemos cortar algúns cantos.
Aceptar.
E entón necesitamos W, X, Y, Z
>> CAROLINE: Yeah.
>> DAVID J. Malan: Excelente.
Así, un gran grazas a Caroline para clasificar estes.
>> [Cheering]
>> Grazas.
Moitas grazas.
Entón agora imos considerar por un momento como Caroline pasou facendo o que,
e exactamente o que nós foron capaces a-- como nós
foron capaces de resolver este problema cando estabamos só
dado unha chea de entradas aleatorias.
>> Ben, parece que hai foi un pouco de un sistema de alí?
Dereita.
Así, as primeiras cartas no alfabeto, ela
era poñer á esquerda, eo cartas posteriores no alfabeto,
ela estaba poñendo a dereita.
E así que ela atopou algunhas cartas proximais, queridos
que vaia á dereita xunto ao outro, ía poñer-los en orde.
E entón nós medio que estes pequenos pilas de entradas ordenadas produciron.
>> E así que é moi parecido ao que a maioría de nós seres humanos faría.
Queremos especie de peneirar, e nós medio que temos un mecanismo.
Pero pode ser difícil de escribir -o abaixo nunha fórmula de per si.
El Sentín un pouco máis orgánico que iso.
Entón, imos ver se podemos agora conectado O problema co menor número de entradas.
>> No canto de 26, imos facer algo moito menos
con só dicir, sete, atrás estas portas, por así dicir.
Hai só sete números?
E se o obxectivo agora en man é atopar un valor,
imos ver como eficaz podemos facer sobre este asunto.
E imos ver se podemos agora comezar a aplicar algúns números,
ou algunhas fórmulas coas que para describir a eficiencia do noso libro de teléfono
algoritmo, o noso algoritmo libro exame, e de xeito máis xeral, busca de información.
>> Entón, para iso, deixe-me ir adiante, e na pantalla táctil aquí,
poñer un navegador web que ten exactamente eses sete portas.
E se nós puidésemos adquirir outro voluntariamente para vir ata aquí,
Engada esas mesmas portas por aquí.
Voluntario rápido.
>> Este um-- demos van a unha máis rápida e máis rápido agora.
Imos cara a abaixo.
Cal é o teu nome?
Trevor: Trevor.
>> DAVID J. Malan: Trevor?
Todo ben, Trevor, imos alí abaixo.
Entón Trevor ofreceuse aquí para facer un problema semellante, pero un que é
de ámbito máis restrinxido, e que está a suceder para permitir-nos para tentar formalizar agora
o proceso de selección de eses números.
>> Entón Trevor, pracer en coñece-lo.
Entón aquí é unha matriz, por así falar, unha lista de sete portas.
Dalle atopar-nos no número 50.
E, a continuación, despois do feito, di-nos como o atopou.
Debe ser-- todo ben.
Si, este é o único aquí?
Uh-oh.
Aceptar.
Premeu esa.
Bo.
>> E boa.
Agora fai clic esta.
E deixe-me dar-lle o micrófono, de xeito que telo en só un momento.
Dalle prema o xunto que pretende.
Si, é bo.
Trevor: Podo desmarque a porta?
DAVID J. Malan: Non, non pode desmarque.
Trevor: Aceptar.
Este.
DAVID J. Malan: Onde quere ir?
Cal?
>> Trevor: Que un.
>> DAVID J. Malan: Non.
>> Trevor: Aceptar.
Este.
>> DAVID J. Malan: Si.
Isto foi bo.
Todo ben.
Entón, cal foi o seu algoritmo ou procedemento para facelo, Trevor?
>> Trevor: Eu só pasei portas ata que eu atope a 50.
DAVID J. Malan: Aceptar.
Excelente algoritmo.
Entón, iso é bo.
Porque, en realidade, se eu revelar o que é detrás destas dúas outras portas, o que
imos atopar aquí é que só temos entrada aleatoria.
Así, foi realmente como así como se podería obter.
E, de feito, ten mellor que exhaustivamente buscando todo o conxunto,
porque sería realmente azaroso se tivese alcanzado o número
50 no último porto.
Pero o que en vez deulle unha hipótese.
Supoña que classifico todos estas portas ao redor,
de xeito que ten a números clasificados este tempo,
pero esta vez é realmente un diferente-- este tempo,
é realmente clasificadas para ti.
E agora a meta na man é acadar o número de 50.
>> Trevor: Aceptar.
>> DAVID J. Malan: Cal é seu algoritmo vai ser?
>> Trevor: Ben, se é clasificadas, é calquera que vai
para ser-- maior para o maior, descendente, vai ser o primeiro,
ou se é o contrario, será a última.
Entón só vou tocar esta porta, e a continuación, pode tocar a última porta.
DAVID J. Malan: Excelente.
Todo ben.
Así, atopamos o número 50.
Así, logo que soubese eles foron ordenados, nós
foron capaces de aproveitar esta suposición.
Entón, eles están moi parecido a exemplo do libro de teléfono.
Así que ten, mesmo con un pequeno problema como este,
súas entradas pre-clasificados, podemos realmente atopar o valor indiscutibelmente
de forma máis eficiente.
>> E eu non lle dixen que era clasificadas pequeno a grande, ou grande a pequeno,
e por iso era moi razoable para comezar nunha extremidade ou outro
para realmente atopar ese valor obxecto de aprendizaxe.
Por iso, gracias ao Trevor tamén.
E eu vou propose-- ben feito.
Temos un pequeno clip, de feito, que está entre os nosos momentos favoritos en CS50,
polo que, ás veces, estas demostracións non chegan a ir de acordo co plan.
E, de feito agora, eu tirou a interface incorrecta
que utilizar a pantalla táctil.
Así, foi culpa miña alí.
>> Entón, iso vai facer para clip do próximo ano como
a razón pola que eu estaba facendo clic no meu propio pantalla.
Pero imos dar un ollo rápida para o que pasou o ano pasado
con Jay, que xurdiu, moi como Trevor aquí, ofreceu-se,
e neste clip curto, podes ver como esta mesma demostración non fixo moito
revelar as mesmas leccións aprendidas.
[REPRODUCIÓN DE VIDEO]
-Todo Que quero que faga agora para atopar a min, e para nós,
realmente, o número 50 un paso de cada vez.
>> -O Número 50?
>> -O Número 50.
E pode revelar o que é detrás de cada unha destas portas
simplemente por tocar cun dedo.
Droga.
>> [Risas]
>> [FIN DE REPRODUCIÓN]
DAVID J. Malan: Así que foi moi ben.
Estas foron as portas sen clasificar.
E Jay, por suposto, penso todo moi rápido.
Trevor fixo un traballo moito mellor en termos de un momento de aprendizaxe,
por así dicir, este ano, en levando máis tempo para atopalo.
Claro, entón nós demos Jay unha segunda oportunidade,
polo cal nós ordenamos as portas, así como fixemos para o Trevor,
e Trevor fixo super-ben esta vez.
Pero Jay fixo metade tan axiña.
[REPRODUCIÓN DE VIDEO]
-O Obxectivo agora é tamén atopar-nos no número 50,
pero facelo a través de algoritmos, e di-nos como está indo sobre el.
>> -OK.
>> -E Se atopalo, manteña a película.
Se non atopalo, dá-lo de volta.
>> -Man.
>> -Oh!
>> - [Inaudível] Aceptar.
Entón, eu estou indo a comprobar os extremos primeiro para determinar se there's-- Oh.
>> [Aplausos]
>> [FIN DE REPRODUCIÓN]
DAVID J. Malan: Aceptar.
Entón selección portas claramente conduce a unha maior eficiencia.
E así, dúas veces máis rápido é o que eu quería dicir alí.
E así Jay tivo sorte dúas veces.
E tamén tivo sorte naquela última ano, eu pedín algúns discos Blu-ray
para realmente dar para fóra.
Sinto moito este ano, non teñen o mesmo, Trevor.
Pero mellor aínda era hai uns anos.
E algúns de vostedes poden saber iso compañeiro, Sean, que cando estaba na CS50,
foi desafiado coa exacta mesmo problema, aínda que en SD,
como podes ver en breve, de volta ao día.
E vai descubrir que non só el levar un pouco máis do que Jay,
un pouco máis do que Trevor, foi realmente esta oportunidade marabillosa
involucrarse case todos no multitude a la Prezo Correcto, incentivando
Lo a atopar o número que estabamos a buscar.
Imos. dar un ollo rápida.
>> [REPRODUCIÓN DE VIDEO]
>> -OK.
Polo tanto, a súa tarefa aquí, Sean, é o seguinte.
Eu oculto detrás destas portas o número sete.
Pero afastada, nalgunhas desas portas así como outros son números negativos.
E o seu obxectivo é pensar desta liña superior de números
como só unha matriz, ou só secuencia de anacos de papel
con números detrás deles.
E o seu obxectivo é, usando só o principio matriz aquí, atopar-me o número sete.
E nós estamos indo entón para criticar como vai facer sobre iso.
-Todo ben.
-Find-Nos número sete, por favor.
Non.
Cinco, 19, 13.
>> [Risas]
>> Non é unha pregunta capciosa.
Unha.
>> [Risas]
Neste punto, a súa puntuación non é moi bo, entón pode moi ben continuar.
Tres.
>> [Risas]
>> Vai adiante.
Francamente, eu non podo axudar, pero pregunta o que está mesmo a pensar, assim--
>> [Risas]
Só a liña superior, para ten tres esquerda.
Entón, atopar-me sete.
>> [Risas]
17.
Sete.
>> [Aplausos]
>> Todo ben.
>> [FIN DE REPRODUCIÓN]
>> DAVID J. Malan: para que puidésemos asistir a estes todo o día.
E, por suposto, algúns dos demos deste ano quizais
agora vai acabar o próximo video do ano tamén.
Entón agora imos realmente centrar os algoritmos
aquí, para ver se non podemos agora comezar a formalizar
como podemos ir sobre a obtención dos nosos datos a este estado que está clasificado,
de xeito que, en definitiva, podemos, de feito, buscala de xeito máis eficiente.
E aínda que nós imos usar conxuntos de datos relativamente pequeno,
como a que oito números temos aquí no cadro,
en definitiva, podería aplicar estas mesmas ideas 1.000 entradas, un millón de entradas,
4 millóns de insumos, porque os algoritmos van ser fundamentalmente o mesmo.
>> E así, este é o noso último oportunidade para os voluntarios de hoxe,
pero quizais o máis afectado, para o que necesitamos oito voluntarios
para subir e pé connosco a través do proceso de selección que será en breve
ser sobre estes postos de música aquí.
Déixeme comezar a volver aquí.
>> Entón, un no verde turquoise-- é?
Está cometendo?
Dous.
Imos cara a abaixo.
Aceptar.
Tres.
Four.
Imos me-- OK, cinco.
Está a ser nomeado polo seu amigo.
Seis, sete, e oito.
Imos cara arriba.
Todo ben.
Moitas grazas.
Imos cara arriba.
>> Todo ben.
Entón o que temos e iso aqui-- está entre os máis torpes,
xa que este vai esixir que humor Miña só un pouco de tempo.
Ten que ser o número un.
Cal é o teu nome?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
David.
Cal é o teu nome?
>> JOSÉ: José.
>> DAVID J. Malan: José, é o número dous.
>> SERENA: Serena, número tres.
Stefan, o número catro.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, número cinco.
[Inaudível]
DAVID J. Malan: [inaudível].
David, número seis.
Matt: Matt.
DAVID J. Malan: número de Matt sete.
E?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, número oito.
Todo ben.
Se could-- berros.
Se todo, como o seu primeiro reto, hai
Son oito andeis de música aquí de fronte para o público.
Se puidese poñer o seu número no estes soportes de música de tal xeito
que se aliñan co mesmos números no cadro.
Entón, fai-se ollar como por poñendo os seus números sobre estes música
fica aquí.
Excelente ata agora.
>> Excelente.
Aceptar.
Entón, agora, imos pedir ao cuestión en algunhas formas diferentes.
Como podemos ir sobre como clasificar esas persoas aquí enriba?
Porque tivemos algunhas enfoques anteriormente, en que estabamos
tipo de toma de dous baldes diferentes.
E entón nós xeralmente remendos as cousas xuntos.
Así que viu dous números que pertencía xuntos,
nós poñer-los xuntos.
Dúas cartas que pertencen xuntos.
>> Pero imos ver se nós Non se pode formalizar isto,
para que poidamos finalmente ter algúns pseudo-código que vai,
co cal pode resolver estes problemas.
Entón, agora, eu estou ollando para fóra estas cifras aquí.
E vexo unha morea de erros.
En definitiva, quero un no á esquerda e oito á dereita.
>> E entón eu estou ollando estes dous, catro e dous.
E cal é o problema, obviamente?
Si.
So.
Dous, obviamente, vén antes catro, entón vostede sabe o que?
Déixeme primeiro dar unha visión lambona, se, como moito problema
um-- definir se se lembra do Standard Edition do Conxunto de problemas One,
onde só localmente resolver o problema que está ben aquí na miña fronte
e ver onde me leva.
>> Aceptar.
Entón, dous e catro, deixe-me ir adiante e só intercambiar vostedes dous.
Se pode mover fisicamente vós mesmos eo seu papel,
Eu parezo comezar a incluír nun estado mellor.
>> Agora, son bos.
Vou seguir adiante, catro e seis anos, parece ser bo.
Non é un problema.
Seis e oito, Aceptar.
Oito e un, outro problema.
Porque o que é verdade sobre oito e un?
Un vén antes das oito, e así o que temos que facer?
Imos cambiar estes dous.
Un e oito.
E agora, eu vou continuar.
Vou continuar mirando para adiante.
E veremos que pasa.
Oito e tres, de Por suposto, fóra de orde.
Imos intercambio.
Oito e sete, por suposto.
Fóra de orde.
Imos intercambio.
Oito e cinco, por suposto, imos intercambio.
Todo ben.
Lista é ordenada.
si?
>> OK, obviamente, non.
Pero é un pouco mellor, non?
Porque aviso que pasou.
Cada vez que realizou un intercambio, un menor número tipo de percolado que xeito,
e un número maior percolado deste xeito, ou nós imos
comezar a dicir ao borbulhar cara á esquerda ou cara á dereita borbulhar.
>> Agora, non é suficiente, porque no mellor dos casos un número podería
mover un punto á fronte, ou no peor dos casos,
pode ter un número movido un lugar máis lonxe.
Entón, vostede sabe o que este tipo de funcionar moi ben ata agora.
Déixeme só probalo de novo.
Dous e catro, están OK.
Catro e seis, están OK.
Seis e un, fóra de orde.
Entón, imos cambiar vostedes dous.
E agora, repare o problema de empezando a estar un pouco mellor de novo.
Seis e tres, fóra de orde.
Imos cambiar vostedes dous.
Seis e sete, é bo.
Sete e cinco, por suposto, fóra de orde.
Sete e oito, en orde.
E agora, eu pode que necesite facelo máis algunhas veces.
E, de feito, creo que para vós quizais as veces maxima
pode eu teño que andar para atrás e cara adiante?
>> Nós imos voltar a iso.
Entón, dous e catro aínda están OK.
Catro e un, Nope.
Entón, cambio de deixar.
E, de novo, observar visualmente un é unha especie de borbulhar
á esquerda, onde debería estar.
Catro e tres intercambio.
Catro e seis.
Seis e cinco intercambio.
Seis e sete.
Sete e oito son boas.
>> Bo.
Estamos quedando aínda mellor.
Entón imos ver.
Agora temos dous e un.
Por suposto, cambiar.
Dous e tres, tres e catro, catro e cinco, seis e sete, sete e oito.
Bo.
E vostede sabe o que?
Porque eu fixen un cambio alí, deixe-me facer unha verificación de sanidade.
Deixe-me ir ata o final volver ao principio.
Aceptar.
Un, dois-- si, ver?
Algo estaba mal.
Tres, catro, cinco, seis, sete, oito.
E neste último pase, son Está satisfeito coa miña empresa
alegando que é clasificado?
Aceptar.
Visualmente, iso é absolutamente certo.
Pero funcionalmente, o que que tamén só terá lugar
nese último pase que permite que para confirmar que esta lista é de feito
clasificadas?
>> O que eu fixen ou non facelo último pase?
Audiencia: Non se substituiu nengunha verba.
DAVID J. Malan: Sentímolo?
Audiencia: Sen cambios.
DAVID J. Malan: Non se substituiu nengunha verba.
Polo tanto, sería estúpido da miña parte facelo mesmo algoritmo de novo
se eu non facer calquera modifica a primeira vez.
E o Estado non cambiou.
Certamente, eu non vou facer calquera cambia por segunda vez.
E así, é seguro agora quere dicir, lista é ordenada.
>> E, de feito, este é agora algo que nós imos xeral
chamada bubble sort, no que pares, corrixir erros de novo,
e de novo, e de novo, e manter indo e volvendo,
e adiante e cara atrás, ata que facer ningún destes swaps, en que punto
pode estar seguro, si, eu Terminada a fixación os erros.
Imos axustar e tentar outra visión.
Se vós poderían volver a orde que era un momento atrás,
que mirou como esta.
Agora, imos ter unha visión un pouco máis como o libro exame,
polo cal estabamos sempre seleccionando a letra do alfabeto
que nós medio que quería para xestionar o próximo.
Quizais fose carta alta, como A, ou unha baixa letra Z.
>> Entón, todo o mundo está de volta nesta orde.
E agora déixeme facer.
A ver Sei que teño oito números aquí.
Eu estou indo a ir adiante e só deliberadamente seleccione
os elementos máis pequenos.
Non?
Isto parece moi intuitivo.
Por que non atopar o menor elemento, poñelas onde pertence,
a continuación, obter o seguinte elemento máis pequeno, poña Lo onde pertence, e basta repetir.
>> Porque intuitivamente, que debe funcionar tamén.
Entón, catro, que é un número moi pequeno.
Vou lembrar de onde isto é.
Espera un minuto.
Dous é menor.
Déixame lembrar onde dous é, e esquecer-se sobre catro.
Nós imos tratar con isto máis tarde.
Seis, eu non estou interesado.
Oito, eu non estou interesado.
Un deles é o meu novo número pequeno.
Entón, eu vou lembrar onde está.
Tres, non interesa.
Sete, non interesa.
Cinco, non interesa.
>> Entón, sen caer o escenario este ano,
Vou coller número um-- e cal era o seu nome?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
E se puidese unirse a min na o inicio da lista,
imos poñelas onde pertence.
Unfortunately-- cal é o seu nome?
>> Stefan: Stefan.
>> DAVID J. Malan: Stefan está no camiño.
Polo tanto, antes de Stefan resolve este problema, o que temos que facer?
O que imos facer con Stefan?
>> Audiencia: [inaudível].
DAVID J. Malan: Aceptar.
Así poderiamos facelo.
Poderiamos tipo de levar Stefan ea súa catro, e basta colocar-lo nunha variable
e seguro-lo para unha certa cantidade de tempo,
tornando así espazo para o número un.
E iso non é malo.
Eu podería suxerir, por que non facer nós só poñer Stefan aquí?
Por que iso pode violar un das ideas que comezaron
falando última vez, a semana pasada?
Si?
>> Audiencia: [inaudível].
>> DAVID J. Malan: Non hai ningún índice para el.
Se pensas que iso, de feito, como un array, isto é como un negativo,
polo que non hai memoria, en realidade, aquí se este é realmente unha matriz,
como se declarou a semana pasada na conferencia.
Así, non hai que facelo.
Podemos almacena-lo nunha variable.
>> Ou vostede sabe o que?
Escoitei a alguén suxerir iso.
O que máis poderiamos facer Stefan?
Por que non só expulsalo lo e poñelas sobre o lugar onde estaba o número un.
Entón, se quere ir máis alá.
E, de feito, este é un solución moi boa.
Agora, por unha banda, eu teño tipo da empeorou o problema.
Catro é agora máis lonxe de onde debe ser.
Debe ser cara a ese medio.
>> Pero vostede sabe o que?
Isto podería ser mala sorte.
Quizais o número oito foi aquí.
E así, quizais fariamos ter sorte,
e oito empuxada para máis preto do final.
Así, ao final do día, É o tipo de todas as medias para fóra.
Non se preocupe con catro.
Todo o que me importa agora é seleccionando o elemento máis pequeno.
>> E agora, o que eu vou facer é esquecer-se sobre o número un
permanentemente, porque sei o lista detrás de min agora está clasificada.
Así, a miña lista era anteriormente tamaño oito.
Agora, é do tamaño de sete.
Entón, meu problema é conseguir menor, aínda que de forma lineal.
Entón, agora, eu estou indo a seleccionar o actual elemento máis pequeno, dous.
Seis, oito, catro, tres, sete, cinco.
Ese foi o menor elemento.
Entón que é o que eu vou facer com-- o que era o seu nome?
>> JOSÉ: José.
>> DAVID J. Malan: José?
Nós imos deixar Joseph no lugar.
Agora, eu vou finxir que estes faces é-- ben,
Sei que estes dous xa están clasificados.
Imos agora concentrarse na resto da lista.
Seis é a menor corrente.
Oito é maior.
Catro agora a menor corrente.
Tres é agora a menor corrente.
E agora, eu estou indo a seleccionar tres, que é-- o que é o seu nome?
SERENA: Serena.
DAVID J. Malan: Serena, se puidese cara o seu número e intercambio com--
Kalsang: Kalsang.
DAVID J. Malan: Kalsang.
Imos volver, e estamos vai cambiar os dous.
E agora, imos poñer isto no piloto automático.
Eu estou indo a ir e deixar para vós para seleccionar os menores elementos próximos.
Dun, Dun, Dun, Dun.
Número catro, o que ten que facer?
Excelente.
Agora, eu vou facer outra pasaxe.
Dun, Dun, Dun, Dun.
Vexo cinco é o seguinte menor.
Agora, eu vou tomar outra pasaxe.
Dun, Dun, Dun, Dun.
Seis é o menor.
Bo.
Sete é o menor.
Non se produciron cambios.
Oito é o menor.
Feito.
>> Entón, o que acaba de facer de forma iterativa seleccionando un elemento despois da outra
é aplicar algo que somos vai formalizar como selección de clasificación.
E é posible que aínda sinxelo de explicar,
en que, literalmente, todo o que quero facer é só manter
indo e volvendo pola lista selección, a próxima menor elemento,
ata que estea feito.
>> Por iso, é aínda máis sinxela, quizais intuitivamente, que a última.
Imos tentar un último.
Se vós poderían axustar a si mesmos nas seguintes posicións
unha última vez, imos ver se non podemos agora formalizar outra visión.
De feito, sería alguén aí quere propoñer
de que outra forma poderíamos facer sobre este asunto?
Sen tirar buzzwords ou tipo respostas que xa son coñecidas,
só intuitivamente, o que poderiamos facer?
>> Audiencia: [inaudível].
DAVID J. Malan: Yeah.
Entón, hai algunha gran intuición alí.
As cousas boas parecen ocorrer ata agora en ciencia da computación cando dividimos
e conquistar o problema de dividir polo medio e medio a medio.
E así, de feito, nós podería comezar a facelo.
E, de feito, que vai ser, imos ver, un dos nosos mellores solucións aínda.
Pero imos volver a iso en pouco tempo.
En realidade, nós imos facer que un pouco máis tarde esta semana.
O que máis podemos facer para solucionar isto?
Entón, todo o mundo aquí está orde aparentemente aleatoria.
Sabes que?
En vez de ir e volver, adiante e cara atrás, e cara atrás
cada vez, este se sente como Eu estou facendo unha morea de pé.
Por que non podo só comezar en o inicio da lista,
e pode poñer catro onde pertence?
Entón deixe-me asumir para o momento que miña lista é só este primeiro elemento.
É catro clasificados neste momento no tempo, se todo o que me importa é todo aquí?
Esta é unha especie de trivialmente verdadeira, non?
Como a lista contén un número, e que é, obviamente, o número catro clasificados.
>> Entón déixeme só estipular que esta lista é ordenada.
Pero agora eu teño o resto da lista.
Entón, agora, eu encontro dous.
Onde fai dous obviamente pertencen en relación a catro?
Antes catro.
Entón, o que podo facer aquí?
Cal é o seu nome?
>> JOSÉ: José.
>> DAVID J. Malan: José, se puidese volver atrás
por só un momento co seu número.
E agora o que debe Stefan facer aquí?
Imos cambiar Stefan aquí.
E agora, imos Joseph entrar aquí.
E agora, deixe-me dicir que todo aquí está clasificada.
Entón, resultado similar, pero un visión fundamentalmente diferente.
Eu nin sequera mirou para o que está alí en baixo.
Eu sigo tendo os elementos como son entregado a min,
e tratar con eles.
>> Entón, agora, eu vexo o número seis.
Onde é que o número seis pertencen?
Temos dous, catro, seis.
Exactamente onde está agora.
Entón, imos deixar isto quedo, e agora afirman que esta parte da lista
agora está clasificada.
E así, este se sente fundamentalmente diferente, xa que eu son só
movéndose a través da lista aquí linearmente, e eu nunca estou dobrando cara atrás.
Si.
Todo ben.
Así, oito, onde pertence?
Ben aquí.
Perfecto.
Entón, agora, un.
Uh-oh.
Isto parece que é vai ser caro.
Agora, no algoritmo anterior, Eu só trocados persoas.
Para que eu poida poñer-lo todo o camiño no en principio, pero despois cambiou Joseph.
Pero se eu pasar Joseph, agora o que vai ser mal?
>> Agora, eu teño a sorte de undone-- teño dado un paso á fronte e, a continuación,
un paso atrás, porque agora Joseph estaría fóra de orde.
Entón, imos facelo.
Se puidese levar o número un e paso atrás por só un momento.
Como podemos put-- o que mesmo o seu nome?
>> Annan: Annan.
>> DAVID J. Malan: Annan no lugar?
O que ten que ocorrer con respecto a dous, catro, seis, oito e?
Todo o que precisan cambiar.
Polo tanto, se oito quere desprazar en primeiro lugar, a continuación, seis, despois catro, despois dous.
E entón Annan, se quere vir aquí, bo.
Pero aquí, temos só tipo de pago un prezo
nun punto diferente no algoritmo.
Considerando última vez coa selección tipo, e mesmo bubble sort,
Eu estou camiñando cara atrás e adiante, para atrás e cara adiante,
que é, certamente, sumando tempo-sabio, e, literalmente, paso a paso.
>> Ordenación por inserción, na primeira vista, parece que é
super-intelixente, en que eu son só facendo lento, o progreso incremental,
pero eu non vou esta fronte e cara atrás.
Pero se alguén é de feito fóra de orde, previo
todo o traballo que eu só tiven que facer.
Tiven que cambiar a metade da lista só para dar espazo para o número un.
Entón é a mesma cantidade de traballo, ata agora,
sente, só un tipo de traballo.
>> Imos continuar.
Polo tanto, agora sabemos que todo o mundo entre un e oito son clasificadas.
Aquí, eu teño o número tres.
Se che gusta de incorporarse número tres, paso atrás un.
E o que vostedes teñen que facer?
Yep.
Entón, iso é outro, dous, tres pasos.
Tres unidades de tempo que custa só me, de xeito que os tres poden agora encaixar.
Finalmente, sete.
>> Imos adiante e ter tomar un paso atrás.
Isto só vai custar unha unidade de tempo, pero iso é OK.
E agora, cinco de ir ser un pouco máis caro.
Se desexa dar un paso atrás.
Necesitamos avanzar oito, e sete, e seis.
E entón todo o mundo está agora clasificada.
Así, unha gran man para os nosos voluntarios aquí.
Moitas grazas.
>> [Aplausos]
>> Grazas a todos.
Grazas a todos.
Entón imos ver agora como caro todo isto era.
Imos considerar, se cadra, o máis simple delas, unha especie de burbulla.
E digo máis simple, só porque pode resolver-lo avidamente por só
resolver o problema de pares aquí.
Resolver o problema de pares aquí, unha e outra vez
e de novo, repetindo como moitos veces como realmente precisa.
>> Así, verifícase que cunha especie de burbulla, así,
cantos pasos teño que asumir a primeira pasaxe dese algoritmo?
Podería take-- imos see-- un, dous, tres, catro, cinco, seis, sete.
E hai oito elementos aquí.
Entón, é como n menos 1 pasos para comeza a partir do inicio da lista
ao final da lista.
>> Pero con selección tipo, lembre que eu son seleccionar os elementos novo e de novo
e, de novo, que é menor, Estou poñendo-o no lugar,
pero entón eu non son mirando atrás de min de novo.
Entón, eu creo que é un pouco máis clara que, a continuación, por primeira vez, que pode
ten que tomar todos os pasos n menos 1 para atopar o elemento máis pequeno.
Entón eu poñer-los no lugar, e eu expulsar quenquera que estivese aquí anteriormente.
>> Pero entón eu non teño que manter a ollar a este elemento,
porque sei que é xa a menor.
Entón, agora, podo ver só sete elementos, a continuación, seis elementos,
a continuación, cinco elementos, a continuación, catro elementos.
E así matematicamente, se n é o número de elementos ou números
que comezou con, pode imaxinar que este é o mesmo que n menos 1,
ademais n menos 2 etapas, n menos 3 etapas,
n menos 4 pasos, todo o forma abaixo a un paso.
E eu estou na miña última persoa.
>> E se se lembra que unha morea Estado de libros ou libros de matemáticas
ter esas fórmulas na capa dura cara atrás ou diante deles,
verifícase que esta serie pode ser expresado de forma máis simple
como n veces n menos 1 sobre 2.
E é bo se isto non é na vangarda da súa mente.
Pero iso é realmente verdade.
Isto é só unha maneira máis sinxela de escribilo.
E entón se pensas de volta á escola,
cando acaba de comezar multiplicando cousas, iso, por suposto,
é só n ao cadrado menos n dividido por dous.
Todo o que eu teño feito é ampliar as expresións alí.
E así imos ter que volver escribir este un pouco diferente.
Isto n ao cadrado dividido por 2 menos n / 2.
>> Entón, de novo, eu son só un tipo de aplicación un pouco de aritmética goberna alí.
Pero teña en conta-se agora que o maior prazo nesta expresión, por así dicir,
é que n ao cadrado.
Entón, si, é n ao cadrado dividido por dous, menos n / 2.
>> Pero, xeralmente, se n é vai ser un valor grande,
Vou alegar que n ao cadrado vai ser o factor dominante.
É só será un contribuínte grande
ao número de pasos que n / 2.
Entón, o que quero dicir con isto?
Imos tentar un exemplo simple, mesmo aínda que a matemática está un pouco grande.
>> Entón, supoña que 1 millón de persoas no escenario, ou 1 millón de cousas
que quere clasificar.
Imos poñer en marcha un millón en exactamente que fórmula
para ver cantos pasos que leva totais para clasificar un millón de elementos usando digamos,
tipo de selección.
>> Entón, nós teriamos a mesma fórmula como antes.
Conectar un millón, para que eu recibín un millón cadrado dividido por 2,
menos dun millón dividido por 2.
Se eu fai iso de matemáticas con antelación aquí temos 500 millóns
menos 500.000, que dános 499999500000,
que é moi danado grande.
>> En realidade, se comparar agora 499.000 millóns, 999 millóns,
500000 contra o noso valor orixinal, 500 millóns, é tan ben preto.
Non? n ao cadrado dividido por 2 dá US-- ou mellor, n ao cadrado dividido por 2
deunos 500 millóns.
Iso é moi danado preto a 499.999.500.000,
o que quere dicir fóra subtraindo 500.000, ou, máis xeralmente, subtraindo fóra
n ao cadrado, non é realmente un gran negocio.
O n ao cadrado fai que estas números crecen moi rápido.
>> Agora, iso só é importante na medida en como nós, como científicos da computación,
son xeralmente non vai importar tanto sobre as pasaxes destas fórmulas
e exactamente o que o respostas precisas son.
Nós nos preocupa só iso, vostede sabe o que?
Ao final do día, esta fórmula é da orde de n ao cadrado.
>> Si, estamos dividindo por dous alí dentro.
Si, estamos subtraindo off n menos 2.
Con todo, ao final do día, o termo que realmente doe e costa connosco
unha serie de etapas que o termo cadrado.
E entón o que un científico da computación vai xeralmente fan
é ignorar todos os Da orde menor,
e basta ollar para o que máis contribúe ao custo.
>> E iso é bo, porque podemos agora falar con máis xeneralidade
sobre algoritmos, e pode comparalos-los.
E o feito de que eu son O utilizando este é deliberada.
Cando digo no fin de, estou especialmente
referíndose a algo chamado gran O. E ó gran
é unha notación que un ordenador científico usa para describir
un límite superior en algo.
>> Entón, se dicir que un algoritmo é en gran O n ao cadrado,
como eu propuxen só un hai pouco, que os medios
que, en termos da súa execución tempo ou a súa eficiencia,
el asume a orde cadrado de n pasos.
Quizais máis, quizais menos.
Pero é da orde de n ao cadrado.
E ese é o límite superior.
Non vai ser máis doloroso do que iso.
Non vai ser n cubos, ou 2 ao n, ou algo moito maior.
Este é un límite superior en todo o que o custo é.
Así, dado que, imos Considero só algúns exemplos.
E esta é só unha lista finita tempos de execución de moi comúns
para algoritmos que está destinado a ser ilustrativos dalgúns cousas que temos
visto xa.
>> Así, por exemplo, no caso de selección tipo, o que eu digo aquí
se está a executar que a selección de tipo tempo é da orde de n ao cadrado.
No peor caso, eu vou ter unha morea de números aleatorios aquí.
E, como vimos matematicamente, se eu continuar camiñando
por medio da lista, a través do lista, seleccionar o seguinte menor
elemento novo e de novo, se eu de feito, anota todos os pasos
Estou tomando como eu propuxen como unha fórmula antes, é da orde de n ao cadrado
pasos que eu estou tomando.
>> E parece que burbulla tipo e ordenación por inserción
son tan lento no peor dos casos.
Considero, por exemplo, ordenación por inserción, o último algoritmo, tratamos,
que nos fixo ollar para o elemento, e, a continuación, inserir-lo onde pertence.
E entón miramos ao seguinte elemento, e inseriu lo onde pertence.
>> Por iso, considero o mellor escenario posible.
Supoña que tiña meus voluntarios aliñar literalmente, como este, de un a oito,
xa ordenados.
Cantos pasos é a ordenación por inserción vai levar para clasificar oito persoas,
se chegan no escenario mirando así?
>> Oito persoas xa ordenados.
E eu uso a inserción de tipo.
Ese último dos algoritmos.
Ben, imos revivir rápido real.
Entón, se eu comezar, eu vexo un.
Onde é que se pertencen?
Pertence aquí.
Vexo dous.
Onde é que dous pertencen?
Ben aquí.
Vexo tres.
Onde é que tres pertencen?
Ben aquí.
>> Vexo catro.
Ben aquí.
Cinco, seis, sete, oito.
Non hai ningunha razón para me repetir.
E así, como moitos pasos é que, en termos de n?
É da orde de n pasos, non? n menos 1.
Pero eu tomou unha serie lineal de pasos, e agora eu son feito.
Entón ese é o mellor caso, con todo.
E sobre o peor caso?
Que oito estaban alí, e sete estaban alí embaixo,
e un e dous foron máis aquí, entón que a lista foron verdadeiramente revertido?
>> Ben, o que pasa realmente se este é o número?
E nós imos facer só un par de exemplos.
E se, de feito, o número oito está aquí, e os berros number--.
Entón, o que, de feito, o número oito é todo o camiño ata aquí,
e eu estou usando ordenación por inserción?
>> Aceptar.
Eu reivindico no momento que está no lugar.
Pero agora, seven-- onde é que sete ir?
Claro, que vai por aquí.
Entón eu teño que mover oito máis dun lugar.
Agora seis, onde vai?
Ben, todo ben.
Agora, eu teño que cambiar oito máis un lugar, e sete ao longo dun lugar,
e entón eu plop abaixo seis.
>> Así, o primeiro tempo, custo me un paso para fixar as cousas,
entón iso me custou dous pasos para arranxar as cousas.
Cantos pasos se vai levar para corrixir
cousas para poñer cinco no lugar seguro?
Tres.
Porque agora eu teño que mover un, dous, tres.
Cantos pasos é que vai tomar para poñer catro no lugar seguro?
4 plus 5, engade 6, ademais de sete.
>> E por iso é matematicamente idéntica á o que describimos para a selección de clasificación.
Temos nesta serie que só está a aumentar.
1 máis 2 máis 3, 4, ou, inversamente, 7 + 6
máis 5 4 engádese se para hoxe para fins da orde de n ao cadrado.
>> Entón deixe-me tamén que estipulan bubble sort é tamén no n ao cadrado.
Porque con bubble sort, cada xa que eu vaia a lista,
Estou levando aproximadamente cantos chanzos?
Cada vez que eu literalmente andar de alí para alí?
Preto de n pasos.
Pero cantas veces eu podería que ir a través da lista?
>> Ben, preto de tempo n.
Quizais n menos 1, pero preto de n veces.
Ben, por que isto?
Ben, con bubble sort, se comezamos con bubble sort,
coa lista na peor posible situación, que unha vez máis é totalmente
cara atrás, o que vai pasar?
Eu percorrer a lista, eo número un pertence todo o camiño ata alí.
>> Pero con bubble sort, ata que punto é que un mover na miña primeira pasaxe a través da lista?
Cantos puntos consegue máis próximo ao lugar correcto?
Só un.
Entón, se tipo de razón través deste, cada vez a través deste algoritmo,
Tendo uns n pasos de David.
Pero cantos pases a lista é
vai levar a un a burbulla á esquerda, onde pertence?
>> Ten que moverse como, n espazos deste xeito.
Entón, só para facer a selección da lista, Teño que andar cara atrás e n veces.
E cada vez, estou buscando n elementos.
Entón, facer as cousas n n veces da orde de n ao cadrado.
>> Agora, imos ver en algúns dos curtas que
son incorporados no seguinte problema do CS50 definida, outra visión para estes,
pero por agora, imos considerar só algúns outros tempos de execución,
especialmente se os selección tomar un pouco de tempo para afundir.
¿Que é un algoritmo que vimos xa que leva na orde de n pasos?
>> O que debe tomar unha serie lineal de pasos que vimos ata agora?
Que é iso?
A investigación de directorio de teléfono.
O primeiro algoritmo.
Non?
Onde estamos linearmente buscando Mike Smith?
De feito.
A partir da semana cero, cando comece virando unha páxina de cada vez,
e eu mesmo dixo que era unha especie dun algoritmo sensación lineal,
e tivemos que imaxe na tarxeta coa liña vermella recta
eo amarelo en liña recta liña, aqueles eran de feito
algoritmos que son en gran ó n.
>> Porque para atopar Mike Smith nun teléfono libro de n páxinas, no peor caso,
me pode n pasos tomar.
Que tal incorporarse atención?
Un, dous, tres, catro, cinco, seis.
Cal é o tempo de execución deste algoritmo para facer a chamada?
Big O n, porque, en teoría I ten que apuntar todos na sala.
>> Agora, como un aparte, que sobre o outra optimización de semana de cero?
Dous, catro, seis, oito, 10, 12.
Un científico da computación sería entender, agarde un minuto,
que é da orde de n dividido por dous pasos.
Non?
Porque eu estou facendo dúas persoas de cada vez.
Pero imos ignorar estes termos de orde máis baixa,
e nós só estamos indo a xogue fóra a dividir por 2,
e só dicir, gran O n para ese algoritmo ben.
>> Que tal un regalo?
Imos saltar algúns destes, pero o que era un algoritmo que se rexistro de n?
Isto levou preto de log n pasos?
O dividir e conquistar.
Exactamente.
Como o exemplo do libro de teléfono en semana cero e hoxe cedo,
onde dividimos o problema de novo e de novo e de novo.
Nós chamou-o sobre a placa a semana cero como unha liña verde curvado,
e dixemos que día era un algoritmo logarítmica.
>> E, de feito, o número de pasos leva a cabo dividir e conquistar,
ou busca binaria como nós imos comezar chamando-o, como no libro de teléfono,
é da orde de rexistro e etapas.
E iso é un pouco de un estraño.
>> Que leva unha única etapa, ou máis especificamente
un número constante de pasos?
Quizais sexa dous, é posible que tres, pero un científico da computación só
simplifica-lo tan grande O de 1, un número constante de pasos.
¿Que é algo que podería facelo ten un número constante de pasos?
>> Cal é o tempo de execución de aplaudir?
Tempo constante.
Non?
Como, cal é o tempo de execución de facer algo que leva só un
operación, como imprimir F Ola Mundo.
Isto pode ser considerado constante de tempo, a non ser que menos se esquina coa impresión F,
O que o tempo de execución de impresión F realmente ser?
E por que?
¿Que é de medición n nese caso?
>> Audiencia: [inaudível].
DAVID J. Malan: Exactamente.
O número de caracteres que desexa imprimir.
Polo tanto, é moi sensible ao contexto.
Hoxe, temos que chegou a apostar moito en letras e números aquí no consello.
Pero tamén pode ser caracteres nunha secuencia real.
Así, verifícase aí é outra medida que vai comezar a preocuparse,
e iso é o oposto de gran O, por así dicir.
>> Isto é notación omega.
Tendo en conta que gran O significa o que é, o un límite superior ao seu tempo de execución?
Como máximo, canto tempo pode tomar algo?
Omega-- Sentímolo este segue vindo up-- é o contrario do que,
polo que é un límite inferior na cantidade de tempo algo pode tomar.
>> So. por exemplo, o que é un algoritmo que toma medidas sempre n ao cadrado?
Ben, un dos algoritmos que vimos Hoxe en día, de feito, pode ser que como ben.
Tipo de selección.
Selección tipo é moi estúpido.
Aínda que o algorithm-- Sentímolo, mesmo a matriz xa está clasificado,
selección tipo vai manter unha curta andaina a través da lista
para asegurarse de que ten o menor elemento novo e de novo e de novo.
E aínda que o ser humano no público sabe diso, agarde un minuto,
xa pasou o elemento máis pequeno, o ordenador
non sabe que ata parecer todo o camiño a través da lista.
Do mesmo xeito, un límite inferior que Tamén pode ser tida en conta
quizais sexa tempo lineal.
>> Canto tempo leva a elementos tipo n no mellor
caso usando algo bubble sort?
Supoñamos que a súa lista xa está clasificado.
Dixemos bubble sort asume da orde de n ao cadrado etapas.
Pero e se xa está clasificado?
E se entender despois un paso a través da matriz
que fixo hai swaps?
Debe seguir facendo máis pases?
>> Non.
Así, un límite inferior na bubble sort se pode dicir para ser lineal.
Omega de n.
E podemos ollar para outros destes tamén.
Entón, imos dar un ollo rápida en só unha vista aquí
para ver como estes se distinguen.
Eu estou indo a ir para abaixo aquí neste A páxina que está dispoñible na páxina web do C50,
pero vai ser unha dor de comezar a traballar, xa que utiliza unha tecnoloxía chamada
Applets Java, que é un en gran parte sen apoio a día de hoxe,
polo menos por Chrome e certos outros.
>> E deixe-me ir adiante e acelerar este e explicar o que está pasando.
Esta é unha demostración de burbulla tipo, o primeiro algoritmo de nós miramos.
E é a vista na que cada destas barras representa un número.
Canto máis longa sexa a barra, canto maior sexa o número.
Canto menor o bar, Canto menor o número.
E o que se pode ver visualmente, aínda aínda que este vai super rápido,
é que a barra vermella é como eu, camiñando cara atrás e resolver problemas.
Podes ver que os elementos máis grandes son, en realidade burbullas para a dereita,
e os elementos menores está borbulhando á esquerda.
E aquí, se nós realmente ollar máis de preto,
podemos realmente contar o número de comparacións e swaps
que estaban sendo feitos.
>> Pero en vez diso, imos ollar no segundo algoritmo
vimos anteriormente co noso voluntarios, selección de clasificación.
Visualmente, ten un efecto moi diferente.
Pero é, de novo, moi intuitivo, en que temos que seleccionar o próximo menor
elemento, e temos un pouco de sorte.
Iso foi fundamentalmente máis rápido.
Pero se nós corremos ese novo e de novo e de novo con moitos insumos,
veriamos que é de feito aínda en gran O n ao cadrado.
>> Imos facer un último aquí, ordenación por inserción,
que foi o terceiro algoritmo nós miramos, ea recordo
que este trata sobre a como elementos que atopa-los,
Pero, entón, quizais quendas cousas para abrir espazo,
inserción de elementos a que pertencen.
>> E iso tamén acaba dando o resultado final. Agora todos os tres dos
sentín moi rápido.
E, de feito, eu execute a eles nun bo clip.
Pero, fundamentalmente, son todos ben horrible, para ser honesto.
Todos estes algoritmos ata agora que son executados en gran O n ao cadrado
tomar un pouco de tempo para ser executado ao final.
>> E, de feito, podemos ver e sinto que este, por último,
se eu puxar arriba esta terceira e última demostración.
Este é outro visualización que está a suceder
para mostrar bubble sort á esquerda, tipo de selección no medio,
e algo, como un dos nosos man levanta antes suxeriu,
merge sort á dereita.
Un dividir e conquistar estratexia da dereita.
E iso é, en realidade, o que somos indo ollar o mércores.
Pero o tempo estes funcionen en paralelo imos.
É máis ou menos o mesmo número de elementos, todo rodando á vez.
Bubble sort vs selección tipo vs merge sort.
>> Agora, eles están todos correndo en teoría, ao mesmo tempo.
A CPU está en execución en a mesma velocidade, pero
Pode sentir-se como aburrido que é indo moi rápido para facer,
e quão rápido cando nós inxectar un pouco de semana
algoritmos de cero pode que acelerar as cousas.
>> E agora imos comparar estes nunha última forma.
Eu estou indo a ir adiante para o sitio web do CS50, onde
temos este elo final para hoxe, onde alguén en internet
xentilmente montar un vídeo que capta o que ordenación diferente
algoritmos soan como.
Esta é a ordenación por inserción.
>> [Bipé]
>> A través do cal está aplicando unha frecuencia con base na altura da barra de ferramentas.
Esta é bubble sort.
>> [Bipé Warped]
>> Chegando preto é-- benvida xunto especie selección é--,
onde unha vez máis, estamos seleccionando o seguinte elemento máis pequeno,
e podemos velo crecer de esquerda a dereita.
>> Merge sort, o noso gañador, ata agora, hoxe.
Observe como está dividindo as cousas en [inaudível] a metade e trimestres.
Tipo Gnome, que non ten falou, e crea visualmente
e audally un pouco de forma e son diferente.
Indo e volvendo, limpar as cousas.
Tamén check out heapsort na páxina web do cara.
>> E é iso.
Imos velo a próxima vez.
>> [Whooshing E MÚSICA]