DAVID Malan: Todo ben. Estamos de volta. Polo tanto, neste segmento sobre a programación que Penso que faría é unha mestura de cousas. Un, facer un pouco algo práctico, aínda que cunha forma máis lúdica environment-- programación un que é demostrativo de exactamente tipo de ideas vimos falando, pero un pouco máis formalmente. Dous, ollar para algúns dos as formas máis técnicas que un programador sería realmente resolver problemas como o problema busca que mirou antes e tamén unha máis fundamentalmente problema interesante de clasificación. 

Nós só asumiu desde o ir buscar que este libro de teléfono foi resolto, pero que por si só é realmente unha especie de problema difícil con moitas formas diferentes resolvelo. Entón, imos usalos como unha clase de problemas representante das cousas que pode ser resolto dun modo xeral. E entón imos falar sobre con algún detalle que chámanse datos structures-- formas máis extravagantes como listas ligadas e táboas de hash e árbores que programador sería realmente usar e, xeralmente, utilizar nun cadro branco para pintar unha imaxe do que el ou ela albisca para a implantación algún anaco de software. 

Entón imos facer o hands-on primeira parte. Entón, só tes que ensuciar as mans cun ambiente chamada scratch.mit.edu. Esta é unha ferramenta que usan na nosa clase de graduación. Aínda que está deseñado para as idades de 12 e por riba, podemos usalo para o up parte dese algo xa que é un bo, divertido forma gráfica da aprendizaxe algo sobre programación. Entón cabeza para que URL onde debe ver unha páxina como esta, e dalle clic Únete a cero na esquina superior dereita e escoller un nome de usuario e un contrasinal e finalmente, obter-se un scratch.mit.edu account--. Penso en usar isto como unha primeira oportunidade para amosar isto. A cuestión foi levantada durante a pausa sobre o código realmente se parece. E nós estabamos falando durante a pausa de aproximadamente C, en particular un particular-- menor nivel nunha linguaxe máis antiga. E eu só fixen unha rápida Google busca para atopar o código C descriptor binaria, o algoritmo que usado para buscar o libro de teléfono máis cedo. Neste exemplo concreto, por suposto, non buscar un libro de teléfono. El só busca unha morea de números na memoria do ordenador. Pero se quere obter só un Visual sentido que unha programación real linguaxe parece, parece un pouco algo como isto. Polo tanto, é un 20-plus, 30 ou máis liñas de código, pero a conversa que estaban tendo durante as vacacións era sobre como realmente converteuse ceros e uns e se non pode simplemente reverter esta procesar e ir de ceros e uns volver ao código. 

Desafortunadamente, o proceso de é tan transformadora que é moito máis fácil dicir que facer. Fun adiante e realmente se converteu este programa, Binary Search, en ceros e uns por medio dun O programa chamado compilador que ocorrer de ter aquí ben no meu Mac. E se ollar para a pantalla aquí, concentrando-se especialmente neses seis columnas do medio só, verás só ceros e uns. E estes son os ceros e uns que compoñer exactamente este programa de investigación. 

E así cada peza de cinco bits, cada byte de ceros e uns aquí, representan algunhas instrucións tipicamente dentro dun ordenador. E, de feito, se xa escoitou o slogan de márketing "Intel Inside" - que, por suposto, significa só que ten un CPU Intel ou o cerebro no seu ordenador. E o que significa ser un CPU é que ten un conxunto de instrucións, por así dicir. 

Cada CPU no mundo, dos Los feito por Intel nos días de hoxe, comprende un finito número de instrucións. E esas instrucións son tan baixo nivel como engadir eses dous números xuntos, multiplicar estes dous números xuntos, mover este anaco de datos a partir de aquí para aquí na memoria, gardar esta información aquí ata aquí na memoria, e así por forth-- moito baixo nivel, detalles case electrónicos. Pero cos matemático operacións axustado co que discutir anteriormente, a representación dos datos como ceros e uns, pode construír todo que un ordenador pode facer hoxe, sexa é textual, gráfica, musical, ou doutra forma. 

Entón iso é moi fácil de obter perdido nas herbas daniñas de xeito rápido. E hai unha morea de retos sintáticas en que facer o máis sinxelo, estúpido de erros de dixitación ningún programa funcionará calquera. E así, en vez de usar un linguaxe como C, esta mañá, Eu penso que sería máis divertido para realmente facer algo máis visual, que mentres deseñado para nenos é, en realidade, unha manifestación perfecta dunha programación real language-- só pasa de usar imaxes en vez de texto para representar esas ideas. 

Entón, cando de feito ten un conta en scratch.mit.edu, prema no botón Crear na esquina superior esquerda da páxina. E ten que ver un ambiente como o que eu estou a piques de ver na miña pantalla aquí. E nós imos gastar un pouco pouco de tempo a xogar aquí. Imos ver se non podemos todos resolver algúns problemas xuntos do seguinte xeito. 

Entón, o que podes ver dentro deste environment-- e realmente só deixar me unha pausa. Será que alguén non está aquí? Aquí non? OK. Entón, deixe-me salientar algúns características deste medio. 

Entón, na parte superior esquerda da pantalla, nos ten escenario cero, por así dicir. Cero non é só o nome desta linguaxe de programación; é tamén o nome do gato que ve por defecto, non en laranxa. Está nun estadio, de xeito tanto como eu describe a tartaruga anteriormente como estar nun rectangular ambiente cadro branco. mundo deste gato está totalmente confinada para ese rectángulo enriba alí. 

Mentres tanto, do lado dereito lado aquí, é só unha área de guións, unha lousa en branco se quere. Este é o lugar onde nós estamos indo a escribir nosos programas en só un momento. E os bloques de construción que debe usado para gravar esa program-- o puzzle anacos, se will-- son aqueles aquí no medio, e están categorizados pola función. Así, por exemplo, eu estou indo a ir adiante e demostran, polo menos, un destes. Eu estou indo a ir adiante e prema a categoría de control encima. 

Polo tanto, estas son as categorías enriba. Vou prema na categoría de Control. Pola contra, eu vou facer clic nos eventos categoría, o primeiro un encima. E se quere seguir, mesmo como facelo, está moi benvido para. Eu estou indo a facer clic e arrastrar ese primeiro, "cando a bandeira verde premendo." E entón eu vou deixala só aproximadamente na parte superior dos meus follas en branco. 

E o que é agradable sobre risco é que esta parte do enigma, cando interligado con outro puzzle pezas, vai facer literalmente o que estas pezas do puzzle dicir que facer. Así, por exemplo, Scratch é correcto agora no medio do seu mundo. Eu estou indo a ir adiante e elixir Agora, imos dicir, a categoría Movemento, Se desexa facer o same-- categoría Motion. E agora noten teño un todo chea de pezas do puzzle aquí que, de novo, tipo de facer o que eles din. E eu estou indo a ir adiante e arrastrar e soltar o bloque movemento ben aquí. 

E teña en conta que, así que comeza preto da parte inferior da "bandeira verde premendo "botón, o aviso previo como unha liña branca aparece, como se fose case magnética, quere ir máis alá. Só deixe ir, e se encaixará en conxunto e as formas corresponde. E agora pode, talvez, case adiviñar onde estamos indo con iso. 

Se ollar para o estadio cero por aquí e ollar para arriba, verás unha luz vermella, un deixe o sinal, e unha bandeira verde. E eu estou indo a ir adiante e asistir os meus screen-- por só un momento, se puidese. Vou prema o bandeira verde agora, e moveu-se o que parece ser 10 pasos ou 10 píxeles, 10 puntos, na pantalla. 

E así non excitante, pero déixeme propoñer sen sequera ensinando iso, só tes que usando o propio o seu propio let intuition-- -me propoñer que descubrir como facer scratch pé para fóra do escenario. Telo abrir camiño para o lado dereito a pantalla, todo o camiño para a dereita. Deixe-me dar-lle un momento ou máis para loitar con iso. Pode querer dar un ollo noutras categorías de bloques. Todo ben. Entón, só para recapitular, cando temos a bandeira verde premendo aquí e mover 10 pasos é a única instrución, cada vez que eu prema na bandeira verde, o que está pasando? Ben, iso está executando o meu programa. Entón, eu podería facelo quizais 10 veces a man, pero este se sente un pouco pouco hackish, por así dicir, en que eu realmente non estou resolvendo o problema. Eu só estou tentando de novo e de novo e de novo e de novo ata eu medio que accidentalmente alcanzar a Directiva que se propón acadar antes. 

Pero sabemos da nosa pseudocódigo anterior de que hai esta noción en programación de looping, facendo algo novo e de novo. E entón vin que unha morea de ti alcanzou peza o puzzle? Repita ata. Para que puidésemos facer algo como repetir ata. E o que repetir ata que exactamente? 

OK. E déixeme ir con un que é un pouco máis simple para só un momento. Deixe-me ir adiante e facelo. Teña en conta que, como pode ter descuberto baixo control, existe este bloque de repetición, que Non parece que é tan grande. Non hai moito espazo no entre esas dúas liñas amarelas. Pero, como algúns de vostedes poden ter notado, se arrastrar e soltar, notar como medra para cubrir a forma. 

E aínda pode empinar máis. El só vai continuar a crecer, se arrastrar e pair sobre el. E eu non sei o que é mellor aquí, entón imos me, polo menos, repetir cinco veces, por exemplo, e despois volver para o escenario e prema na bandeira verde. E agora entende que non é ben alí. 

Agora algúns de vostedes proposto, Victoria fixo, repita 10 veces. E que xeralmente fai leva-lo todo o camiño, Pero non sería haber unha máis robusta xeito que arbitrariamente descubrir cantos movementos para facer? O que podería ser un bloque mellor que repetir 10 veces ser? 

Si, entón por que non facer algo para sempre? E agora déixeme ir esta parte do enigma dentro e librar-se dun presente. Agora conta, non importa onde Raspadinha comeza, que vai para o bordo. E por sorte MIT, que fai scratch, só garante que nunca desaparece por completo. Poderá coller súa cola. 

E só intuitivamente, por que segue movendo? O que está pasando aquí? El parece parado, pero logo se eu incorporarse e arrastrar segue querendo ir máis alá. Por que é iso? Verdadeiramente, un ordenador é, literalmente, vai facer o que diga a el para facer. Entón, se dixo que antes facer o O seguinte para sempre, mover 10 pasos, vai continuar e vai ata que eu bati o sinal vermello e deixar o programa completo. 

Así, mesmo se non está facelo, como eu podería facer mover máis rápido risco do outro lado da pantalla? Máis pasos, non? Entón, en vez de facer 10 á vez, polo que non dalle cambiar isto a-- o que propose-- 50? Entón agora eu vou prema o verde bandeira, e, de feito, que vai moi rápido. 

