[Powered by Google Translate] [Sección 3 - máis cómodo] [Rob Bowden - Harvard University] [Esta é CS50. - CS50.TV] Entón, a primeira pregunta é estrañamente formulada. GDB permite "depurar" un programa, pero, máis especificamente, que é o que imos facer? Vou responder esa, e eu non sei o que é o esperado, entón eu estou supondo que é algo ao longo das liñas de el permite que paso a paso andar a través do programa, interactuar con el, as variables de cambio, facer todas estas cousas - basicamente controlar completamente a execución dun programa e inspeccionar calquera determinada parte da execución do programa. Entón, eses recursos permiten que depurar as cousas. Okay. Por que a procura binaria require que unha matriz ser clasificados? Quen quere responder a iso? [Alumno] Porque non funciona se non é clasificado. Si >>. [Risas] Se non é resolto, entón é imposible para división lo ao medio e saber que todo a esquerda é menos e todo á dereita é maior que o valor medio. Por iso, debe ser ordenada. Okay. Por que é unha especie de burbulla en O de n ao cadrado? Alguén primeiro quero dar unha moi rápida visión xeral de alto nivel de que tipo burbulla é? [Alumno] Vostede basicamente pasar por cada elemento e comprobar os elementos primeiros. Se eles están fóra de onde troca-los, despois de comprobar os elementos seguintes, e así por diante. Cando chegar ao final, entón vostede sabe que o maior elemento colócase ao final, así ignorar que un, entón continuar pasando, e cada vez que ten que comprobar un elemento menos ata que non facer cambios. Si >>. É chamado especie de burbulla, porque se virar a matriz de lado así que é de arriba para abaixo, vertical, a continuación, os grandes valores que van para o fondo e os pequenos valores vai borbulhar ata o cumio. É así que ten o seu nome. E si, acaba de pasar. Vostede segue pasando pola matriz, trocando o valor maior para obter os maiores valores para o fondo. Por que é o n ao cadrado? En primeiro lugar, alguén quere dicir por iso que é o n ao cadrado? [Alumno] Por cada carreira vai n veces. Só podes estar seguro de que teña tido o maior elemento de todo o camiño, entón tes que repetir que para tantos elementos. Si >>. Polo tanto, teña presente o que significa e gran Que significa Omega grandes. O O gran é como o límite superior sobre o quão lento el realmente pode ser executado. Entón, dicindo que é o n ao cadrado, non é o de n ou el sería capaz de executar no tempo lineal, pero é de O n cubed porque é delimitada por O de n en cubos. Se é limitado por O de n ao cadrado, é limitada tamén polo n cubos. Por iso, é n ao cadrado e, no peor caso absoluta que non pode facer mellor que n ao cadrado, é por iso que é o n ao cadrado. Entón, para ver de matemáticas discreta en como ven sendo n ao cadrado, se temos cinco cousas na nosa lista, a primeira vez que o número de swaps poderiamos potencialmente cómpre facer a fin de obter isto? Imos realmente só - Cantos swaps que imos ter que facer na primeira carreira da especie de burbulla a través da matriz? [Alumno] n - 1. Si >>. Se hai 5 elementos, imos ter que facer n - 1. A continuación, no segundo cantas swaps que imos ter que facer? [Estudante] n - 2. Si >>. E o terceiro vai ser n - 3, e logo para o barrio vou escribir os dous últimos como entón imos ter que facer dous swaps e un de intercambio. Eu creo que o último pode ou non pode realmente precisan pasar. É un intercambio? Eu non sei. Polo tanto, estas son as cantidades totais de swaps ou polo menos comparacións que ten que facer. Mesmo se non cambiar, aínda que comparar os valores. Entón, existen n - 1 comparacións na primeira carreira a través da matriz. Se reorganizar isto, imos realmente facer seis cousas así que as cousas se comportan ben, e entón eu vou facer 3, 2, 1. Entón, só tes que reorganizar estes importes, que queremos ver cantas comparacións facemos no algoritmo enteiro. Entón, se nós traemos estes faces aquí abaixo, entón aínda estamos só sumando comparacións con todo eran. Pero resumir estes e sumamos estes e sumamos estes, aínda é o mesmo problema. Nós só sumar eses grupos particulares. Entón agora estamos sumando 3 n da. Non é só de 3 n. É sempre vai ser n / 2 n é. Entón, aquí acontece que temos 6. Se tivésemos 10 cousas, entón nós poderíamos facelo de agrupación para 5 pares distintos de cousas e acabar con n + n + n + n + n. Entón, está sempre indo para obter N / 2 N, e así por iso, imos anotar-lo para n ao cadrado / 2. E por iso mesmo que é o factor da metade, o que pasa a entrar en debido ao feito de que en cada iteração sobre a matriz compararmos un a menos entón é así que temos a máis de 2, pero aínda é n ao cadrado. Nós non nos importamos co factor constante dun media. Entón, unha morea de cousas O grande como este se basea en só un tipo de facer este tipo de matemáticas, facer contas de aritmética e outras cousas serie xeométrica, pero a maioría deles neste curso son moi sinxelo. Okay. Por que é tipo de inserción no Omega de n? O que o omega significa? [Dous alumnos falan ao mesmo tempo - inintelixibles] si. >> Omega pode pensar como o límite inferior. Polo tanto, non importa o quão eficaz o seu algoritmo de ordenación por inserción e, independentemente da lista que se transmite, el sempre ten que comparar polo menos n cousas ou ten que iterar n cousas. Por que isto? [Alumno] Porque a lista xa está clasificado, a continuación, a través iteração o primeiro só pode garantir que o primeiro elemento é o mínimo, ea segunda iteração só pode garantir os dous primeiros son porque non sabe o que o resto da lista está ordenada. Si >>. Se pasar a unha lista completamente clasificados, como mínimo ten que pasar por riba de todos os elementos para ver que nada ten que ser movidos. Entón, pasando por riba da lista e dicir oh, iso xa está clasificado, é imposible para ti saber que está clasificada ata que verifique cada elemento para ver que están en orde de clasificación. Así, o límite inferior é Omega tipo de inserción de n. Cal é o peor caso de tempo de funcionamento merge sort, O peor caso de ser grande de novo? Así, no peor caso, como é que merge sort correr? [Estudante] N log n. Si >>. Os máis rápidos algoritmos de clasificación xeral son n log n. Vostede non pode facer mellor. Hai casos especiais, e se temos tempo de hoxe - pero probablemente won't - podemos ver un que fai mellor que n log n. Pero, no caso xeral, non pode facer mellor que n log n. E merge sort pasa a ser o que debes saber para este curso que é n log n. E así imos realmente ser de execución que hoxe. E, finalmente, en non máis que tres frases, como funciona o tipo de selección? Alguén quere responder, e eu vou contar as súas frases porque se pasar por riba de 3 - Alguén se lembra tipo de selección? Tipo de selección é xeralmente moi fácil de lembrar só do nome. Só iterar sobre a matriz, atopar o que o maior valor é menor ou - orde que está clasificando dentro Entón, imos dicir que estamos clasificación da menor á maior. Vostede iterar sobre a matriz, ollando para o que o elemento mínimo é, selecciona-lo, e despois é só troca-lo o que está en primeiro lugar. E entón, na segunda pasaxe sobre a matriz, busque o elemento mínimo de novo, selecciona-lo, e despois troca-lo o que está na segunda posición. Entón, estamos só escollendo os valores mínimos e inserindo-os na fronte da matriz ata que sexa ordenada. Preguntas sobre iso? Isto inevitablemente aparecen nas formas que ten que cubrir cando está enviando o pset. Estes son, basicamente, as respostas a estes. Ok, entón agora codificación problemas. Eu xa enviado mediante correo-e - Será que ninguén obter ese e-mail? Okay. Eu xa enviou por correo-e o espazo que imos utilizar, e se fai clic no meu nome - entón eu creo que vou estar no fondo por mor do r atrás - pero se fai clic no meu nome que vai ver dúas revisións. Revisión 1 vai ser xa copiou e colou o código en espazos a cousa de busca terá que aplicar. Revisión 2 e será a cousa tipo que imos aplicar despois diso. Así, pode facer clic no meu Revisión 1 e traballar a partir de aí. E agora queremos aplicar busca binaria. Alguén quere só dar unha explicación de alto nivel pseudocódigo de que nós imos ter que facer para investigacións? Si [Estudante] Vostede acaba de tomar a metade da matriz para ver o que está a buscar é menor que ou maior que iso. E se é menos, vai para a metade que é menos e é máis, vai para a metade que é máis e repetir iso ata, é só incorporarse unha cousa. [Bowden] Yeah. Teña en conta que a nosa matriz de números xa está clasificado, e así que significa que podemos sacar proveito diso e podemos comprobar primeiro, ben, eu estou ollando para o número 50. Entón eu podo ir para o medio. Medio é difícil de definir cando é un número par de cousas, pero imos só dicir que sempre truncar para o medio. Polo tanto, temos aquí oito cousas, de xeito que o medio sería 16. Estou na procura de 50, polo que 50 é maior que 16. Entón agora podo tratar a miña matriz basicamente como estes elementos. Eu podo tirar todo de máis 16. Agora a miña matriz é só estes catro elementos, e repito. Entón eu quero atopar o medio novo, que vai a ser 42. 42 é menor que 50, entón eu podo tirar estes dous elementos. Esta é a miña matriz resto. Eu vou atopar o medio de novo. Eu creo que 50 foi un mal exemplo, porque eu estaba sempre botando fóra as cousas á esquerda, pero pola mesma medida, se eu estou buscando algo e é menos que o elemento Actualmente estou mirando, entón eu vou tirar todo á dereita. Entón agora necesitamos aplicar iso. Teña en conta que temos que pasar de tamaño. Non podemos tamén debe duro código de tamaño. Entón, se librar dese # define - Okay. Como podo moi ben imaxinar o que o tamaño da matriz de números, actualmente, é? Cantos elementos están na matriz de números? [Alumno] Números, soportes. Lonxitude? [Bowden] Iso non existe en C. Precisa. Lonxitude. Matrices non teñen propiedades, por iso non hai propiedade de lonxitude de matrices que só vai dar-lle todo o tempo que pasa a ser. [Estudante] Ver a cantidade de memoria que ten e dividir por canto - Si >> Entón, como podemos ver canta memoria ten? >> [Alumno] Sizeof. >> Si, sizeof. Sizeof é o operador que vai voltar o tamaño da matriz de números. E iso vai ser enteiros con todo, hai moitas veces o tamaño dun enteiro xa que é a cantidade de memoria que está realmente tomando-se. Entón, se eu queira que o número de cousas na matriz, entón eu vou querer dividir o tamaño dun enteiro. Okay. Así que me permite pasar a tamaño aquí. Por qué me teño pasar en tamaño a todos? Por que non podo simplemente facer aquí int tamaño = sizeof (palheiro) / sizeof (int)? Por que iso non funciona? [Alumno] Non é unha variable global. [Bowden] Haystack existe e estamos pasando en números como palheiro, e esta é unha especie de prenúncio do que está por vir. Si [Alumno] Haystack é só a referencia a el, por iso sería volver como gran referencia que é. Si Eu dubido que na charla que xa viu a pila aínda moi, non? Acaba de falar sobre iso. Así, a pila é onde todas as súas variables van ser gardados. Calquera memoria que está asignado para as variables locais vai na pila, e cada función recibe o seu propio espazo na pila, o seu cadro de pila propia é o que se chama. Entón principal ten o seu cadro de pila, e dentro del vai existir esa matriz de números, e que vai ser de tamaño sizeof (números). Vai ter o tamaño de números separados por tamaño dos elementos, pero que todas as vidas dentro do cadro principal de pila. Cando chamamos de busca, investigación recibe o seu cadro de pila propia, o seu propio espazo para almacenar todas as súas variables locais. Pero estes argumentos - así palheiro non é unha copia desta matriz enteira. Non pasamos en toda a matriz como unha copia en investigación. El só pasa unha referencia a esta matriz. Entón investigación pode acceder estes números a través desta referencia. Aínda está accedendo as cousas que viven dentro da estrutura principal da pila, pero, basicamente, cando chegamos aos punteiros, que debe ser en breve, Isto é o que os punteiros son. Os punteiros son só referencias a cousas, e pode usar punteiros para acceder as cousas que están en cadros de outras cousas "pila. Así, aínda que os números e lugar para o principal, que aínda pode acceder a través deste punteiro. Pero xa que é só un punteiro e é só unha referencia, sizeof (palheiro) retorna só o tamaño da propia referencia. Non retorna o tamaño da cousa que está a apuntar. Non retorna o tamaño real dos números. E iso non vai funcionar como queremos que el. Preguntas sobre iso? Punteiros será ir en detallados significativamente máis sanguento a semana que vén. E é por iso que unha morea de cousas que ve, cousas de busca máis ou cousas de clasificación, están case todos indo a necesidade de ter o tamaño real da matriz, porque en C, non temos idea do que o tamaño da matriz é. Debe manualmente pasalo dentro E non pode manualmente pasar en toda a matriz, porque está só de paso na referencia e non pode obter o tamaño da referencia. Okay. Entón, agora queremos aplicar o que foi explicado antes. Pode traballar con el por un minuto, e non ten que se preocupar en obter todo perfectamente o 100% funcionando. Só ten que escribir o pseudocódigo metade para como pensas que debe funcionar. Okay. Non hai necesidade de facer completamente con iso aínda. Pero será que alguén se sinta cómodo co que, ata agora, como algo que pode traballar en conxunto? Alguén quere ser voluntario? Ou eu vou escoller aleatoriamente. Non ten que estar seguro de calquera medida, senón algo que pode modificar en un estado de traballo. [Alumno] Claro. Ok >>. Entón podes gardar a revisión premendo na icona Gardar pouco. Vostede é Ramya, non? >> [Estudante] Yeah. >> [Bowden] Okay. Entón agora podo ver a súa revisión e todos poden puxar arriba a revisión. E aquí temos - Correcto. Entón Ramya foi coa solución recursiva, que é sempre unha solución válida. Hai dúas formas que pode facer este problema. Podes facelo de forma iterativa ou recursivamente. A maioría dos problemas que atopa o que se pode facer recursivamente tamén pode ser feito de forma iterativa. Entón aquí temos feito isto de forma recursiva. Será que alguén quere definir o que significa facer unha función recursiva? [Estudante] Cando ten unha función chamar a si mesma e despois chamar ata que sae con certo e verdade. Si >>. Unha función recursiva é só unha función que chama a si mesmo. Hai tres cousas grandes que unha función recursiva debe ter. O primeiro é, obviamente, el chama a si mesmo. O segundo é o caso base. Entón, en algún momento, a función precisa deixar de chamarse, e iso que o caso base é. Entón aquí sabemos que debemos parar, debemos dar-se en nosa procura cando comezo iguala final - e nós falaremos sobre o que iso significa. Pero, finalmente, a última cousa que é importante para funcións recursivas: as funcións de algunha maneira abordar o caso base. Como se non está realmente actualizar algo cando fai a segunda chamada recursiva, se está literalmente só chamando a función novo cos mesmos argumentos e non variables globais cambiaron ou algo, nunca vai chegar ao caso base, caso en que iso é malo. Será unha recursão infinita e un estourido de pila. Pero aquí vemos que a actualización está a suceder desde o inicio, estamos a actualizar + final / 2, estamos a actualizar o argumento final aquí, estamos a actualizar o argumento start aquí. Así, en todas as chamadas recursivas estamos a actualizar algo. Okay. Quere andar connosco a través da súa solución? >> Suposto. Está a usar SearchHelp de xeito que cada vez que fago esta chamada de función Eu teño o inicio de onde eu estou buscando na matriz e ao final de onde eu estou mirando a matriz. A cada paso onde está dicindo que é o elemento do medio, que é de inicio + final / 2, que coincide co que nós estamos a buscar? E se é, entón, que atopamos, e eu creo que é pasado ata os niveis de recursão. E se iso non é verdade, entón imos comprobar ese valor medio da matriz é moi grande, caso en que se mira cara á parte esquerda da matriz, indo desde o inicio ata o índice medio. E se non, facer a media final. [Bowden] Okay. É unha boa idea. Ok, entón un par de cousas, e en realidade, iso é unha cousa moi alto nivel que nunca vai ter saber para este curso, pero é verdade. Funcións recursivas, sempre escoita que son un mal negocio porque se recursivamente chamar-se moitas veces, tes de estourido de pila unha vez que, como dixen antes, cada función recibe o seu cadro de pila propia. Entón, cada chamada da función recursiva obtén a súa estrutura propia pila. Entón, se fai mil chamadas recursivas, recibe 1.000 cadros de pila, e axiña levar a ter cadros de pila máis e as cousas simplemente romper. É por iso que funcións recursivas son xeralmente mal. Pero hai un subconxunto agradable de funcións recursivas chamado rabo-recursivas funcións, e este pasa a ser un exemplo de un que o compilador percibe iso e que debería, creo eu - en Clang se pasar a O2-bandeira a continuación, que vai entender que é rabo recursiva e facer as cousas ben. El vai reutilizar o cadro de pila, unha e outra vez para cada chamada recursiva. E así dende que está a usar o cadro de pila mesmo, non se preocupe nunca Empilhe transbordador, e, ao mesmo tempo, como dixen antes, onde unha vez voltar certo, entón ten que volver a todos estes cadros de pila ea chamada de 10 a SearchHelp ten que volver ao 9, ten que volver ao 8. De xeito que non precisa ocorrer cando funcións cola recursiva. E entón o que fai esta cola función recursiva é aviso de que, para un convite para searchHelp a chamada recursiva que está facendo é o que está retornando. Así, en primeira chamada para SearchHelp, que quere voltar inmediatamente falso, voltar inmediatamente certa, ou facemos unha chamada recursiva para SearchHelp onde o que está retornando é o que esta chamada está retornando. E non podería facelo se fixemos algo así como int x = SearchHelp retorno, x * 2, só algunha alteración aleatoria. Entón, agora chamada esta recursiva, esta int x = SearchHelp chamada recursiva, xa non é rabo recursiva porque en realidade non ten que devolver de volta para un cadro de pila anterior de xeito que a chamada anterior para a función Pode, entón, facer algo co valor de retorno. Entón iso non é rabo recursiva, pero o que tiña antes, é ben cola recursiva. Si [Alumno] non debe caso base segundo verificar primeiro porque pode haber unha situación en que, cando pasar o argumento comezar = fin, pero son o valor da agulla. A cuestión foi que non podemos executar para o caso en que o valor final é de agulla ou iniciar = fin, apropiadamente, comezar final = e realmente non teño comprobado que un valor particular, con todo, a continuación, iniciar + final / 2 é só vai ser o mesmo valor. Pero nós xa regresou falso e nós nunca realmente comprobado o valor. Entón, como mínimo, en primeira convocatoria, o tamaño é 0, entón queremos volver falso. Pero se o tamaño é 1, entón de inicio non vai acabar igual, e nós imos polo menos comprobar a un elemento. Pero eu creo que está certo en que pode acabar nun caso onde comezar + final / 2, inicio acaba sendo o mesmo que de inicio + final / 2, pero nós nunca realmente comprobado ese elemento. Entón, se nós primeiro comprobar que o elemento do medio o valor que está a buscar, entón podemos voltar inmediatamente certo. Máis se son iguais, non hai sentido en continuar xa que estamos indo só para actualizar a un caso en que estamos en unha matriz de elementos único. Se ese elemento único non é o que estamos a buscar, entón está todo mal. Si [Estudante] O problema é que unha vez que o tamaño é realmente maior que o número de elementos na matriz, Xa existe un desprazamento - >> Entón vai tamaño - [Alumno] Dicir a matriz foi tamaño 0, entón o SearchHelp vai realmente comprobar palheiro de 0 na primeira chamada. A matriz ten tamaño 0, de modo que o 0 é - >> Yeah. Hai outra cousa que - que podería ser bo. Imos pensar. Entón, se a matriz tiña 10 elementos e un medio que imos comprobar se o índice de 5, por iso estamos comprobando 5, e imos dicir que o valor é menor. Entón, nós estamos xogando todo fóra de 5 en diante. Entón comeza a + final / 2 vai ser o noso novo fin, Entón, si, el sempre vai estar máis aló do fin da matriz. Se é un caso era par ou impar, entón poderiamos comprobar, por exemplo, 4, pero aínda estamos xogando fóra - Entón, si, o fin é sempre vai ser ademais do fin real da matriz. Así, os elementos que estamos focando, final é sempre vai ser o un despois. E así se fai sempre comezo final igual, estamos nunha matriz de tamaño 0. A outra cousa que eu estaba a pensar que estamos a actualizar inicio para comezar a ser + final / 2, por iso este é o caso que eu estou a ter problemas con onde comezar + final / 2 é o elemento que estamos comprobando. Imos dicir que tivemos esa matriz de 10 elementos. Calquera que sexa. Entón comeza a + final / 2 vai ser algo así como este, e se iso non é o valor, digamos que quere actualizar. O valor é maior, por iso queremos mirar para esta metade da matriz. Entón, como estamos a actualizar inicio, estamos a actualizar inicio para agora ser ese elemento. Pero iso aínda pode traballar, ou polo menos, pode facer start + final / 2 + 1. [Alumno] Non precisa ser comezar final + [inaudível] >> Yeah. Nós xa comprobada este elemento e sei que non é o que estamos a buscar. Polo tanto, non é necesario actualizar inicio para este elemento. Podemos simplemente ignore-lo e actualizar comezar a ser este elemento. E sempre hai un caso, imos dicir que este fose final, así, entón comezar sería iso, inicie + final / 2 sería este, comezar a final + - Si, eu creo que pode acabar en recursão infinita. Imos dicir que é só unha matriz de tamaño 2 ou unha matriz de tamaño 1. Eu creo que iso vai funcionar. Así, actualmente, é que inicio e fin elemento é un alá. Así, o elemento que imos comprobar é este, e entón, cando actualizamos inicio, estamos a actualizar inicio para ser 0 + 1/2, que vai acabar nos de volta con saída sendo este elemento. Entón, nós estamos comprobando o mesmo elemento e outra vez. Polo tanto, este é o caso en que cada chamada recursiva que realmente actualizar algo. Entón, necesitamos facer start + final / 2 + 1, ou ben hai un caso onde non estamos realmente actualizar inicio. Todo o mundo ve isto? Okay. Alguén ten preguntas sobre esta solución ou comentarios máis? Okay. Alguén ten unha solución iterativa que todos podemos mirar? Será que todos nós facemos iso recursivamente? Ou eu tamén creo que se abre o seu, entón vostede pode ter substituído o seu anterior. Será que gardar automaticamente? Eu non son positivos. Alguén ten iterativo? Podemos camiñar con el xunto, se non. A idea de que vai ser o mesmo. Resolución iterativa. Nós imos querer facer basicamente a mesma idea onde queremos seguir o novo fin da matriz e do novo comezo da matriz e facelo máis e máis. E se o que estamos mantendo o control de como o inicio eo fin non se cruzan, entón non atopalo e podemos voltar falso. Entón, como podo facer iso? Alguén ten suxerencias ou código para me puxar arriba? [Alumno] Fai un loop while. Si >>. Vai querer facer un loop. Será que ten o código que eu podería tirar cara arriba, ou o que estaba indo a suxerir? [Alumno] Coido que si. >> Todo ben. Isto fai as cousas máis fáciles. Cal era o seu nome? [Alumno] Lucas. Revisión 1. Okay. Baixo é o que chamamos comezar antes. Se non é o que chamamos final antes. En realidade, o fin agora dentro da matriz. É un elemento que debemos considerar. Tan baixa é 0, se é o tamaño da matriz - 1, e agora estamos looping, e estamos comprobando - Eu creo que pode andar por ela. Cal foi o seu pensamento por iso? Ande connosco a través do seu código. [Alumno] Claro. Vexa o valor palheiro no medio e comparalos-lo con agulla. Entón, se é maior que a agulla, entón quere - Oh, en realidade, que debe ser para atrás. Vai querer tirar a metade dereita, e entón si, que debe ser o camiño. [Bowden] Polo tanto, este debe ser menos? É iso que dixo? >> [Estudante] Yeah. [Bowden] Okay. Menos. Entón, o que estamos vendo é menor que o que queremos, entón si, queremos tirar a metade esquerda, o que significa que estamos a actualizar todo o que estamos considerando movendo baixo á dereita da matriz. Este parece ser bo. Eu creo que ten o mesmo problema que nós dixemos que o anterior, onde se baixa é 0 e no 1, entón baixo a + / 2 vai definir ata que a mesma cousa de novo. E mesmo se ese non é o caso, é aínda máis eficiente como mínimo só para xogar fora o elemento que só mirou para que sabemos que é malo. Entón baixo + arriba / 2 + 1 - >> [alumno], que debería ser o contrario. [Bowden] Ou este debe ser - 1 e outro debe ser + 1. [Alumno] E non debe ser un dobre signo igual. >> [Bowden] Yeah. [Estudante] Yeah. Okay. E, finalmente, agora que temos este 1 + - 1 cousa, é - non pode ser - é sempre posible para abaixo para acabar con un valor maior que para arriba? Eu creo que a única forma que pode ocorrer - É posíbel? >> [Alumno] non sei. Pero se queda truncado e logo recibe menos que 1 e despois - >> Yeah. [Alumno] Sería posiblemente ficar confuso. Eu creo que debe ser bo só porque para que acabe menor que tería que ser igual, eu creo. Pero se son iguais, non tería feito o loop while para comezar e nós só tería devolto o valor. Entón, eu creo que estamos ben agora. Nótese que, aínda que este problema xa non é recursivo, o mesmo tipo de ideas aplicar onde podemos ver como iso tan facilmente se presta a unha solución recursiva polo feito de que nós estamos só actualización dos índices e outra vez, estamos facendo o problema cada vez menor, estamos concentrando en un subconxunto da matriz. [Estudante] baixo é 0 e no 1, ambos estarían 0 + 1/2, que ía a 0, e, a continuación, un sería + 1, pode-se ser - 1. [Alumno] Onde estamos comprobando a igualdade? Como se o medio é realmente agulla? Non estamos facendo actualmente isto? Oh! Se isto é - Si Non podemos simplemente facer a proba aquí porque imos dicir que a primeira metade - [Alumno] É realmente como non tirar o límite. Entón, se tirar o salto, ten que comprobar primeiro ou o que quere. Ah. Si >> [Estudante] Yeah. Polo tanto, agora temos xogado fóra o que actualmente mirou, o que significa que nós agora precisamos ter if (palheiro [(+ abaixo) / 2] == agulla), entón podemos voltar true. E se eu poñer máis ou só se, significa literalmente o mesmo porque este tería retornado verdade. Entón, eu vou poñer máis, pero iso non importa. Entón, máis se iso, máis iso, e iso é unha cousa común que fago onde incluso se é o caso, onde todo é bo aquí, como baixo non pode ser maior que se non é o razoamento que paga a pena saber se iso é verdade. Así, pode dicir mentres abaixo é menor que ou igual a ou mentres baixo é inferior a por iso, se son sempre iguais ou baixa acontece a pasar-se, entón podemos romper este ciclo. Preguntas, problemas, comentarios? Okay. Este parece ser bo. Agora queremos facer tipo. Ou tamén a miña segunda revisión, vemos eses mesmos números, pero agora eles non están máis en orde de clasificación. E nós queremos aplicar ordenación usando calquera algoritmo en O de n log n. Así que o algoritmo que pensas que debe aplicar aquí? >> [Alumno] tipo Merge. [Bowden] Yeah. Merge sort é O (n log n), de xeito que é o que imos facer. E o problema vai ser moi semellante, onde se presta facilmente a unha solución recursiva. Tamén podemos chegar a unha solución iterativa, se quere, pero recursão será máis fácil aquí e nós temos que facer a recursividade. Creo que imos camiñar por merge sort primeiro, aínda que haxa un vídeo bonito en merge sort xa. [Risas] Entón, merge sort existen - Estou perdendo moito deste traballo. Oh, hai só unha esquerda. Entón, se funden. Oh, 1, 3, 5. Okay. Merge leva dúas matrices distintas. Individualmente as dúas matrices son ambos clasificados. Entón, esa matriz, 1, 3, 5, clasificados. Esta matriz, 0, 2, 4, clasificados. Agora, o que debe facer é mesturar combina-los nunha única matriz que é en si clasificados. Entón, nós queremos unha matriz de tamaño 6, que vai ter eses elementos dentro del en orde de clasificación. E así podemos aproveitar do feito de que estas dúas matrices son clasificadas facelo en tempo lineal, significado de tempo lineal esa matriz é x tamaño e este é y tamaño, entón o algoritmo total debe ser o (x + y). Okay. Así suxestións. [Alumno] Poderiamos comezar a partir da esquerda? Entón vai poñer a 0 para abaixo primeiro e despois a 1 e, a continuación, aquí está no 2. Entón é tipo de como ten unha guía que se está movendo cara a dereita. >> [Bowden] Yeah. Para ambas as matrices concentrarse só no elemento máis á esquerda. Porque ambas as matrices son clasificadas, sabemos que eses dous elementos son os máis pequenos elementos nun array. Entón isto significa que un deses dous elementos debe ser o menor elemento na nosa matriz resultante da fusión. O que pasa é que o menor é o tempo este dereito. Entón, tomamos 0, introduce o á esquerda porque 0 é menor que 1, así que tomar 0, inserir-lo na nosa primeira posición, e despois actualizar esta para concentrarse en primeiro elemento. E agora imos repetir. Entón agora nós comparar 2 e 1. 1 é menor, polo que imos inserir unha. Nós actualizar este punteiro para apuntar para este cara. Agora imos facelo de novo, entón 2. Isto actualizar, comparar estes 2, 3. Isto actualiza, despois 4 e 5. De xeito que é de mesclagem. Que debe ser bastante obvio que é o tempo lineal, xa que só tes que ir en cada elemento dunha vez. E ese é o maior paso para a implantación de merge sort está facendo iso. E non é tan difícil. Algunhas cousas para se preocupar e imos dicir que foron fusión 1, 2, 3, 4, 5, 6. Neste caso, imos acabar no escenario onde este vai ser menor, entón nós actualizamos este punteiro, este vai ser menor, actualizar esta, este é menor, e agora ten que recoñecer cando realmente ficar sen elementos para comparar. Unha vez que xa utilizaron este matriz enteira, todo nesta matriz é agora só inserido aquí. Entón, se nós nunca executar para o punto onde unha das nosas matrices é completamente fundidas xa, entón simplemente tomar todos os elementos da matriz que non e inserir-las no fin do array. Así, podemos só engadir 4, 5, 6. Okay. Iso é unha cousa a observar. De aplicación que debe ser o paso 1. Mesturar clasificar, entón con base niso, que é dúas etapas, dúas etapas de bobos. Imos dar esa matriz. Entón, merge sort, etapa 1 é recursivamente romper a matriz en metades. Entón, dividir esa matriz en metades. Temos, agora, 4, 15, 16, 50 e 8, 23, 42, 108. E agora nós facelo de novo e nós dividimos estas en metades. Eu só vou facer iso deste lado. Entón, 4, 15 e 16, 50. Queremos facer o mesmo aquí. E agora nós dividídelo en dúas metades de novo. E nós temos 4, 15, 16, 50. Entón, ese é o noso caso base. Unha vez que as matrices son de tamaño 1, entón imos parar coa división en dúas metades. Agora o que imos facer con iso? Imos acabar isto tamén se dividen en 8, 23, 42 e 108. Entón, agora que estamos neste momento, agora o segundo paso merge sort é só fusión pares para as listas. Entón, nós queremos unir estes. Nós só chamar fundir. Sabemos fusión volverá estes en orde de clasificación. 4, 15. Agora, queremos xuntar estas, e que vai voltar unha lista con aqueles en orde de clasificación, 16, 50. Quedamos os - Eu non podo escribir - 8, 23 e 42, 108. Polo tanto, temos pares incorporadas unha vez. Agora só fundir de novo. Teña en conta que cada unha destas listas é clasificada en si, e entón podemos só mesturar estas listas para obter unha lista de tamaño 4, que se clasifica e mesturar estas dúas listas para obter unha lista de tamaño 4, que está clasificada. E, finalmente, podemos mesturar estas dúas listas de tamaño 4 para obter unha lista de tamaño 8, que está clasificada. Entón, a ver que este é global n log n, xa vimos que mesclagem é lineal, Entón, cando estamos lidando con a unión destes, así como o custo global de fusión para estas dúas listas é só 2 porque - Ou ben, é o de n, pero n aquí é só eses dous elementos, por iso é 2. E estes dous será 2 e estes dous será 2 e estes 2 vai ser 2, así en todas as fusións que temos que facer, acabamos facendo n. Como 2 + 2 + 2 + 2 é de 8, que é n, de xeito que o custo de fusión neste conxunto é n. E entón o mesmo aquí. Imos xuntar estas dúas, entón estes dous e, individualmente, esta fusión terá catro operacións, esta fusión terá catro operacións, pero, unha vez máis, entre todos eles, acabamos fusión n cousas totais, e por iso este paso leva n. E así cada nivel ten n elementos a seren reunidos. E cantos son os niveis? En cada nivel, a nosa matriz crece tamaño 2. Aquí nosas matrices son de tamaño 1, aquí son de tamaño 2, aquí son de tamaño 4, e, finalmente, son de tamaño 8. Entón, unha vez que está dobrando, non van ser un total de log n destes niveis. Así, co rexistro de n niveis, cada nivel individual, tendo n total de operacións, temos un log n n algoritmo. Preguntas? Xa as persoas xa fixeron progresos sobre como implementar isto? Será que alguén xa nun estado onde eu só podo tirar para arriba o seu código? Eu podo darlle un minuto. Este vai ser máis longo. Eu recomendo se repiten - Non ten que facer recursão para fusión porque para facer recursão para mesclagem, vai ter que pasar por unha chea de diferentes tamaños. Pode, pero é irritante. Pero recursão para clasificar-se é moi doado. Só literalmente chamar especie na metade esquerda, tipo na metade dereita. Okay. Alguén ten algunha cousa que podo tirar para arriba aínda? Ou entón eu vou dar un minuto. Okay. Alguén ten algo que podemos traballar? Ou entón nós imos traballar con iso e, a continuación, ampliar a partir de aí. Alguén ten máis que iso que podo tirar para arriba? [Estudante] Yeah. Podes puxar a miña. >> Todo ben. Si! [Alumno] Había unha serie de condicións. >> Oh, tirar. Pode - [Estudante] Eu teño que salvalo. Si >>. Entón nós fixemos a fusión por separado. Ah, pero non é tan malo así. Okay. Entón tipo é en si só chamando mergeSortHelp. Explique-nos o que mergeSortHelp fai. [Alumno] MergeSortHelp practicamente fai as dúas etapas principais, que é o de clasificar cada metade da matriz e, a continuación, para fundir os dous. [Bowden] Ok, entón me dea un segundo. Eu creo que iso - >> [alumno] eu teño - Si Eu estou sentindo falta de algo. Na fusión, podo entender que eu teño para crear unha nova matriz porque eu non podería facelo no lugar. Si >>. Vostede non pode. Corrixir. [Estudante] Entón eu crear unha nova matriz. Esquecín o meu a finais de fundir a re-cambiar. Okay. Necesitamos unha nova matriz. En merge sort, iso é case sempre certo. Parte do custo dun algoritmo de mellor en termos de tempo é case sempre a necesidade de usar a memoria un pouco máis. Entón, aquí, non importa como facer merge sort, vostede inevitablemente ten que utilizar un pouco de memoria extra. El ou ela creou unha nova matriz. E entón vostede di, ao final, só precisa copiar nova matriz para a matriz orixinal. [Estudante] Coido que si. Eu non sei se isto funciona en termos de contador de referencia ou o que sexa - Si, vai funcionar. >> [Alumno] Okay. Será que intente realizar isto? >> [Alumno] Non, aínda non. Ok >>. Probe executa-lo, e entón eu vou falar sobre iso por un segundo. [Alumno] Eu preciso ter todos os prototipos de función e todo, non? Os prototipos de función. Ah, quere dicir como - Si Ordenar está chamando mergeSortHelp. Entón, para que tipo de chamar mergeSortHelp, mergeSortHelp debe ser definido antes tipo ou só necesitamos do prototipo. Basta copiar e pegar isto. E do mesmo xeito, mergeSortHelp está chamando fundir, pero mesclagem non foi definido aínda, entón nós podemos só deixar mergeSortHelp saber que é iso que vai fundir a aparencia, e que é iso. Entón mergeSortHelp. Temos un problema aquí, onde temos ningún caso base. MergeSortHelp é recursiva, calquera función recursiva Vai ter algún tipo de caso base para saber cando deixar de chamar recursivamente si. O que é o noso caso base vai ser aquí? Si [Estudante] Se o tamaño é 1? >> [Bowden] Si Entón, como se viu alí, paramos matrices de división Unha vez que temos en matrices de tamaño 1, que inevitablemente están clasificados si. Entón, se o tamaño é igual a 1, sabemos que a matriz xa está clasificado, para que poidamos voltar só. Teña en conta que é baleiro, de modo que non voltar nada especial, só devolver. Okay. Entón, ese é o noso caso base. Eu creo que o noso caso base tamén podería ser se ocorrer de ser fusión dunha matriz de tamaño 0, Nós probablemente quere deixar nalgún momento, Así, podemos dicir tamaño inferior a 2 ou inferior ou igual a 1 de xeito que iso vai funcionar para calquera matriz agora. Okay. Entón, ese é o noso caso base. Agora se quere andar connosco a través fusión? O que todos estes casos significa? Ata aquí, nós estamos só facendo a mesma idea, o - [Estudante] Eu teño estar pasando tamaño, con todas as chamadas mergeSortHelp. Eu engade tamaño como unha primaria adicional e que non está aí, como o tamaño / 2. [Bowden] Oh, tamaño / 2, tamaño / 2. >> [Estudante] É, e tamén na función anterior, así. [Bowden] Aquí? >> [Alumno] Só o tamaño. >> [Bowden] Oh Tamaño, tamaño? >> [Estudante] Yeah. [Bowden] Okay. Deixe-me pensar por un segundo. Non nos atopamos con un problema? Estamos sempre tratar a esquerda como 0. >> [Alumno] Non Isto é malo tamén. Sentímolo. Debe ser partida. Si [Bowden] Okay. Gústame que mellor. E fin. Okay. Entón agora quere andar connosco a través fusión? >> [Alumno] Okay. Eu só estou pasando esta nova matriz que eu creei. O seu tamaño é o tamaño da parte da matriz que queremos ser clasificados e tentando atopar o elemento que eu debería poñer na etapa nova matriz. Entón, para facelo, primeiro eu estou comprobando a metade esquerda da matriz segue a ter máis elementos, e se iso non acontecer, entón vai para abaixo para que a condición máis, que só di Todo ben, debe estar no dereito de matriz, e imos poñer isto no índice actual de newArray. E entón, doutro xeito, eu estou comprobando o lado dereito da matriz tamén está rematado, caso en que eu só poñer na esquerda. Isto pode non ser realmente necesario. Non estou seguro. Pero de calquera xeito, a verificación de outros dous cal dos dous son menores na esquerda ou na dereita. E tamén, en cada caso, estou incrementando o que incrementar espazo reservado. [Bowden] Okay. Isto parece bo. Alguén ten comentarios ou preguntas ou preguntas? Así, os catro casos que temos que levar as cousas en só sendo - ou parece que cinco - pero temos que considerar a matriz de esquerda non ten máis cousas que necesitamos fundir, o dereito de matriz non ten máis cousas que precisamos unir - Estou apuntando para o nada. Entón, a matriz de esquerda non ten máis cousas ou o dereito de matriz non ten máis cousas. Estes son dous casos. Necesitamos tamén dun caso trivial de se a cousa esquerdo é menor que as cousas ben. Entón, nós queremos elixir a cousa esquerdo. Estes son os casos. Entón iso era certo, entón é iso. Matriz esquerda. E 1, 2, 3. Okay. Entón, si, esas son as catro cousas que pode querer facer. E nós non imos pasar por enriba dunha solución iterativa. Eu non recomenda - Fundir tipo é un exemplo dunha función que é ao mesmo tempo non a cola recursiva, non é fácil facer que a cola recursiva, pero tampouco é moi fácil facelo interactivo. Isto é moi fácil. Esta implementación do merge sort, funden, non importa o que fai, está indo para a construción de mesclagem. Entón, merge sort construída encima de mesturar recursivamente é só estas tres liñas. Iterativamente, é máis aburrido e máis difícil de pensar. Pero teña en conta que non é rabo recursiva dende mergeSortHelp - cando se chama a si mesma - aínda cómpre facer as cousas tras esta chamada retorna recursivas. Polo tanto, este cadro de pila debe continuar a existir mesmo tras chamar iso. E entón, cando chama iso, o cadro de pila debe continuar a existir porque, mesmo despois que a chamada, aínda necesitamos mesturar. E iso non é trivial para facer este rabo recursiva. Preguntas? Todo ben. Entón, volvendo a clasificar - Oh, hai dúas cousas que quero amosar. Okay. Volvendo ao tipo, imos facelo rápido. Ou investigación. Tipo? Ordenar. Si Volvendo aos inicios da especie. Queremos crear un algoritmo que ordena a matriz usando calquera algoritmo en O de n. Entón, como iso é posible? Alguén ten calquera tipo de - Suxerín antes - Se estamos a piques de mellorar a partir de n log n a O de n, temos mellorado o noso algoritmo en termos de tempo, o que significa que imos precisar facer para compensar iso? [Alumno] Espazo. Si >>. Nós imos estar usando máis espazo. E nin sequera só espazo, é exponencialmente máis espazo. Entón eu creo que este tipo de algoritmo é algo pseudo, pseudo polynom - pseudo - Eu non me lembro. Pseudo algo. Pero é porque necesitamos empregar tanto espazo que isto pode ser conseguido, pero non realista. E como imos conseguir isto? Podemos alcanzar iso garantir que algún determinado elemento da matriz é inferior a un determinado tamaño. Entón imos só dicir que o tamaño é de 200, calquera elemento dunha matriz é debaixo do tamaño 200. E iso é realmente moi realista. Pode moi facilmente ter unha matriz que sabe todo na mesma vai ser menor que o número. Como se ten algún vector absolutamente enorme ou algo pero xa sabe que todo vai estar entre 0 e 5, a continuación, que vai ser moito máis rápido para facelo. E o límite de calquera dos elementos é de 5, así que este límite, que é a cantidade de memoria que vai estar usando. Así, o límite é de 200. En teoría, sempre hai un límite desde un enteiro só pode ser de ata 4 millóns, pero iso é irreal, desde entón, estaría usando o espazo da orde de 4000 millóns. Entón, iso é irreal. Pero aquí imos dicir que o noso límite é 200. O truco para facelo en O de n é que facer unha outra matriz chamada conta de tamaño vinculado. Entón, en realidade, este é un atallo para - Eu realmente non sei se Clang fai iso. Pero no GCC, como mínimo - Clang asumindo estou fai iso tamén - iso só vai arrincar a matriz enteira para ser 0s. Entón, se eu non quere facelo, entón eu podería facer por separado for (int i = 0; i > Okay. Podo entender unha cousa, cando estabamos pasando. Creo que o problema estaba en Lucas e, probablemente, cada un que xa vimos. Eu esquezo completamente. O único que eu quería comentar é que cando está lidando con cousas como índices, nunca realmente ver iso cando está escribindo un loop, pero, técnicamente, sempre que está lidando con estes índices, ten que case sempre tratar con números enteiros sen signo. A razón para iso é cando está lidando con números enteiros asinados, por iso, se ten dous enteiros asinados e engadila los xuntos e eles acaban moi grande, entón acaba con un número negativo. Entón é iso que é estourido de enteiro. Se eu engadir 2 millóns e 1 billón, eu acabar con negativo 1 billón. É así que funciona en computadores enteiros. Así, o problema co uso - Isto é bo, excepto baixo pasa a ser 2 millóns e pasa a ser 1 billón, entón iso vai ser negativo 1 billón e, a continuación, imos dividir ese por dous e acabar con negativo de 500 millóns. Polo tanto, este é só un problema se ocorrer de estar buscando por unha matriz de millóns de cousas. Pero se + abaixo acontece a rebordar, entón iso é un problema. Así que facelos sen sinal, entón 2 millóns, máis 1 billón é 3 millóns. 3.000 millóns dividido por dous é de 1,5 millóns. Así, logo que eles están sen sinal, todo é perfecto. E por iso é tamén un problema cando está escribindo o seu loops, e realmente, probablemente fai iso automaticamente. Será realmente só berrar con vostede. Polo tanto, se ese número é moi grande para ser só un enteiro, pero que cabería nun enteiro non asinado, vai berrar con vostede, é por iso que nunca executar para a cuestión. Podes ver que un índice non vai ser negativo, e así, cando está interactuando sobre unha matriz, case sempre pode dicir unsigned int i, pero realmente non precisa. As cousas están indo para o traballo practicamente tan ben. Okay. [Sussurra] Que hora é? A última cousa que eu quería amosar - e eu vou facelo moi rápido. Vostede sabe como nós # define para que poidamos # define MAX como 5 ou algo así? Non imos facer MAX. # Establece límite como 200. Iso é o que fixemos antes. Que define unha constante, que só vai ser copiado e pegado onde queira que aconteza para escribir vinculado. Así, podemos realmente facer máis con # define. Podemos # define funcións. Eles non son realmente funcións, pero imos chamalos de funcións. Un exemplo sería algo así como MAX (x, y) é definida como (x > Ideal, 14. A cuestión é que, como define o traballo de hash, lembre que é unha copia literal e pegar de practicamente todo, entón o que é que isto vai ser interpretado como 3 é inferior a 1, máis 6, 2 veces 1 máis 6, 2 veces 3. Así, por esta razón, case sempre embrulhar todo entre parénteses. Calquera variable que case sempre embrulho en parénteses. Hai casos en que non ten que, como eu sei que eu non teño que facer iso aquí porque menos do que é practicamente sempre vai funcionar, a pesar de que pode ata non ser verdade. Se hai algo ridículo como DOUBLE_MAX (1 == 2), entón que vai estar substituído por 3 é igual a menos de 1 é igual a 2, E entón el vai facer 3 menor que 1, que igual a 2, o que non é o que queremos. Polo tanto, a fin de evitar os problemas de precedencia de operadores, sempre embrulho en parénteses. Okay. E é que, 5:30. Se tes algunha dúbida sobre o pset, aviso connosco. Debe ser divertido, ea edición hacker tamén é moito máis realista que a edición hacker do ano pasado, polo que esperamos que unha morea de tentar. O ano pasado, foi moi grande. [CS50.TV]