E, por suposto, é só unha manifestación de animación. Que é animación? É só mostrándolle a un ser humano grupo enteiro de imaxes fixas, realmente, moi, moi rápido. E por iso, se nós estamos só dicindo Lo a moverse máis pasos, Nós só estamos tendo o efecto pode cambio onde está na pantalla toda a unidade máis rapidamente por tempo. 

Agora, o seguinte reto que propuxen era telo ir para fóra do borde. E sen saber o puzzle pezas exist-- porque é fina se non chegar ao etapa que challenge-- quere facer intuitivamente? Como poderiamos telo ir para atrás e diante, entre a esquerda e dereita? 

Si. Entón, necesitamos algún tipo da condición, e parecen condicionais, por así falar, baixo a categoría de control. Cal destes bloques nós probablemente quere? Si, quizais ", entón." Entón, teña en conta que, entre os bloques amarelo temos aquí, non é este "se" ou este "if, else" bloque que nos permiten tomar unha decisión para facelo ou para facelo. E aínda pode inserir-las para facer moitas cousas. Ou se non fose aínda aquí, dalle á categoría Sensing e- imos ver se está aquí. 

Entón, o bloque pode ser útil aquí para detectar se está fóra do escenario? Si, ter en conta que algúns destes bloques pode ser parametrizada, por así dicir. Poden ser tipo de personalización, non ao contrario do HTML onte con atributos, onde estes atributos tipo de personalizar o comportamento dunha etiqueta. Do mesmo xeito aquí, podo coller esta conmovedora bloque e cambio e facer a pregunta, está tocando o rato punteiro como o cursor ou está tocando a bordo? 

Entón deixe-me entrar e facelo. Eu estou indo a afastar un momento. Déixeme coller esta parte do enigma aquí, este enigma que, e eu vou Desorde Los por só un momento. Eu estou indo a ir este, cambiar esta a bordo tocar, e eu vou facelo de movemento. Entón, aquí están algúns ingredientes. Eu creo que eu teño todo o que quero. 

Será que alguén quere propoñer como eu pode conectar estes quizais de arriba para abaixo a fin de resolver o problema de ter Cero dereita a esquerda a dereita para mover esquerda a dereita á esquerda, cada un tempo só ir fóra da pantalla? O que quero facer? Cal bloque debe podo conectar á "Flag cando verde clic por primeira vez"? 

OK, entón imos comezar co "para sempre". Que dentro logo? Alguén máis. OK, move etapas. Todo ben. Entón o que? Entón a. E teña en conta, aínda que pareza imprensados ​​xunto con forza, ela só vai medrar para cubrir. Vai só no salto, onde quero. 

E o que eu puxen entre if e entón? Probablemente "se tocar bordo." E observen, de novo, é moi grande para el, pero el vai medrar para cubrir. E, a continuación, Xire 15 graos? Cantos graos? Si, entón 180 virará me a toda a volta. Entón imos ver se eu teño ese dereito. Déixeme afastar. 

Déixeme arrastrar cero superior. Entón, el é un pouco distorsionada agora, pero iso é bo. Como se restaurar-lo facilmente? Eu estou indo a enganar un pouco. Entón, eu estou engadindo outro bloque, só para quedar claro. Quero que apunta 90 graos á dereita por defecto, entón eu só vou dicir a el para facelo por medio de programación. E aquí imos nós. Nós parecemos ter feito isto. É un pouco raro, porque está camiñando de cabeza para baixo. Imos chamar ese un erro. Isto é un erro. Un erro é un erro nun programa, un erro lóxico que, o ser humano, feito. Por que está indo de cabeza para abaixo? Será que MIT romper ou eu? 

Si, quero dicir, non é MIT fallo. Eles me deron unha parte do enigma que di que transformar algúns número de graos. E por suxestión de Victoria, Estou xirando 180 graos, que é a intuición correcta. Pero transformar 180 graos literalmente significa virar 180 graos, e iso non é realmente o que quero, aparentemente. Porque polo menos está este mundo bidimensional, de xeito decisivo que realmente está a suceder para virar de cabeza para baixo. 

I probablemente vai querer usar o bloque en vez diso, segundo o que ve aquí? Como podemos solucionar isto? É, por tanto, podería apuntar no sentido oposto. E, de feito, aínda que sexa non vai ser suficiente, porque só pode código ríxido apuntando á esquerda ou á dereita. 

Vostede sabe o que poderiamos facer? Parece que temos un bloque de barrio aquí. Se eu aumentar o zoom, ver algo que nos gusta aquí? Polo tanto, parece que o MIT ten unha abstracción construída aquí. Este bloque parece ser equivalente para que outros bloques, plural? 

Este bloque parece ser equivalente a todo este trío de bloques que temos aquí. Non é que podo simplificar a miña programa por se librar de todo isto e pode poñer iso aquí. E agora aínda é un pouco cesta, e iso é bo para agora. Imos deixar que sexa. Pero o meu programa é aínda máis simple, e iso, tamén, sería representativa dun obxectivo en programming-- é ideal facer o código como simple, tan compacto como sexa posible, mentres seguen a ser tan lexible posible. Non quere facelo de xeito sucinto que é difícil de entender. 

Pero teña en conta que eu substituído tres bloques cun, e iso é, sen dúbida, unha cousa boa. Eu abstraída a noción comprobar se está no bordo con só un bloque. Agora podemos divertirse con iso, en realidade. Isto non engadir moito valor intelectual, pero valor lúdico. Eu estou indo a ir adiante e incorporarse este son aquí. Entón deixe-me ir adiante, e deixe-me deter o programa por un momento. Vou gardar o seguinte, permitindo o acceso ao meu micrófono. 

Alá imos. Ouch. Imos tentar que de novo. Alá imos. OK, eu gravei a cousa incorrecta. Alá imos. Ouch. Ouch. Todo ben. Agora eu teño para se librar desa. Todo ben. 

Entón agora eu teño un gravar só "ouch". Entón agora eu estou indo a ir adiante e chamar iso de "ai". Eu estou indo a volver para os meus guións, e agora aviso hai este bloque que se chama reproducir o son "Miau" ou reproducir o son "ai". Eu estou indo a arrastrar iso, e onde debo poñer isto para efecto cómico? É, polo que agora é unha especie de cesta, porque agora este block-- observe como este "na beira, salto "é unha especie de auto-contido. Entón eu teño fixar iso. Deixe-me ir adiante e facelo. Déixeme librarse desa e volver para a nosa orixinal, máis deliberada funcionalidade. Entón, "se tocar bordo, a continuación," Eu quero a xirar, como Victoria proposto, 180 graos. E quero xogar o son "ouch" alí? 

Si, ter en conta que é fóra este bloque amarelo. Entón, iso tamén sería unha erro, pero teño notado iso. Entón eu vou arrastralo ata aquí, e aviso agora dentro do "si". Así, o "si" é ese tipo de como blot brazo-like que só vai facer o que está dentro dela. Entón agora eu reducir en o risco de annoying-- 

Ordenador: Ai, ai, ai. 

DAVID Malan: E só vai durar para sempre. Agora é só para acelerar as cousas aquí, deixe-me ir adiante e abrir-se, imos dizer-- déixeme ir a algún do meu propio material de clase. E déixeme abrir, imos dicir, este un feito por un dos nosos compañeiros de ensino un par de anos. Entón, algúns de vostedes poden lembrar este xogo doutros tempos, e é realmente notable. Aínda que nós fixemos o máis simple de programas de agora, imos considerar o que iso realmente parece. Déixeme bateu xogar. 

Entón, neste xogo, temos un ra, e utilizando a frecha keys-- toma pasos máis grandes que eu recorde-- Teño control sobre ese sapo. E o obxectivo é atravesar o movemento estrada sen executar para os coches. E imos see-- se eu ir ata aquí, eu ten que esperar por un rexistro para rodar. Isto parece un erro. Este é un tipo de erro. Todo ben. Estou neste aquí, alí, e entón segue indo ata obter toda as ras para os lírios. Agora isto pode parecer tanto máis complexa, pero imos tentar romper este abaixo mentalmente e verbalmente os seus bloques compoñentes. Entón, hai probablemente un puzzle peza que non vimos aínda pero que responde aos mandos das teclas, a cousas que eu bati o teclado. 

Entón, hai probablemente algún tipo de bloque que di, a clave é igual a anterior, a continuación, facer algo con Scratch-- quizais movelo 10 pasos desta forma. Se cursor abaixo é presionado, mover 10 pasos Deste xeito, ou á esquerda, mover 10 pasos Deste xeito, o 10 pasos que. Virei claramente o gato nun sapo. Entón, iso é só onde a traxe, como chamadas de raspadinhas ele-- nós acaba de importar unha imaxe do sapo. 

Pero o que máis está a suceder? Que outras liñas de código, o que as outras pezas do puzzle fixo Blake, o noso ensino do compañeiro, utilizar neste programa, aparentemente? O que está facendo todo move-- o que de programación construír? 

Movemento, de xeito que o sure-- mover o bloque, con certeza. E que é o que o bloque movemento Dentro, máis probable? Si, algún tipo de loop, quizais un sempre bloquear, quizais unha repetición block-- repetir ata que o bloque. E iso é o que está a facer os rexistros e os lírios e todo máis movemento e cara atrás. É só a suceder sen parar. 

Por que algúns dos coches movendo máis rápido que os outros? Que é diferente sobre estes programas? Si, probablemente algúns deles están a tomar máis pasos dunha soa vez e algúns deles menos etapas dunha soa vez. E o efecto visual é rápido contra lento. 

¿Que pensas que pasou? Cando eu teño o meu sapo todo o camiño do outro lado da rúa e do río na almofada de lírio, algo digno de nota pasou. Que pasou así que eu fixen iso? Deixou. Aquel sapo parou, e Eu teño unha segunda ra. Entón, o construto debe ser usado alí, o recurso? 

É, por iso hai algún tipo de "Se" condicionar-se alí, tamén. E pasa out-- non vimos isto-- pero hai outros bloques en que hai pode dicir que, se está tocando algo na pantalla, se está tocando a almofada de lírio ", entón". E, a continuación, que é cando facer a segunda ra aparecer. Así, aínda que este xogo é certamente moi antigo, aínda que a primeira vista hai tanta cousa suceder Blake on-- e non chicotear isto en dous minutos, probablemente levou varios horas para crear este xogo con base na súa memoria ou vídeos da versión de pasado del. Pero todas estas pequenas cousas indo na pantalla de forma illada resumen-se a estes moi sinxelo movementos constructs-- ou declaracións como xa discutir, loops e condicións, e é sobre iso. Hai algunhas outras características extravagantes. Algúns deles son puramente estética ou acústico, como os sons Só xogou con. Pero para a maior parte, vostede ten nesta lingua, risco, todos de fundamental bloques de construción que teñen en C, Java, JavaScript, PHP, Ruby, Python, e calquera número de outras linguas. Calquera dúbida sobre cero? Todo ben. Polo tanto, non imos mergullar máis fondo a cero, que é benvido este fin de semana, especialmente se ten fillos ou sobriños e sobriñas e tal, presenta-los a cero. É realmente un marabillosas lúdica ambiente, con, como os seus autores, teitos moi altos. Aínda que comezou con moi detalles de baixo nivel, pode realmente facer algo con el, e este é quizais unha demostración de exactamente isto. 

Pero imos agora facer a transición cara un pouco máis problemas sofisticados, se quixeren, coñecida como "busca" e "Selección", de xeito máis xeral. Tivemos este libro de teléfono earlier-- aquí outra só para discussion-- que fomos capaces de busca de forma máis eficiente porque dun presuposto significativo. E só para quedar claro, o que suposición era eu facendo Ao buscar a través deste libro de teléfono? Que Mike Smith estaba o libro de teléfono, aínda que sería capaz de tratar o escenario sen el alí se eu simplemente deixou prematuramente. O libro é alfabético. E iso é moi xeneroso suposición, porque iso significa someone-- Eu son do tipo de corte de esquina, como eu son máis rápido porque alguén outros fixeron unha chea de traballo duro para min. 

Pero e se o teléfono libro foron non separados? Quizais Verizon teño preguiza, só xogou nomes e números de todos dentro quizais na orde en que asinou o servizo de teléfono. E canto tempo leva-me para atopar alguén como Mike Smith? 1.000 páxinas de teléfono book-- cantas páxinas que eu teño que ollar a través? 

Todos eles. Es tipo de fóra da sorte. Vostede literalmente ten que mirar para todos os páxina se o libro de teléfono é só ordenados aleatoriamente. Pode ter sorte e atopar Mike na primeira páxina, porque foi o primeiro cliente para solicitar o servizo de teléfono. Pero pode ser a última tamén. 

Entón orde aleatoria non é bo. Entón, supoña que temos para ordenar a libro de teléfono ou nos datos xerais tipo que se nos deu. Como podemos facer iso? 

Ben, deixe-me tentar un exemplo simple aquí. Deixe-me ir adiante e tirar unha algúns números no cadro. Supoña que os números que temos son, digamos, catro, dous, un e tres. E, Ben, clasificar estes números para nós. 

OK, bo. Como fixo iso? Todo ben. Entón comeza coa menor valor e o máis alto, e iso é realmente boa intuición. E entender que nós os seres humanos son realmente moi bo en resolver problemas así, polo menos, cando os datos é relativamente pequena. Así que comeza a ter centos de números, miles de números, millóns de números, Ben probablemente Non podería facelo tan rápido, asumindo que había lagoas nos números. Moi fácil de contar ata un millón Se non, pode levar. 

Así, o algoritmo soa como Ben usado agora Foi busca polo menor número. Así, aínda que nós, humanos, pode levar en unha morea de información visuais, un ordenador é, en realidade algo máis limitada. O ordenador non pode mirar para un byte de cada vez ou quizais catro bytes de cada vez-- nos días de hoxe é posible 8 bytes de cada vez-- pero un número moi pequeno de bytes nun determinado momento. 

Entón, unha vez que realmente temos catro valores separados aqui-- e pode pensar en Ben como tendo antolhos se fose un ordenador, tales que non pode ver nada dun número nunha vez-- por iso, xeralmente pode asumir, como en Inglés, imos ler de dereita a esquerda. Así, o primeiro número Ben probablemente parecía logo foi de catro e moi rapidamente entender que é un moi grande number-- déixeme seguir buscando. 

Hai dous. Espera un minuto. Dous é menor que catro. Vou lembrar. Dous é agora menor. Agora um-- que é aínda mellor. Isto é aínda menor. Vou esquecer dous e lembra-se un momento. 

E podería deixar de mirar? Ben, podería baseadas nesta información, pero sería mellor busca resto da lista. Porque o que si é cero estaban na lista? E se negativo alguén fose na lista? El só sabe que a súa resposta é correcto se é extensa comproba a lista enteira. Entón miramos o resto deste. Three-- que era unha perda de tempo. Demos azar, pero eu estaba Aínda correcta de facelo. E entón agora presuntamente seleccionado o número máis pequeno e só colocar-lo no inicio da lista, como eu vou facer aquí. Agora, o que fixo despois, aínda non pensar niso case a este punto? Repita o proceso, de xeito algún tipo de loop. Hai unha idea familiar. Entón aquí é catro. Isto é actualmente o máis pequeno. Isto é un candidato. Non máis. Agora que vin dous. Ese é o seguinte elemento máis pequeno. Three-- que non é menor, entón, agora Ben pode arrincar os dous. 

E agora nós repita o proceso, e de curso de tres é levado para fóra a continuación. Repita o proceso. Catro é levado cara fóra. E agora estamos fóra dos números, así que a lista debe ser ordenada. 

E, de feito, este é un algoritmo formal. Un científico da computación sería chaman iso de "tipo de selección," A idea é tipo un listar iteratively-- novo e de novo e de novo seleccionando menor número. E o que é agradable sobre el é iso é tan danado intuitiva. É tan sinxelo. E pode repetir o mesmo operación de novo e de novo. É sinxelo. 

Neste caso, foi rápido, pero canto tempo fai exame realmente? Imos facelo parecer e sentir un pouco máis tedioso. Entón, un, dous, tres, catro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16-- número arbitrario. Eu só quería máis que tempo que a catro. Entón, se eu teño un todo chea de números agora --- lo non importa mesmo o que é-- Imos pensar sobre o que este algoritmo é realmente como. 

Supoña que hai números alí. Unha vez máis, non importa o que son, pero son aleatorios. Estou aplicando o algoritmo de Ben. Necesito seleccionar o menor número. Que fago? E eu vou fisicamente facelo esta vez para representalo. Mirando, mirando, mirando, mirando, mirando. Só no momento que eu chegar a o fin da lista pode Eu entendo a menor número era dous neste momento. Non está na lista. Entón, eu coloque dous. 

Que debo facer a continuación? Mirando, mirando, mirando, mirando. Agora eu atope o número sete, porque hai erros nestes números de pero só arbitraria. Todo ben. Entón agora podo tirar abaixo sete. Mirando mirando, mirando. 

Agora eu estou supondo, claro, que non fai Ben ten RAM extra, extra memoria, porque, obviamente, Estou mirando para o mesmo número. Certamente eu podería lembrar todos estes números, e iso é absolutamente certo. Pero se Ben recorda todo dos números que viu, el non fixo realmente progresos fundamentais porque xa ten a capacidade de buscar a través dos números na mesa. Lembrando todas as O número non axudan, porque pode aínda como un ordenador só ollar para, xa dixemos, un número á vez. Polo tanto, non hai ningún tipo de fraude alí que pode aproveitar. 

Entón, en realidade, como eu seguir buscando a lista, Eu literalmente só ten que seguir adiante e cara atrás a través del, arrincando a seguinte menor número. E como pode tipo de inferir dos meus movementos parvos, isto só queda moito tedioso moi rapidamente, e eu parecen estar indo cara atrás e adiante, para atrás e para adiante un pouco. Agora, para ser xusto, eu non teño que ir así como, así, imos see-- para ser xusto, Non teño que camiñar bastante como moitos pasos de cada vez. Xa que, por suposto, como I seleccionar números da lista, a lista restante está quedando máis curto. 

E así imos pensar sobre cantos pasos eu estou realmente traipsing través de cada vez. Na primeira situación tivemos 16 números, e así por maximally-- imos só facelo por un discussion-- Tiven que ollar a través de 16 números para atopar a menor. Pero unha vez eu arrincado menor número, como tempo durou a lista restante, por suposto? Só 15. Entón, cantos números fixo Ben ou eu teño ollar a través da segunda vez? 15, só para ir e atopar o menor. Pero agora, por suposto, a lista é, Tamén, menor que era antes. Entón, como moitos pasos fixo I ten que tomar a seguinte visita? 14 e despois 13 e despois 12, ademais de punto, punto, punto, ata que eu estou á esquerda con só un. Polo tanto, agora un científico da computación sería preguntar, así, o que fai que todos iguais? En realidade, é igual a algún formigón número que seguramente poderiamos facer aritmeticamente, pero queremos falar sobre a eficiencia de algoritmos un pouco máis como unha fórmula, independente de canto tempo a lista é. 

E así que sabe o que? Este é 16, pero como dixen antes, imos chamar o tamaño do problema n, onde n é un número. Quizais sexa 16, quizais sexa tres, quizais sexa un millón. Non sei. Eu non me importa. O que realmente quero é unha fórmula que poida usar para comparar este algoritmo contra outros algoritmos que alguén pode reclamar son mellores ou peores. 

Así, ao parecer, e só eu sei que isto de escola, que iso realmente funciona para o mesmo que n máis de n un sobre dous. E isto ocorre para igualar, de Por suposto, n ao cadrado máis n máis de dous. Entón, se eu quería unha fórmula por cantos pasos estaban implicados en ollar para todos deses números novo e de novo e de novo e de novo, eu diría é n ao cadrado máis n máis de dous. Pero vostede sabe o que? Isto só parece confuso. Realmente quero un sentido xeral das cousas. E pode lembrar de ensino medio que non é a noción de expiración maior orde. Cal destes termos, a n cadrado, a N, ou a media, ten o maior impacto no tempo? O maior n recibe, que destes asuntos máis? 

Noutras palabras, se eu conectar nun millón, n ao cadrado será máis probable o factor dominante, Unha vez que un millón de veces en si é moi grande que máis un adicional millóns. Entón vostede sabe o que? Este é un tal danado gran número se cadrado dun número. Iso realmente non importa. Nós só imos cruz que fóra e esquece. E así un científico da computación diría que a eficiencia deste algoritmo é da orde de n ao cadrado Quero dicir realmente unha aproximación. É unha especie de aproximadamente n ao cadrado. Co paso do tempo, a maior e maior n recibe, este é unha boa estimación para o que o a eficiencia ou a falta de eficiencia deste algoritmo é realmente. E eu derivar que, por suposto, de realmente facer a matemática. Pero agora eu só estou acenando as mans, porque eu só quere un sentido xeral deste algoritmo. 

Entón, usando a mesma lóxica, non obstante, imos considerar outro algoritmo xa mirou at-- busca lineal. Cando eu estaba a buscar ao teléfono book-- non clasificándose o, buscando a través do teléfono book-- mantivemos dicindo que era 1.000 pasos, ou 500 pasos. Pero imos xeneralizar iso. Se hai n páxinas o libro de teléfono, o que é o tempo de execución ou o eficiencia da busca lineal? E da orde de cantos pasos para atopar Mike Smith usando a busca lineal, a primeiro algoritmo, ou mesmo o segundo? 

No peor dos casos, o Mike é ao final do libro. Entón, se o libro de teléfono ten 1.000 páxinas, dixemos última vez, no peor caso, isto pode levar máis ou menos como moitas páxinas para atopar Mike? Como 1000. É un límite superior. É unha peor situación posible. Pero, de novo, nós estamos movendo para lonxe desde números como 1.000 agora. É só n. 

Entón, cal é a conclusión lóxica? Buscar Mike nun teléfono libro que ten n páxinas pode levar, no peor caso, cantos pasos na orde de n? E, de feito un ordenador científico diría que o tempo de execución, ou o o desempeño ou a eficiencia ou ineficiencia, dun algoritmo como unha investigación lineal está na orde de n. E podemos aplicar o mesmo lóxica de atravesar algo fóra como eu fixen co segundo algoritmo que tivemos co libro de teléfono, onde fomos dúas páxinas á vez. 

Entón 1000 páxina do libro de teléfono pode levar 500 páxinas voltas, máis un dobrar un pouco para atrás. Polo tanto, se un libro de teléfono ten n páxinas, pero nós estamos facendo dúas páxinas por vez, que é aproximadamente o que? N ao longo de dous, de xeito que é como n máis de dous. Pero eu fixen a petición dun hai pouco que n ao longo dois-- iso é medio mesmo que n. É só un factor constante, científicos da computación diría. Nós só centrar as variables, realmente-- os maiores variables na ecuación. 

investigación de modo lineal, sexa feito un páxina de cada vez ou dúas páxinas por vez, é unha especie de fundamentalmente o mesmo. Aínda é da orde de n. Pero reivindicado coa miña foto anterior que a terceira algoritmo non foi lineal. Non era unha liña recta. Foi que liña curva, eo fórmula alxébrica había o que? Rexistro de n-- tan rexistro base dous n. E non debemos ir moi moitos detalles sobre logaritmos de hoxe, pero a maioría dos científicos da computación non estaba mesmo dicirlle que é a base. Por todo só factores constantes, por así dicir, só pequenas diferenzas numéricas. E así esta sería unha moi común camiño para ordenador particular formais científicos unha placa ou programadores nun cadro branco en realidade, argumentando que algoritmo que usarían ou que a eficiencia do seu algoritmo é. 

E iso non é necesariamente algo vostede discute en calquera gran detalle, pero un bo programador é alguén que ten unha base sólida, formal. É capaz de falar con Lo neste tipo de forma e realmente facer argumentos cualitativos como a razón pola que un algoritmo ou unha peza de software é superior, dalgunha forma a outra. Porque podería certamente basta con executar o programa dunha persoa e contar o número de segundos hai que para clasificar algúns números, e pode realizar algúns O programa de outra persoa e contar o número de segundos que leva. Pero esta é unha forma máis xeral, que pode usar para analizar algoritmos, se quixeren, só de papel ou só verbalmente. Sen mesmo executalo, sen mesmo tentando entradas de mostra, pode só razoar con el. E así, coa contratación de un creador ou téndolle especie de discutir con vostede porque o seu algoritmo, o seu segredo salsa para buscar millóns de páxinas web para o seu empresa é mellor, estes son os tipos de argumentos que debería idealmente ser capaz de facer. Ou, polo menos, estes son tipo de cousas que viría en discusión, na menos nunha discusión moi formal. Todo ben. Entón Ben propuxo algo chamado de selección de clasificación. Pero eu vou propoñer que hai outras formas de facelo, tamén. O que eu non me gusta moito sobre o algoritmo de Ben é que continuou camiñando, ou téndome andar, e cara atrás e de atrás e cara adiante e cara atrás e cara adiante. E se en vez eu fose facer algo así como eses números aquí e eu fose só para tratar con cada número á súa vez, como eu estou dado? 

Noutras palabras, é aquí A miña lista de números. Catro, un, tres, dous. E eu vou facer o seguinte. Eu estou indo a introducir os números onde eles pertencen, en vez que seleccionar os un de cada vez. Noutras palabras, aquí é o número catro. 

Aquí está a miña lista orixinal. E eu vou manter esencialmente unha nova lista aquí. Polo tanto, esta é a lista de idade. Esta é a nova lista. Eu vexo o número catro en primeiro lugar. Miña nova lista é inicialmente baleiro, por iso é o caso trivialmente que catro está a lista variada. Estou só tomando o número que eu son dado, e eu estou poñendo isto na miña nova lista. 

É esta nova lista ordenada? Si. É estúpido porque hai só un elemento, pero é absolutamente clasificadas. Non hai nada fóra do lugar. É máis interesante, este algoritmo, cando pasar á seguinte etapa. 

Agora eu teño un. Así, unha, por suposto, pertence ao inicio ou no fin desta nova lista? O comezo. Entón eu teño que facer un traballo agora. Fun tomar uns liberdades co meu marcador por só deseñar cousas onde quero que, pero iso non é realmente que nun ordenador. Un ordenador, como se sabe, ten RAM, ou memoria de acceso aleatorio, e iso é un byte e outro byte e outro byte. E se tes un gigabyte de RAM, ten mil millóns de bytes, pero eles están fisicamente nun único lugar. Non pode simplemente mover cousas arredor deseñando a no taboleiro onde quere. Entón, se a miña nova lista ten catro locais na memoria, Desafortunadamente a catro é xa no lugar incorrecto. 

Así, para introducir o número un Non podo simplemente deseña-lo aquí. Este lugar de memoria non existe. Iso sería facer trampas, e eu teño sido trampas pictoricamente por uns minutos aquí. Entón, en realidade, se eu queira poñer un aquí, Teño que copiar temporalmente os catro e logo poñer un alí. 

Isto é bo, iso é correcto, que é tecnicamente posible, pero entende que é un traballo adicional. Non só tes que poñer o número no lugar. A primeira vez que tivo que mover unha número, a continuación, colocar-lo no lugar, entón eu medio que duplicou a miña cantidade de traballo. Polo tanto, manter isto presente. 

Pero agora estou feito con este elemento. Agora quero incorporarse o número tres. Onde, por suposto, pertence? No medio. Non pode enganar máis e só poñelas alí, porque, de novo, esta memoria é en lugares físicos. Entón eu teño que copiar os catro e poñer os tres aquí. Non é un gran negocio. É só unha etapa extra novamente-- sente moi barato. 

Pero agora eu paso para os dous. Os dous, por suposto, pertence aquí. Agora comeza a ver como o traballo pode acumular. Agora o que eu teño que facer? Si, eu teño que ir a catro, Eu, entón, ten que copiar os tres, e agora podo inserir os dous. E a captura con este algoritmo, curiosamente, que supoña que temos unha forma máis extrema caso en que é, digamos oito, sete, seis, cinco, catro, tres, dous, un. Isto é, en moitos contextos, o peor escenario, porque o danado é, literalmente, para tras. 

realmente non afecta o algoritmo de Ben, porque na selección de Ben tipo que vai continuar indo e volvendo pola lista. E porque estaba sempre á procura a través de toda a lista restante, non importa en que os elementos son. Pero, neste caso, coa miña inserción approach-- imos tentar iso. 

Entón, un, dous, tres, catro, cinco, seis, sete, oito. Un dous tres catro, cinco, seis, sete, oito. Vou tomar a oito, e onde podo poñelas? Ben, no inicio da miña lista, porque esta nova lista é ordenada. E eu atravesa-la fóra. 

Onde debo poñer o sete? Danado. Necesita ir alí, entón Teño que facer algunha copia. E agora a sete vai aquí. Agora eu pasar ao seis. Agora é aínda máis traballo. 

Oito ten que ir aquí. Sete ten que ir aquí. Agora, a seis pode ir aquí. Agora eu coller a cinco. Agora, a oito ten que ir aquí, sete ten que ir aquí, seis ten que ir aquí, e agora os cinco e repita. E eu estou moi ben movéndose o constantemente. 

Así, ao final, este algorithm-- imos chamalo de inserción sort-- realmente ten unha chea de traballo, tamén. É só diferente tipo de traballo de Ben. O traballo de Ben tiña-me ir e cara atrás todo o tempo, seleccionar o seguinte menor elemento novo e de novo. Por iso, foi este tipo moi visual do traballo. 

Este outro algoritmo que aínda é correct-- vai comezar o traballo done-- só cambia a cantidade de traballo. Parece que inicialmente está aforro, porque está só tratar con cada elemento diante sen andar todo o camiño a través da lista como Ben era. Pero o problema é, sobre todo nestes casos tolo onde todo está de volta, é só un tipo de adiando o traballo duro ata que ten que corrixir os seus erros. 

E por iso, se pode imaxinar este oito e sete anos e seis e cinco e despois de catro e tres e dous movendo o seu camiño a través da lista, temos só cambiou o tipo de traballo que estamos facendo. No canto de facelo no inicio da miña iteración, Eu estou facendo iso só na final de cada iteración. Así, verifícase que este algoritmo, Tamén, xeralmente chamado de ordenación por inserción, é tamén a orde de n ao cadrado. Realmente non é mellor, non é mellor en todo. 

Con todo, hai unha terceira visión Quere fomentar-nos a considerar, que é esta. Entón supoño miña lista, por simplicidade unha vez máis, é de catro, un, tres, dois-- só catro números. Ben tivo boa intuición, boa intuición humana antes, polo que se fixa o conxunto listar eventually-- tipo de inserción. I persuadiu connosco xunto. Pero imos considerar o maneira máis sinxela de resolver esta lista. 

A lista non está ordenada. Por que? En inglés, explicar por que En realidade non é clasificada. O que significa a menos ordenados? 

ESTUDANTE: Non é secuencial. 

DAVID Malan: Non secuencial. Dáme un exemplo. 

ALUMNO: Pon-as en orde. 

DAVID Malan: OK. Dáme un exemplo máis específico. 

ALUMNO: orde crecente. DAVID Malan: Orde non ascendente. Ser máis preciso. Non sei o que quere dicir con ascendente. O que hai de malo? 

ALUMNO: O menor da números non está no primeiro espazo. 

DAVID Malan: menor número de non no primeiro espazo. Sexa máis específico. Estou empezando a coller. Estamos contando, pero o que está fóra de orde aquí? 

ALUMNO: secuencia numérica. DAVID Malan: secuencia numérica. tipo de todos de mantemento iso aqui-- nivel moi alto. Só literalmente me dicir o que é mal como unha forza de cinco anos de idade. 

ALUMNO: Máis un. 

DAVID Malan: ¿Que é iso? 

ALUMNO: Máis un. 

DAVID Malan: O que quere dicir un? Déame unha persoa distinta de cinco anos de idade. O que hai de malo, nai? O que está mal, pai? O que quere dicir que non é ordenada? 

ALUMNO: Non é o lugar seguro. 

DAVID Malan: Cal é non no lugar seguro? 

ALUMNO: Four. DAVID Malan: OK, bo. Entón, catro non é onde debería estar. En particular, é ese dereito? Catro e un, o primeiro dous números que vexo. Isto é certo? Non, están fóra de orde, non? De feito, creo que agora sobre un ordenador, tamén. Pode só ollar para quizais un, quizais dúas cousas á once-- e, de feito, só unha cousa á vez, pero pode, polo menos ollar a unha cousa, entón o seguinte ben próximo a ela. 

Entón son estes en orde? Por suposto que non. Entón vostede sabe o que? Por que non tomamos bebé pasos corrixir este problema en vez de facer estes fantasía algoritmos, como Ben, onde É unha especie de resolve-lo por Looping través da lista en vez de facer o que eu fixen, onde Eu medio que fixa-lo como nós imos? Nós só literalmente romper a noción de orde numérica order--, chamalo de todo o que want-- para estas comparacións de pares. 

Catro e un. É esta a orde correcta? Entón imos solucionar isto. Un e catro, e logo imos só copiar isto. Todo ben, bo. Fixei un e catro. Tres e dous? Non. Deixe miñas palabras coincidir cos meus dedos. Catro e tres? 

Non é en orde, entón eu vou para facer un, tres, catro, dous. OK, bo. Agora, catro e dous? Necesitamos corrixir isto, tamén. Entón, un, dous, tres, catro. Entón, se clasifica? Non, pero é o máis preto de ordenar? 

É, xa que nós modificado este erro, nós modificado este erro, e nós modificado este erro. Por iso, fixo tres erros, sen dúbida. Aínda realmente non parece ordenada, pero é obxectivamente máis preto de ordenado porque fixa algúns deses erros. 

Agora o que fago agora? I tipo de alcanzar o fin da lista. Eu parecía fixado os erros, pero non. Porque neste caso, algúns números podería borbulhava máis preto para outros números aínda están fóra de orde. Entón, imos facelo de novo, e eu vou só facelo no lugar neste momento. Un e tres? Está ben. Tres e dous? Claro que non, entón imos cambiar isto. Entón, dous, tres. Tres e catro? E agora imos ser particularmente pedante aquí. É clasificado? Vostede humanos sabe que está clasificada. 

Eu debería tentar de novo. Entón, Olivia está propondo que tente de novo. Por que? Porque un ordenador non ten o luxo dos nosos ollos humanos de só mirando traseira-- OK, eu son feito. Como o ordenador determinar que a lista está clasificado? Mecánicamente. 

Eu debería pasar por unha vez máis, e só se I non faga / atopa algún erro pode I entón concluír que o equipo, si, somos bos de ir. Así, un e dous, dous e tres, tres e catro. Agora podo definitivamente dicir que este é clasificadas, porque eu non fixo cambios. Agora sería un erro e só tolo si, o ordenador, Pregunta esas mesmas preguntas novo esperando respostas diferentes. non debería pasar. 

E entón agora a lista é ordenada. Desafortunadamente, duración de este algoritmo tamén é n cadrado. Por que? Porque ten n números, e na peor caso ten que mover n números n veces, porque ten que seguir de volta para comprobar e corrixir potencialmente estas cifras. E podemos facer máis análise formal, tamén. 

Entón, todo isto é para dicir que tomamos tres enfoques diferentes, unha deles inmediatamente intuitiva fóra do pau de Ben á miña inserción suxerido tipo a este onde tipo de perder de vista o bosque para as árbores inicialmente. Pero, entón, se tomar un paso atrás, voila, temos fixo a noción de clasificación. Polo tanto, este é, atrévome a dicir, un nivel máis baixo posible que algúns dos outros algoritmos, pero imos ver se non podemos ver estes a través deste. 

Entón, este é un bo programa que alguén escribiu usando barras de cores que hai de vai facer o seguinte para nós. Cada unha destas barras representa un número. Taller barra, maior o número, menores do bar, Canto menor o número. Así, idealmente, queremos unha boa pirámide onde comeza pequeno e recibe gran, e iso significaría que estas barras son clasificadas. Entón, eu estou indo a ir adiante e elixir, por exemplo, o algoritmo de Ben tipo selección first--. 

E teña en conta o que está facendo. A forma como eles optaron por facer ver este algoritmo é que, como eu era camiñando a través da miña lista, este programa está camiñando a través da súa lista de números, destacando en cada rosa número que está mirando. E o que está a piques de pasar agora? 

O menor número de que I é Ben atopou de súpeto é movido para o inicio da lista. E noten que fixeron evict o número que estaba alí, e iso é perfectamente ben. Non entrar nese nivel de detalle. Pero hai que poñer este número en algún lugar, por iso, só mudouse para o lugar aberto que foi creado. Entón eu vou para acelerar este -Se, porque se non, fai-se rapidamente moi tedioso. Animación speed-- alí imos nós. Entón, agora mesmo principio Estaba aplicando, pero Pode comezar a sentir o algoritmo, se vai, ou velo un pouco máis claramente. E este algoritmo ten o efecto de seleccionar o seguinte elemento máis pequeno, entón vai comezar a velo rampla ata a esquerda. E en cada iteración, como eu proposto, que fai algo menos de traballo. Non ten que percorrer todo o camiño de volta á extrema esquerda da lista, porque xa coñece os son clasificadas. Entón, que tipo de parece que é acelerando, aínda que cada paso é tendo a mesma cantidade de tempo. Hai poucas etapas restantes. E agora pode tipo de sentir a algoritmo de limpeza do final do mesmo, e de feito xa está clasificada. 

Entón ordenación por inserción é todo feito. Eu necesidade de re-embaralhar a matriz. E teña en conta Só pode manter randomização-lo, e teremos un achegamento das a mesma visión, ordenación por inserción. Déixeme retarda-lo para aquí. Imos comezar que máis. Parar. 

Imos saltar catro. Alí imos nós. Randomize eles matriz. E aquí vai-- tipo de inserción. Xogar. Teña en conta que está lidando con cada elemento que atopa inmediatamente, pero se pertence a o aviso de lugar incorrecto todo o traballo que ten que pasar. Temos que seguir cambiando máis e máis elementos para abrir espazo para o que queremos poñer no lugar. 

Entón, nós estamos focando en extremo esquerda da lista única. Lembre que non temos sequera mirou at-- nós non destacaron en calquera cousa rosa cara á dereita. Estamos só lidando con os problemas a medida que avanzamos, pero estamos creando unha morea de traballar para nós aínda. E así se acelerar este proceso agora a estar completa, el ten unha sensación diferente para el, de feito. É só incidir sobre o fin esquerdo, pero facendo un pouco máis de traballo como needed-- tipo de cousas suavización máis, arranxar as cousas, pero tratar última instancia, co cada elemento de un de cada vez ata chegar ao as-- ben, nós Todos sabemos como iso vai acabar, por iso é un pouco nada asombroso quizais. 

Pero a lista na end-- spoiler-- será resolto. Entón, imos ollar para un último. Non podemos ignorar o momento. Estamos case alí. Dúas para ir, un para ir. E listo. Excelente. 

Entón agora imos facer unha última, re-randomização con bubble sort. E teña en conta aquí, sobre todo si retarda-lo abaixo, iso manter mergullando totalmente. Pero teña en conta que só fai pairwise tipo comparisons-- de solucións locais. Pero así que chegamos a o fin da lista en cor rosa, o que vai ter que pasar de novo? Si, vai ter que comezar de novo, porque só erros de pares fixos. E que pode revelar aínda outros. E entón se acelerar este proceso, vai ver que, así como o nome indica, menor elements-- ou mellor, os elements-- maiores empezan a burbulla ata o cumio, se quere. E os elementos son menores empezando a burbulla para abaixo á esquerda. E, de feito, este é o tipo de o efecto visual ben. E así que vai acabar terminando dun xeito moi semellante, tamén. 

Non temos a habitar nun presente particular. Déixeme abrir iso agora tamén. Hai algúns outros algoritmos de ordenación en todo o mundo, algúns dos cales son capturados aquí. E, sobre todo, para os alumnos que non son necesariamente visual ou matemáticas, como fixemos antes, podemos Tamén facelo audially asociar un son con iso. E só por diversión, aquí está un algúns algoritmos diferentes, e un deles, en especial, está Vai notar é chamado de "merge sort". 

É realmente unha fundamentalmente mellor algoritmo, de tal forma que merge sort, un dos os que está a piques de ver, non é orde de n ao cadrado. É na orde rexistro de n veces de n, que é realmente menor e, polo tanto, máis rápido que os outros tres. E hai un par outra bobas que veremos. 

Entón, imos con algún son. Esta é a ordenación por inserción, polo que de novo é só xestionar os elementos como eles veñen. Este é bubble sort, polo que é considerándose os pares de cada vez. E, de novo, os maiores elementos están burbullas ata o cumio. 

Logo tipo de selección. Este é o algoritmo de Ben, onde novo está seleccionando de forma iterativa o seguinte elemento máis pequeno. E unha vez máis, agora pode realmente escoitar que está acelerando, pero só na medida como está facendo cada vez menos traballar en cada iteración. Este é o máis rápido un, merge sort, que é clasificar grupos de números xuntos e logo, combina-las. Así look-- esquerda metade xa están clasificados. 

Agora que está clasificando a metade dereita, e agora vai combina-los nun só. Isto é algo chamado "Gnome tipo." E pode tipo de ver que vai alí e para aquí, que fixa o traballo un pouco aquí e antes de proceder á nova obra. E iso. Hai outro tipo, que é Realmente só para fins académicos, chamado "tipo estúpido", que leva os seus datos, clasifícase o de forma aleatoria, e comproba se está clasificada. E se non é, re-ordena-lo azar, comproba se está clasificado, e se non se repite. E, en teoría, probabilisticamente isto vai rematar, pero despois de un pouco de tempo. Non é o máis eficiente de algoritmos. Así, calquera preguntas sobre os algoritmos particulares ou nada relacionados alí, tamén? 

Ben, imos agora desmembrar o que todos estas liñas son que teño deseñado eo que eu estou supondo que o ordenador pode facer debaixo do capó. Eu diría que todos estes números Eu sigo drawing-- precisan para obter almacenado nalgún lugar na memoria. Imos librar dese cara agora, tamén. 

Así, unha parte da memoria nunha Computador-- tan RAM DIMM é o que buscou onte dobre memoria en liña module-- parécese iso. E cada unha destas pequenas fichas negras é un número de bytes, normalmente. E entón os pinos de ouro son como o fíos que conectan ao ordenador, ea placa de silicio verde é só o que mantén todo en conxunto. Entón o que iso realmente significa? Se eu tipo de deseñar esta mesma imaxe, imos supor que a sinxeleza que este DIMM, dobre Liña Memory Module, é un gigabyte de memoria RAM, un gigabyte de memoria, que é o número de bytes en total? Un gigabyte é cantos bytes? Máis que iso. 1124 é kilo, 1000. Mega é millóns. Giga é mil millóns. 

Eu estou mentindo? podemos ata ler a etiqueta? Isto é, en realidade, 128 gigabytes, polo que é máis. Pero imos finxir que iso é só un gigabyte. Entón isto significa que hai mil millóns bytes de memoria dispoñible para min ou 8 millóns de bits, pero imos para falar en termos de bytes agora, avanzar. 

Entón, o que iso significa que o que un byte, este é un byte, este é un byte, e se realmente queriamos para ser máis específico, teriamos que deseñar un billón de pequenos cadrados. Pero o que significa isto? Ben, deixe-me só aumentar en nesta imaxe. Se eu teño algo que parece así agora, iso é catro bytes. 

E así eu podería poñer catro números aquí. Un dous tres catro. Ou eu podería poñer catro letras ou símbolos. "Hey!" podería ir para a dereita alí, porque cada unha das cartas, discutir anteriormente, Pode ser representado con oito bits ou ASCII ou un byte. Polo tanto, noutras palabras, pode poñer 8 mil millóns de cousas dentro dun presente da vara da memoria. Agora o que iso supón para poñer as cousas de volta a volta atrás na memoria como esta? Isto é o que un programador chamaría dun "array". Nun programa de ordenador, non pensa sobre o hardware subxacente, per se. Só pensa en si mesmo como tendo acceso a un total mil millóns de bytes, e pode que queira con el. Pero por conveniencia normalmente é útil para manter o seu dereito de memoria á beira do outro como este. Entón, se eu aumentar o zoom en isto-- porque certamente non vai deseñar un billón de pequenos squares-- imos supor que este cadro representa esta vara da memoria agora. E eu vou só chamar a todos cantos o meu marcador acaba me dando aquí. Polo tanto, agora temos unha vara de memoria na tarxeta que ten un, dous, tres, catro, cinco, seis, un, dous, tres, catro, cinco, seis, seven-- así 42 bytes de memoria sobre o total da pantalla. Grazas. Si, fixen a miña aritmética dereita. Así, 42 bytes de memoria aquí. Entón o que iso realmente significa? Ben, un programador de ordenador sería realmente xeral pensa deste como memoria endereçável. Noutras palabras, cada unha delas locais na memoria, en hardware, ten un enderezo único. 

Non é tan complexo como un Brattle Square, Cambridge, Mass., 02138. Ao contrario, é só un número. Este é byte número cero, é dicir un, é dicir dous, isto é tres, e esta é de 41. Espera un minuto. Eu penso que eu dixen 42 un momento atrás. Comecei a contar desde cero, de xeito que é realmente correcto. Agora non temos realmente deséñase la como unha rede, e se deseña-lo como unha reixa Creo que as cousas realmente obter un pouco erro. O que un programador faría, na súa propia mente, xeralmente pensan desta memoria como é como unha fita, como un anaco de cinta adhesiva que só vai sobre e sobre para sempre ou ata quedar sen memoria. Así, un xeito máis común para debuxar e só pensar sobre a memoria sería a de que esta é cero bytes, un, dous, tres, e logo, punto, punto, punto. E ten 42 destes bytes total, o mesmo aínda permanece pode realmente ser algo máis como este. 

Entón, se vostede pensa agora do seu memoria como esta, así como unha cinta, iso é o que un programador de novo chamaría dunha matriz de memoria. E cando quere realmente gardar algo en memoria dun ordenador, normalmente facer cousas tenda back-to-back to back-to-back. Entón, estamos a falar de números. E cando eu quería para resolver problemas como catro, un, tres, dous, aínda que eu estaba só un debuxo só o número catro, un, tres, dous no bordo, o ordenador faría Realmente ten esta configuración na memoria. 

E o que sería a carón do dous na memoria do ordenador? Ben, non hai ningunha resposta a iso. Nós realmente non sabemos. E desde que a O ordenador non precisa del, non se preocupe que é o seguinte aos números que se preocupa. E cando eu dixen anteriormente que un ordenador só pode ollar a un enderezo de cada vez, este é o tipo de por que. 

Non ao contrario dun rexistro xogador e unha cabeza de lectura só ser capaz de ollar para un correcto suco nun rexistro da vella escola física á vez, de xeito semellante Pode un ordenador grazas a CPU ea súa conxunto de instrucións Intel, entre cuxos instrución é lido a partir da memoria ou gardar en memory-- un ordenador só pode ollar nun lugar de cada vez-- por veces, unha combinación dos mesmos, pero realmente só un lugar de cada vez. Entón, cando estabamos facendo estes varios algoritmos, Non só estou escribindo nun vacuum-- catro, un, tres, dous. Estas cifras, en realidade, pertencen algures na memoria física. Polo tanto, hai pequeno transistores ou algún tipo da electrónica debaixo da Hood almacenar eses valores. 

E en total, cantos bits son implicados agora, só para quedar claro? Polo tanto, este é catro bytes, ou agora é 32 bits total. Entón, en realidade existen 32 ceros e aqueles que compoñen estas catro cousas. Hai aínda máis aquí, pero unha vez máis, non se preocupan con iso. 

Entón agora imos facer outra pregunta empregando memoria, pois que a finais do día está na varianza. Non importa o que pode facer o ordenador, ao final do día hardware aínda o é mesmo debaixo do capó. Cómo podería almacenar unha palabra aquí? Ben, unha palabra nun ordenador, como "Hey!" sería almacenado como esta. E se quería un máis Word, pode simplemente substituír este e dicir algo como "Ola" e tenda que aquí. 

E aquí, tamén, este contiguidade é realmente unha vantaxe, porque un ordenador pode só ler de dereita a esquerda. Pero aquí está unha pregunta. No contexto desta palabra, h-e-l-l-o, punto de exclamación, como pode o equipo sabe onde a palabra comeza e onde a palabra remata? No contexto de números, Como o ordenador saber canto tempo a secuencia de números é ou onde comeza? Ben, acontece out-- e non imos entrar moi a este nivel de detail-- ordenadores mover cousas arredor da memoria literalmente, por medio destes enderezos. Así, nun ordenador, se está escribir código para gardar cousas como palabras, o que está facendo realmente está escribindo expresións que lembran onde en memoria do ordenador estas palabras son. Entón deixe-me facer unha moi, exemplo moi sinxelo. 

Eu estou indo a ir adiante e abrir un programa de texto simple, e eu estou indo a crear un arquivo chamado hello.c. A maioría desta información que Non vou entrar en en gran detalle, pero eu estou indo a escribir un programa nese mesmo idioma, C. Isto é moito máis intimidante, Eu diría, que cero, pero é moi semellante en espírito. En realidade, estes rizado braces-- Pode tipo de pensar o que eu fixen como esta. 

Imos facelo, en realidade. Cando a bandeira verde premendo, faga o seguinte. Quero imprimir "Ola". Polo tanto, esta é agora pseudocódigo. Eu son o tipo de borrar as liñas. C, esta lingua que eu estou falando sobre, esta liña de impresión Ola convértese en realidade "printf" con algúns parénteses e un punto e coma. 

Pero é exactamente a mesma idea. E moi amigable "Cando a bandeira verde premendo" convértese en o máis arcano "void main int." E iso realmente non ten cartografía, entón eu só vou ignorar isto. Pero as claves son como o pezas do puzzle curvo como este. 

Así, pode tipo de adiviñar. Mesmo se nunca programou antes, que é o que este programa probablemente facer? Probablemente imprime Ola cun signo de admiración. 

Entón, imos tentar iso. Eu estou indo para salvalo. E isto é, de novo, unha moi ambiente da vella escola. Non podo facer clic, non pode arrastrar. Teño que escribir ordes. Entón, quero facer o meu programa, de xeito Podería facelo, como hello.c. Ese é o ficheiro que eu execute. Pero espera, eu estou falta un paso. O que dicimos é unha condición necesaria paso a unha linguaxe como C? Acaba de fonte escrita código, pero o que eu teño? Si, eu teño un compilador. Entón, o meu Mac aquí, eu teño un programa chamado GCC, o compilador GNU C, o que me permite facer isto-- vez meu código fonte en, imos chamalo, código de máquina. 

E podo ver que, outra vez, como segue, estes son os ceros e uns EU SÓ creado a partir do meu código fonte, todo ceros e uns. E se eu queira executar meu program-- isto ocorre a ser chamado a.out para reasons-- histórico "Ola". Podo executa-lo de novo. Ola, ola, ola. E parece estar funcionando. 

Pero iso significa que en algún lugar na miña memoria do ordenador son as palabras h-e-l-l o punto de exclamación. E verifícase se, como un aparte, o que un ordenador faría normalmente facer para que saiba onde as cousas comezan e end-- é vai poñer un símbolo especial aquí. E o convenio é poñer o número cero ao final dunha palabra para que vostede sabe onde realmente remata, de xeito que non manter imprimir máis e máis caracteres que realmente pretende. 

Pero o takeaway aquí, mesmo aínda que este é moi misterioso, é que é, en definitiva relativamente simple. Foille dado unha especie de cinta, un espazo en branco espazo onde pode escribir cartas. Vostede simplemente ten que ter un símbolo especial, como arbitrariamente o número cero, para poñer no extremo da as súas palabras para que o ordenador sabe, Oh, eu debería deixar a impresión despois Eu vexo o punto de exclamación. Porque a seguinte cousa alí é un valor ASCII de cero, ou o carácter nulo como alguén vai chamalo. Pero hai un tipo de problema aquí, e imos volver a números por un momento. Supoña que fago, en realidade, teñen unha serie de números, e supor que o programa que eu estou escribindo é como un libro de notas para un profesor e unha clase profesores. E este programa permite que el ou ela para escribir as notas dos seus alumnos en cuestionarios. E supoña que o alumno recibe 100 no seu primeiro exame, quizais como un 80 o próximo, a continuación, un 75, a continuación, un 90 no cuarto quiz. 

Polo tanto, neste punto da historia, a matriz é de tamaño catro. Non hai absolutamente máis memoria na ordenador, pero a matriz, por así dicir, é de tamaño catro. Supoñamos agora que o profesor quere para asignar un quinto exame para a clase. Ben, unha das cousas que ou vai ter que facer agora almacenar un valor adicional aquí. Pero se a matriz o profesor ten creado neste programa é de tamaño para, un dos problemas con que é unha matriz non pode simplemente seguir engadir a memoria. Porque o que se outra parte do programa ten a palabra "hey" alí? 

Noutras palabras, a memoria pode ser usado para calquera cousa nun programa. E se antes eu escriba, hey, Quero entrada catro puntuacións do cuestionario, poden ir aquí e aquí. E se de súpeto cambiar a súa mente máis tarde e dicir que quero un quinto proba puntuación, non pode simplemente poñelas onde quere, porque o que se esta memoria está a ser usada para algo else-- algún outro programa ou algunha outra característica do programa que está correndo? Entón tes que pensar con antelación como quere almacenar os seus datos, porque agora pintou só nun recuncho dixital. 

Así, un profesor pode, en vez dicir cando se escribe un programa para almacenar o seu notas, vostede sabe o que? Vou pedir, ao escribir o meu programa, que quero cero, un, dous, tres, catro, cinco, seis, oito graos en total. Entón, un, dous, tres, catro, cinco, seis, sete, oito. O profesor pode só sobre-reservar memoria ao escribir o seu programa e dicir, vostede sabe o que? Eu nunca vou asignar máis de oito probas nun semestre. Isto é unha tolemia. Eu nunca vou asignar iso. Así que esta forma que el ou ela ten a flexibilidade para puntuacións tenda de estudante, como 75, 90, e quizais un extra, onde o alumno ten crédito extra, 105. 

Pero se o profesor non utiliza estes tres espazos, hai un takeaway intuitiva aquí. El ou ela é só desperdicio de espazo. Polo tanto, noutras palabras, non é iso tradeoff común na programación onde podes reservar exactamente tanta memoria como quere, a cabeza do que é o que está super efficient-- non está a ser a pérdida en todos-- pero a desvantaxe dos cales é o que se cambiar a súa mente cando usando o programa que quere gardar máis datos do que inicialmente previsto. 

Entón, se cadra a solución é, entón, escribir os seus programas de tal forma que empregan máis memoria do que realmente precisan. Desta forma, non vai a executar para este problema, pero está a ser un desperdicio. E o máis memoria o programa usa, como discutir onte, a menos memoria que está dispoñible para outros programas, canto máis cedo o seu ordenador pode retardar abaixo por mor da memoria virtual. E así a solución ideal pode ser o que? 

Sub-reparte parece malo. Over-reparte parece malo. Entón, o que pode ser unha solución mellor? A deslocalización. Sexa máis dinámico. Non force a escoller un priori, en principio, o que quere. E, por suposto, non o exceso de reservar, para que non ser un desperdicio. 

E así, para acadar este obxectivo, que xogar esta estrutura de datos, por así dicir, lonxe. E entón o que un programador tipicamente utilizará é algo que non é unha chamada matriz, pero unha lista ligada. Noutras palabras, el ou ela vai comezar a pensar na súa memoria como un tipo de forma que eles pode aproveitar do seguinte xeito. Se eu queira gardar un número na un program-- polo que é de setembro de Eu dei os meus alumnos un cuestionario; quero para almacenar primeira proba dos alumnos, e ten un 100 sobre ele-- I vou pedir o meu ordenador, por medio do programa que eu teño escrito, por un anaco de memoria. E eu estou indo para almacenar o número 100, e é iso. 

Logo unhas semanas máis tarde cando chegar no meu segundo cuestionario, e é o momento de escribir en que o 90%, eu vou para pedir o ordenador, hey, ordenador, Podo ter outro anaco de memoria? Me vai dar a este anaco branco de memoria. Vou poñer o número 90, pero no meu programa de algunha maneira ou outro-- e nós non vai preocuparse a sintaxe para isto-- necesito dalgún xeito encadear esas cousas xuntas. E eu vou acorrentá los xunto coa o que parece ser unha frecha aquí. 

O terceiro cuestionario que xorde, Eu vou dicir, hey, ordenador, darme outro anaco de memoria. E eu vou tirar abaixo que quere que fose, como 75, e teño de cadea presente xuntos agora dalgún xeito. Cuarta cuestionario ven xunto, e quizais isto é para o final do semestre. E por ese punto o meu programa pode estar usando memoria en todo o lugar, en todo fisicamente. E así, só por diversión, eu son vai sacar esa luz quiz-- esquezo o que era; eu creo que quizais un 80 ou algo-- camiño ata aquí. 

Pero iso é bo, porque pictoricamente Eu estou indo a deseñar esta liña. Noutras palabras, en realidade, no hardware do seu ordenador, a primeira puntuación pode acabar aquí, porque é Ao comezo do semestre. O seguinte pode acabar aquí porque un pouco de tempo xa pasou eo programa segue funcionando. A seguinte puntuación, que foi a 75, pode ser por aquí. E a última puntuación pode ser un 80, que é por aquí. 

Entón, en realidade, fisicamente, que pode ser o que a memoria do seu ordenador parece. Pero este non é un mentais útil paradigma para un programador informático. Por que ten que se preocupar onde a Parreira seus datos están rematando? Só quere almacenar datos. 

Este é tipo de como a nosa discusión antes de deseñar o cubo. Por que lle importa o que é o ángulo do cubo e como ten que volver para deseña-lo? Só quere un cubo. Do mesmo xeito aquí, só quero libro de notas. Só quere pensar isto como unha lista de números. Quen lle importa como é aplicadas en hardware? 

Así, a abstracción agora É esta foto aquí. Esta é unha lista ligada, como programador estaba chamalo, na medida en que ten un lista, obviamente, de números. Pero está ligada pictoricamente por medio destas frechas, e todas estas frechas é-- debaixo o capó, se está curioso, Recordamos que o noso hardware físico ten enderezos cero, un, dous, tres, catro. Todas estas frechas son é como un mapa ou instrucións, onde se 90 é-- agora Teño que contar. 

Cero, un, dous, tres, catro, cinco, seis, sete. Parece que o 90 é o memoria do número de enderezo de sete. Todas estas frechas son é como un pequeno anaco de papel que está dando instrucións ao programa que di que siga este mapa para chegar ao lugar de sete. E alí vai atopar o segunda puntuación do cuestionario do estudante. Mentres tanto, o 75-- si continuar con este, este é sete, oito, nove, 10, 11, 12, 13, 14, 15. 

Estoutra frecha representa só nun mapa para localización de memoria 15. Pero, de novo, o programador xeralmente fai non se preocupan este nivel de detalle. E na maioría cada programación linguaxe de hoxe, o programador nin vai saber onde na memoria estas cifras realmente son. Todo o que el ou ela ten que se preocupan o que son de algunha maneira ligado xuntos nunha estrutura de datos como este. 

Pero resulta que non ser moi técnico. Pero só porque podemos quizais dar o luxo de ter esta conversa aquí, supoña que revisitar esta cuestión aquí dunha matriz. Imos ver se nós lamentamos indo para alí. Esta é de 100, 90, 75, e 80. 

Deixe-me facer brevemente esta reivindicación. Esta é unha matriz, e de novo, o característica destacada dunha matriz é que os seus datos está de volta ao de volta para atrás en memory-- literalmente Un byte ou quizais catro bytes, un número fixo de bytes de distancia. Nunha lista ligada, o que poderiamos chamar así, debaixo do capó que sabe onde o material é? El nin sequera teñen que fluír como este. Algúns dos datos pode ser de volta á esquerda ata alí. Vostede nin sequera sabe. 

E así, cunha matriz, ten un recurso coñecido como acceso aleatorio. E o que os medios de acceso aleatorio é que o ordenador pode ir instantáneamente para calquera lugar nunha matriz. Por que? Porque o equipo sabe que é o primeiro localización cero, un, dous e tres. 

E entón se quere ir de este elemento para o elemento seguinte, vostede literalmente, na A mente de ordenador, só tes que engadir un. Se quere ir ao terceiro elemento, basta engadir um-- seguinte elemento, só engadir un. Con todo, nesta versión da historia, supoña o ordenador está a visitar ou en manexar o número 100. Como chegar ao seguinte grao no libro de notas? 

Ten que tomar sete etapas, que é arbitraria. Para chegar ao seguinte, ten que levar oito pasos para chegar a 15. Noutras palabras, non é un lagoa constante entre os números, e por iso só leva o ordenador máis tempo é o punto. O ordenador debe buscar a través da memoria, a fin para atopar o que está a procurar. 

Así, mentres que unha matriz tende a ser un structure-- rápida de datos porque Pode literalmente só facer aritmética simple e chegar onde quere pola adición dun, para instance-- unha lista ligada, vostede sacrifica este recurso. Non pode simplemente ir de primeira para a segunda a terceira para a cuarta. Ten que seguir o mapa. Ten que tomar máis medidas para chegar a eses valores, que parece ser a adición dun custo. Entón, nós estamos pagando un prezo, pero o que era o recurso que Dan busca aquí? O que fai unha lista ligada parecer nos permiten facer, cal foi a orixe da esta historia en particular? 

Exactamente. Un tamaño dinámico para iso. Podemos engadir a esta lista. Podemos incluso máis a, para que só está a usar o máximo de memoria como queremos realmente e así estamos nunca over-reparte. 

Agora é só para ser realmente nit-esixente, hai un custo oculto. Entón non debe deixarme convencer que este é un compromiso convincente. Hai outro custo oculto aquí. O beneficio, para ser claro, é que comezamos dinamismo. Se eu queira outro elemento, só pode deseña-lo e poñer un número alí. E entón eu podo ligala cunha imaxe aquí, mentres aquí, de novo, se eu teño pintou-me en un canto, se algo xa está a usar a memoria aquí, estou fóra da sorte. Pintei-me para o canto. 

Pero o que é o oculto custa nesta foto? Non é só a cantidade de tempo que leva para ir de aquí ata aquí, que é de sete pasos, logo oito etapas, que é máis que un. Que é outro custo oculto? Non só tempo. Información adicional están necesario para lograr este cadro. 

Si, ese mapa, eses pequenos anacos de papel, como eu manter describindo os como. Estes arrows-- aqueles que non son libres. A Computador-- sabe o que un ordenador ten. Ten ceros e uns. Se desexa representar unha frecha ou un mapear ou un número, precisas algunha memoria. Entón, o outro prezo que pagar por unha lista ligada, a ciencia da computación común de recursos, é tamén espazo. 

E de feito así, tan comunmente, Entre as compensacións no deseño de enxeñaría de software sistemas é o tempo e espaço-- son dous dos seus ingredientes, dous dos seus ingredientes máis caros. Isto me custando máis tempo porque eu teño que siga este mapa, pero tamén me custa máis espazo porque eu teño que manter este mapa arredor. Así, a esperanza, como nós tipo de discutido sobre onte e hoxe, é que os beneficios ha superan os custos. 

Pero non hai ningunha solución obvia aquí. Quizais sexa melhor-- a la rápida e sucia, como Kareem proposta earlier-- para xogar memoria ao problema. Só ten que mercar máis memoria, pensar menos duro sobre como resolver o problema, e resolver-lo dun xeito máis sinxelo. E, de feito antes, cando falamos compensacións, non había espazo o ordenador e tempo. Era hora creador, que é aínda outro recurso. 

Entón, de novo, é este acto de equilibrio tentando decidir cal destas cousas está disposto a gastar? Cal é o menos caro? Que produce os mellores resultados? Si? 

Por suposto. Neste caso, se está representando números na maps-- estes son chamados en moitas linguas "Ponteiros" ou "enderezos" - que é o dobre do espazo. Isto non debe ser tan malo como o dobre se agora estamos só almacenar números. Supoña que estaban almacenando rexistros de pacientes nun hospital-- así nomes de Pierson, números de teléfono, números de seguridade social, médico historia. Esta caixa pode ser moi, moito maior, en cuxo caso algo punteiro minúsculo, a dirección do a seguinte element-- non é un gran negocio. É un tal franxa custo, non importa. Pero neste caso, si, é unha duplicación. Boa pregunta. 

Imos falar sobre o tempo que un pouco máis concretamente. Cal é o tempo de execución de buscar esta lista? Supoña que quería para buscar a través de todas as notas dos alumnos, e hai n graos nesta estrutura de datos. Aquí, tamén, podemos tomar prestado o vocabulario da anterior. Esta é unha estrutura de datos lineal. 

Big O de n é o que é necesario para obter ao final da presente estrutura de datos, whereas-- e non vimos este antes-- unha matriz dálle o que se chama de tempo constante, o que significa un paso ou dous pasos ou 10 steps-- non importa. É un número fixo. Non ten nada que ver con o tamaño da matriz. E a razón para iso, unha vez máis, é de acceso aleatorio. O ordenador pode só inmediatamente ir a outro lugar, porque son todos iguais distancia de todo o resto. Non hai ningún pensamento parte. Todo ben. Entón, se eu puidera, déixeme probar pintar dous cadros finais. Un moi común coñecida como unha táboa hash. Entón, para motivar a discusión, déixeme pensar sobre como facelo. 

Así como sobre iso? Supóñase que o problema queremos resolver agora está a aplicar nun dictionary-- polo que unha morea de palabras en inglés ou o que quere. E o obxectivo é o de poder responder preguntas do formulario esta é unha palabra? Entón quere aplicar un corrector ortográfico, só como un dicionario física que podes ollar as cousas en. Supoña que eu fose facelo con unha matriz. Podería facelo. 

E supoñer que as palabras son de mazá e bananas e melón. E eu non podo pensar de froitas que comezan con D, entón estamos só terá tres froitas. Polo tanto, este é un array, e estamos almacenar todas estas palabras neste dicionario como unha matriz. A cuestión, entón, é que outra forma pode almacenar esta información? 

Ben, eu son o tipo de trampas aquí, porque cada unha destas letras da palabra é realmente un byte individual. Entón, se eu realmente quería ser nit-esixente, realmente debería ser dividindo este en moi pequenos anacos de memoria, e poderiamos facer exactamente isto. Pero nós estamos indo funcionar o mesmo problema que antes. E se, como Merriam Webster ou Oxford fai cada ano-- que engadir palabras ao dictionary-- non necesariamente quere nos pintar nunha esquina cunha matriz? 

Entón, en vez, se cadra unha visión máis intelixente é poñer a mazá no seu propio nó ou caixa, como diriamos, banana, e entón aquí temos melón. E corda que estas cousas xuntas. Polo tanto, esta é a matriz, e esta é a lista ligada. Se non pode ver, só di "matriz", e iso di "lista". 

Polo tanto, temos o mesmo cuestións exactas como antes, polo cal agora temos dinamismo na nosa lista ligada. Pero temos un dicionario moi lento. Supoña que queira procurar unha palabra. Me pode levar gran O de n pasos, porque a palabra pode ser todo o camiño a finais de a lista, como melón. E verifícase que na programación, sort do Santo Graal dos datos estruturas, é algo que lle dá constante tempo como unha matriz pero que aínda lle dá dinamismo. 

Así, podemos ter o mellor dos dous mundos? E, de feito, hai algo chamada táboa hash que permite que fai exactamente que, aínda que aproximadamente. Unha táboa é un columbófilo estrutura de datos que nós pode pensar en como a combinación dun array-- e eu vou deseña-lo como isto-- e listas ligadas que eu vou deseñar como este aquí. 

E a forma como esa cousa obras é como segue. Se este agora-- de hash mesa-- é a miña estrutura de datos de terceira, e quero gardar palabras neste, eu non fago quero só almacenar todas as palabras de volta para atrás a volta atrás. Quero aproveitar algunhas peza de información sobre as palabras que lle permitirán me obtelo onde é máis rápido. 

Así, dada a mazá palabras e bananas e melón, Eu deliberadamente elixiu estas palabras. Por que? O que é unha especie de fundamentalmente diferente sobre os tres? Cal é o evidente? Comezan con letras distintas. 

Entón vostede sabe o que? No canto de poñer todas as miñas palabras mesmo balde, por así dicir, como nunha lista grande, por que non facer Eu, polo menos, tentar unha optimización e facer as miñas listas de 1/26 do tempo. A optimización convincente Pode ser por que non facer Eu-- ao inserir unha palabra para esa estrutura de datos, na memoria do ordenador, por iso Non coloque todas as palabras "o" aquí, todo 'B' palabras aquí, e todos os "c" palabras aquí? Entón iso acaba poñendo unha mazá aquí, banana aquí, melón aquí, e así por diante. 

E se eu tivera un adicional palabra como-- o que é outro? Mazá, plátano, pera. Calquera pensa dunha froita que comeza con a, b, c? perfecta Blueberry--. Isto vai acabar aquí. E así parece que temos un marxinalidade mellor solución, porque agora se eu queira para buscar mazá, I first-- Non só mergullo na miña estrutura de datos. Non mergullo na memoria do meu ordenador. I primeiro ollar para a primeira letra. 

E iso é o que un ordenador científico diría. Vostede botar na súa estrutura de datos. Toma a súa entrada, o que, neste caso, é unha palabra como mazá. Vostede analiza-lo, buscando a primeira letra neste caso hashing-o así. Hashing é un termo xeral que toma algo como entrada e producir algunha saída. E a saída na que caso é a localización quere investigar, o primeiro local, segundo lugar, a terceira. Así, a entrada é de mazá, a saída é en primeiro lugar. A entrada é de bananas, o saída debe ser segundo. A entrada é melón, a saída debe ser o terceiro. A entrada é de Arandeira, o saída debe volver a ser segundo. E iso é o que axuda a sacar atallos a través da súa memoria a fin de obter a palabras ou datos de forma máis eficaz. 

Agora, iso reduce noso tempo potencialmente xa que logo como un de 26, porque se asumir que ter tantos "a" palabras como "z" palabras como palabras "q", que non é realmente realistic-- terá a inclinación do outro lado certas letras do alphabet-- pero iso sería un incremental visión que non permite Lo a obter a palabras moito máis rápido. E, en realidade, un sofisticado programa, os Googles do mundo, o Facebooks do mundo-- eles usarían unha táboa hash para unha serie de fins distintos. Pero non sería tan inxenuo basta ollar para a primeira letra na mazá ou albaricoque ou pera ou melón, porque como podes ver eses listas aínda podía comezar por moito tempo. 

E por iso este pode ser tipo de linear-- tan especie de lento, como co gran O de n que discutir anteriormente. Entón, o que un verdadeiro táboa hash boa vontade fazer-- terá unha variedade moi grande. E vai usar un moito máis función de hash sofisticado, de xeito que non só ollar para o "a". Quizais ten en conta "a-p-p-l-e" e dalgún xeito, convértese esas cinco letras no lugar onde mazá debe ser almacenado. Estamos só inxenuamente usando letra 'a' só porque é agradable e sinxela. 

Pero unha táboa hash, en Ao final, pode pensar como unha combinación de unha matriz, cada un dos cales ten unha lista vinculada que idealmente deberá ser tan curto como sexa posible. E iso non é unha solución obvia. De feito, gran parte da sintonização fina o que pasa debaixo do capó cando aplicar estes tipos de estruturas de datos sofisticados é o que é o dereito lonxitude da matriz? Cal é a función hash non? Como gardar cousas na memoria? 

Pero entender o quão rápido este tipo de debate escalada, sexa tan lonxe que é unha especie de sobre a cabeza neste momento, que está ben. Pero comezamos, recall, con verdadeiramente algo de baixo nivel e electrónicos. E así esta nova é este tema da abstracción, onde unha vez que comezar a tomar para concedido, OK, eu teño ele-- hai memoria física, OK, ten, cada localización física ten un enderezo, OK, I got it, I pode representar estes enderezos como arrows-- pode rapidamente comezar a ter conversas máis sofisticados que ao final parece estar nos permite para resolver problemas como buscar e selección de forma máis eficaz. E por suposto, demasiado-- porque eu creo que iso é o máis profundo, fomos nalgún destes temas CS proper-- Nós feito en un día e unha metade neste apuntar o que pode xeralmente facer máis o curso de oito semanas nun semestre. 

Calquera preguntas sobre estes? Non? Todo ben. Ben, por que non facemos un descanso alí, iniciar o xantar uns minutos máis cedo, retomar en só aproximadamente unha hora? E eu vou durar algo con preguntas. Entón eu vou ter que ir levar algunhas chamadas, se está todo OK. Vou chamar unha música, con todo, pero o xantar debe ser á volta da esquina.