[Powered by Google Translate] [Sección 3 - Más Cómodo]
[Rob Bowden - Harvard University]
>> [Esta es CS50. - CS50.TV]
>> Así que la primera pregunta es extrañamente redactada.
GDB le permite "depurar" un programa, sino, más específicamente, ¿qué vamos hacer?
Voy a responder a eso, y yo no sé qué es exactamente lo esperado,
así que supongo que es algo a lo largo de las líneas de deja paso a paso
caminar a través del programa, interactuar con ella, las variables del cambio, hacer todas estas cosas -
básicamente completamente controlar la ejecución de un programa
e inspeccionar cualquier parte dada de la ejecución del programa.
Así que esas funciones le permiten depurar las cosas.
Bien.
¿Por qué la búsqueda binaria que requieren un arreglo pueden ordenar?
¿Quién quiere responder a eso?
[Estudiante] Porque no funciona si no está ordenada. Sí >>. [Risas]
Si no está ordenado, entonces es imposible que dividirlo por la mitad
y saber que todo a la izquierda es menor y todo a la derecha
es mayor que el valor medio.
Así que tiene que ser resuelto.
Bien.
¿Por qué es una especie de burbuja en O del cuadrado n?
¿Hay alguien que primero quiere dar una muy rápida visión general de alto nivel de burbuja qué tipo es?
[Estudiante] Es, básicamente, a través de cada elemento y compruebe los elementos primeros.
Si están fuera de donde cambiarlos, luego de comprobar los elementos próximos y así sucesivamente.
Al llegar a la final, entonces usted sabe que el mayor elemento se coloca en el extremo,
por lo que ignorar aquel entonces sigues pasando,
y cada vez que tiene que comprobar un elemento menos hasta que se haga ningún cambio. Sí >>.
Se llama tipo burbuja, porque si le da la vuelta el conjunto de su lado por lo que es arriba y hacia abajo, vertical,
a continuación, los valores grandes se hunden hasta el fondo y los valores pequeños se burbuja hasta la parte superior.
Esa es la forma en que obtuvo su nombre.
Y sí, que acaba de pasar.
Sigues yendo a través de la matriz, cambiando el valor mayor
para obtener los valores más grandes para la parte inferior.
>> ¿Por qué es O cuadrado de n?
En primer lugar, ¿alguien quiere decir eso que es de O n al cuadrado?
[Estudiante] Debido a que para cada carrera se va n veces.
Sólo se puede estar seguro de que usted ha tomado el elemento más grande hasta el fondo,
entonces usted tiene que repetir eso para tantos elementos. Sí >>.
Así que tenga en cuenta lo grande O significa y qué grandes medios Omega.
El O grande es como el límite superior de lo lento que en realidad se puede ejecutar.
Así que decir que es de O n al cuadrado, no es de O n o de lo que sería capaz de ejecutar
en el tiempo lineal, pero es O de n cubos
porque está limitada por O de n cubos.
Si está acotado por O cuadrado de n, entonces es acotada también por n en cubos.
Por lo tanto, es n al cuadrado, y en el caso peor absoluto que no puede hacer mejor que cuadrada n,
que es por eso que es O de n al cuadrado.
Así que para ver las matemáticas leve en la forma en que viene a ser n al cuadrado,
si tenemos cinco cosas en nuestra lista, por primera vez cómo los swaps muchos podríamos potencialmente necesitan para tomar
con el fin de conseguir esto? Que en realidad sólo -
Cómo swaps muchos vamos a tener que hacer en la primera ejecución de la ordenación de burbuja a través de la matriz?
[Estudiante] n - 1. Sí >>.
>> Si hay 5 elementos, vamos a tener que hacer n - 1.
Luego, en la segunda como swaps muchos vamos a tener que hacer?
[Estudiante] n - 2. Sí >>.
Y la tercera va a ser n - 3 y, a continuación por conveniencia escribiré los dos últimos
como entonces vamos a tener que hacer 2 swaps y swaps 1.
Supongo que el último puede o no puede necesitar realmente a suceder.
Se trata de un intercambio? No se.
Así que estas son las cantidades totales de swaps o por lo menos comparaciones que tienen que hacer.
Incluso si usted no intercambia, usted todavía necesita para comparar los valores.
Así que hay n - 1 comparaciones en la primera pasada a través de la matriz.
Si reorganiza estas cosas, vamos a realmente hacer seis cosas para apilar las cosas muy bien,
y luego voy a hacer 3, 2, 1.
Así que reorganizar estas sumas, queremos ver cómo muchas comparaciones que hacemos
en el algoritmo completo.
Así que si traemos a estos chicos por aquí,
entonces estamos siendo sólo suma comparaciones sin embargo muchos no lo eran.
Pero si sumamos estos y sumamos estos y sumamos estos,
que sigue siendo el mismo problema. Acabamos de resumir esos grupos en particular.
>> Así que ahora estamos sumando los 3 n. No se trata sólo de 3 n.
Siempre va a ser n / 2 n de.
Así que aquí sucede que tiene 6.
Si tuviéramos 10 cosas, entonces podríamos hacer esta agrupación para 5 pares diferentes de cosas
y terminar con n + n + n + n + n.
Así que siempre vas a obtener n / 2 n, y por lo que este lo vamos a apuntar a n al cuadrado / 2.
Y así, a pesar de ser el factor de la media, que pasa a ser en
por el hecho de que a través de cada iteración en la matriz se comparan menos 1
así es como conseguimos el sobre 2, pero sigue siendo n al cuadrado.
No me importa el factor constante de la mitad.
Así que un montón de grandes cosas O como esto se basa en un solo tipo de hacer esta clase de matemáticas,
haciendo sumas aritméticas y cosas serie geométrica,
pero la mayoría de ellos en este curso son bastante sencillos.
Bien.
¿Por qué es la ordenación por inserción en Omega de n? ¿Qué omega decir?
[Dos estudiantes que hablan a la vez - ininteligible] >> Yeah.
Omega se puede considerar como el límite inferior.
>> Así que no importa qué tan eficiente es su algoritmo de ordenación por inserción es,
independientemente de la lista que se pasa adentro, siempre hay que comparar al menos n cosas
o tiene que iterar n cosas.
¿Por qué es eso?
[Estudiante] Porque si la lista ya está ordenado, y luego a través de la primera iteración
sólo se puede garantizar que el primer elemento es el menor,
y la segunda iteración sólo se pueden garantizar las dos primeras son
porque no saben que el resto de la lista está ordenada. Sí >>.
Si usted pasa en una lista completamente ordenados, por lo menos tienes que ir a través de todos los elementos
para ver que nada necesita ser movido alrededor.
Así que pasando por encima de la lista y diciendo oh, esto ya está clasificado,
es imposible que usted sepa que está ordenados hasta que marque cada elemento
para ver de que están en el orden establecido.
Así que el límite inferior de la ordenación por inserción es Omega de n.
¿Qué es el peor de los casos el tiempo de funcionamiento de tipo fusión,
peor caso es O grandes otra vez?
Así que en el peor de los casos, ¿cómo ordenar fusión correr?
[Estudiante] N log n. Sí >>.
Los más rápidos algoritmos generales de ordenación son n log n. No se puede hacer mejor.
>> Hay casos especiales, y si tenemos tiempo hoy - pero probablemente no verán -
pudimos ver uno que lo haga mejor que n log n.
Pero en el caso general, no se puede hacer nada mejor que n log n.
Y combinar especie pasa a ser el que usted debe saber para este curso que es n log n.
Y por lo que en realidad va a ser la aplicación de dicho hoy.
Y, por último, en no más de tres frases, ¿cómo funciona la selección de clase?
¿Alguien quiere contestar, y yo te cuente sus penas
porque si usted se pasa de 3 -
¿Alguien recuerda tipo de selección?
Tipo de selección es por lo general bastante fácil de recordar sólo por el nombre.
Usted acaba de recorrer el array, encontrar lo que es el valor más grande o más pequeño -
el orden que le toque lavar pulg
Así que digamos que estamos ordenar de menor a mayor.
Usted iterar sobre la matriz, en busca de lo que es el elemento mínimo,
selecciónelo y, a continuación, sólo cambiar lo que está en el primer lugar.
Y luego, en la segunda pasada a través de la matriz, busque el elemento mínimo de nuevo,
selecciónelo y, a continuación, intercambiarlo con lo que está en la segunda posición.
Así que sólo estamos escogiendo y seleccionando los valores mínimos
y su inserción en la parte frontal de la matriz hasta que se ordena.
Las preguntas sobre eso?
>> Estos inevitablemente aparecen en los formularios que tienen que llenar cuando usted está presentando el conjunto de procesadores.
Estos son, básicamente, las respuestas a ellos.
Bien, ahora codificación problemas.
Ya he enviado por correo electrónico - ¿Nadie conseguir que el correo electrónico? Bien.
Ya he enviado por correo electrónico el espacio que vamos a utilizar,
y si haces click en mi nombre - así que creo que voy a estar en el fondo
debido a la r hacia atrás - pero si haces click en mi nombre verás dos revisiones.
Revisión 1 va a ser que ya copiar y pegar el código en los espacios
por lo que la búsqueda va a tener que poner en práctica.
Y Revisión 2 será lo tipo que ponemos en práctica después de eso.
Así que usted puede hacer clic en mi Revisión 1 y trabajar desde allí.
Y ahora queremos implementar la búsqueda binaria.
>> ¿Alguien quiere dar sólo un pseudocódigo de alto nivel explicación
de lo que vamos a tener que hacer para la búsqueda? Si.
[Estudiante] Usted acaba de tomar el centro de la matriz y ver si lo que estás buscando
es menor que o más que eso.
Y si es menos, vas a la parte que es menos,
y si es más, te vas a la media que es más y repetir hasta que usted acaba de conseguir una cosa.
[Bowden] Yeah.
Tenga en cuenta que nuestra matriz de números ya está ordenado,
y por lo que significa que podemos tomar ventaja de eso y pudimos comprobar en primer lugar,
bien, estoy buscando el número 50.
Para que pueda entrar en el centro.
Medio es difícil de definir, cuando es un número par de cosas,
pero digamos que siempre vamos a truncar a la mitad.
Así que aquí tenemos 8 cosas, por lo que la media sería de 16.
Estoy buscando a 50, así que 50 es mayor que 16.
Así que ahora, básicamente, puede tratar mi matriz como estos elementos.
Puedo tirar todo a partir de 16 años.
Ahora mi matriz es sólo estos 4 elementos, y lo repito.
Así que quiero encontrar el medio más, que va a ser 42.
42 es menor que 50, por lo que puedo tirar estos dos elementos.
Este es mi arsenal restante.
Voy a encontrar el medio de nuevo.
Supongo que 50 era un mal ejemplo porque siempre estaba tirando cosas a la izquierda,
pero en la misma medida, si estoy buscando algo
y es menor que el elemento que estoy mirando,
entonces voy a tirar todo a la derecha.
Así que ahora tenemos que aplicar eso.
Tenga en cuenta que tenemos que pasar de tamaño.
No podemos también deben codificar tamaño.
Así que si nos deshacemos de que # define -
Bien.
¿Cómo puedo averiguar muy bien cuál es el tamaño de la matriz de números en la actualidad es?
>> ¿Cuántos elementos hay en la matriz números?
[Estudiantes] Los números, paréntesis,. Longitud?
[Bowden] Eso no existe en C.
Necesidad. Longitud.
Las matrices no tienen propiedades, por lo que no hay ninguna propiedad de las matrices de longitud
que sólo le dará el tiempo que pasa a ser.
[Estudiante] Ver la cantidad de memoria que tiene y dividir por la cantidad - >> Yeah.
Entonces, ¿cómo podemos saber cuánta memoria tiene? >> [Estudiante] sizeof. >> Sí, sizeof.
Sizeof es el operador que va a devolver el tamaño de la matriz de números.
Y eso va a ser enteros sin embargo hay muchas veces el tamaño de un entero
ya que es la cantidad de memoria que está realmente tomando.
Así que si desea que el número de cosas en la matriz,
entonces voy a querer dividir por el tamaño de un entero.
Bien. Así que me permite pasar de tamaño aquí.
¿Por qué tengo que pasar en tamaño después de todo?
¿Por qué no puedo hacer aquí int size = sizeof (pajar) / sizeof (int)?
¿Por qué no funciona?
[Estudiante] No es una variable global.
[Bowden] Haystack existe y estamos pasando en números como pajar,
y esto es una especie de presagio de lo que vendrá. Si.
[Estudiante] Haystack es sólo la referencia a la misma, por lo que volvería lo grande que es de referencia.
Si.
Dudo que en la conferencia que ha visto la pila todavía realmente, ¿verdad?
Hemos hablado sobre ello.
Así que la pila es donde todas las variables se van a almacenar.
>> Cualquier memoria que está asignada para las variables locales va en la pila,
y cada función tiene su propio espacio en la pila, su propio marco de pila es lo que se llama.
Así que tiene su principal marco de pila, y dentro de ella va a existir esta matriz números,
y que va a ser de tamaño sizeof (números).
Va a tener el tamaño de los números dividido por el tamaño de los elementos,
sino que todas las vidas dentro de marco de pila principal.
Cuando llamamos a la búsqueda, búsqueda obtiene su propio marco de pila,
su propio espacio para almacenar todas sus variables locales.
Pero estos argumentos - así pajar no es una copia de esta matriz completa.
No entregamos en todo el conjunto como una copia en la búsqueda.
Apenas pasa una referencia a la matriz.
Así búsqueda puede acceder a estos números a través de esta referencia.
Es todavía el acceso a las cosas que viven en el interior del marco de pila principal,
pero en el fondo, cuando lleguemos a los punteros, que debe ser breve,
esto es lo que los punteros son.
Los punteros son sólo referencias a las cosas, y se puede utilizar punteros para acceder a las cosas
que se encuentran en los marcos de pila otras cosas.
Así que, aunque el número es local principal, todavía puede acceder a él a través de este puntero.
Pero ya que es simplemente un puntero y es sólo una referencia,
sizeof (pajar) sólo devuelve el tamaño de la misma referencia.
No devuelve el tamaño de lo que está señalando.
No devuelve el tamaño real de los números.
Y para que esto no va a funcionar como se desea.
>> Las preguntas sobre eso?
Los punteros se habrá ido en detalle mucho más sangriento en las semanas por venir.
Y esta es la razón por un montón de cosas que se ven, la mayoría de las cosas o las cosas de orden de búsqueda,
son casi todos vamos a tener que tomar el tamaño real de la matriz,
porque en C, no tenemos idea de lo que el tamaño de la matriz es.
¡Tienes que pasar manualmente pulg
Y no se puede pasar manualmente en toda la matriz, ya que está de paso en la referencia
y no se puede obtener el tamaño de la referencia.
Bien.
Así que ahora queremos poner en práctica lo que se ha explicado anteriormente.
Puede trabajar en él durante un minuto,
y usted no tiene que preocuparse de conseguir todo perfectamente 100% de trabajo.
Sólo tiene que escribir el pseudocódigo medio de cómo creo que debería funcionar.
Bien.
No hay necesidad de estar completamente terminado con esto.
Pero, ¿alguien se sienta cómodo con lo que tengo hasta ahora,
como algo que podemos trabajar de forma conjunta?
¿Alguien quiere ser voluntario? O escogerán aleatoriamente.
No tiene que ser justo por cualquier medida, sino algo que puede modificar en un estado de trabajo.
[Estudiante] Claro. >> Okay.
Así se puede ahorrar la revisión haciendo clic en el pequeño icono Guardar.
Usted es Ramya, ¿verdad? >> [Estudiante] Yeah. >> [Bowden] Bueno.
Así que ahora puedo ver su revisión y todo el mundo puede levantar la revisión.
Y aquí tenemos - Está bien.
Así fue con Ramya la solución recursiva, que es definitivamente una solución válida.
Hay dos maneras que usted puede hacer este problema.
Usted puede hacerlo iterativamente o recursivamente.
La mayoría de los problemas que encuentre que se puede hacer de forma recursiva también puede realizarse iterativamente.
Así que aquí lo hemos hecho de forma recursiva.
>> ¿Alguien quiere definir lo que significa hacer una función recursiva?
[Estudiante] Cuando se tiene una función propia llamada
y luego llamar a sí mismo hasta que salga con verdadero y cierto. Sí >>.
Una función recursiva es una función que se llama a sí misma.
Hay tres cosas importantes que una función recursiva debe tener.
La primera es, obviamente, se llama a sí misma.
El segundo es el caso base.
Así que en algún punto la función tiene que dejar de llamar a sí mismo,
y eso es lo que el caso base es para.
Así que aquí sabemos que debemos dejar, debemos renunciar a nuestra búsqueda
cuando el inicio es igual a extremo - y vamos a repasar lo que eso significa.
Pero, finalmente, la última cosa que es importante para las funciones recursivas:
las funciones de alguna manera debe abordar la causa base.
Al igual que si usted no está realmente actualizar nada cuando usted hace la llamada recursiva en segundo lugar,
si usted está literalmente a la llamada a la función de nuevo con los mismos argumentos
y no hay variables globales han cambiado ni nada,
usted nunca alcanzará el caso base, en cuyo caso eso es malo.
Será una repetición infinita y un desbordamiento de pila.
Pero aquí vemos que la actualización está ocurriendo desde que se inicia la actualización + final / 2,
estamos actualizando el argumento final aquí, estamos actualizando el argumento de inicio aquí.
Así, en todas las llamadas recursivas estamos actualizando algo. Bien.
¿Quieres que nos guiará a través de su solución? >> Claro.
Estoy usando SearchHelp de modo que cada vez que hago esta llamada de función
Tengo el principio de donde yo estoy buscando en la matriz y el fin
de donde yo estoy buscando la matriz.
>> A cada paso, donde se dice que es el elemento central, que es inicio + final / 2,
que es igual a lo que estamos buscando?
Y si es así, entonces que lo encontramos, y supongo que se pasa a los niveles de recursividad.
Y si eso no es cierto, entonces se comprueba si el valor medio de la matriz es demasiado grande,
en cuyo caso nos fijamos en la mitad izquierda de la matriz por va desde el comienzo hasta el índice medio.
Y otra cosa que hacemos la media final.
[Bowden] Bueno.
Eso parece bien.
Está bien, así que un par de cosas, y de hecho, esto es una cosa muy alto nivel
que usted nunca tendrá que saber para este curso, pero es cierto.
Las funciones recursivas, que siempre se oye que son un mal negocio
porque si se llama a sí mismo de forma recursiva demasiadas veces, se obtiene desbordamiento de pila
ya que, como he dicho antes, cada función tiene su propio marco de pila.
Así que cada llamada de la función recursiva obtiene su propio marco de pila.
Así que si usted hace 1.000 llamadas recursivas, se obtiene 1.000 marcos de pila,
y rápidamente le llevará a tener marcos de pila demasiadas cosas y acaba de romper.
Por eso es que las funciones recursivas son generalmente malos.
Pero hay un subconjunto de las funciones recursivas agradable llamado cola de funciones recursivas,
y este pasa a ser un ejemplo de uno en el que si el compilador nota esto
y debe ser, creo - en Clang si se le pasa la bandera-O2
entonces se dará cuenta de esto es la cola recursiva y hacer las cosas bien.
>> Se volverá a utilizar el mismo marco de pila y otra vez para cada llamada recursiva.
Y ya que estás utilizando el mismo marco de pila, usted no tiene que preocuparse acerca de
nunca apilar desbordante, y al mismo tiempo, como dijiste antes,
donde una vez que regrese cierto, entonces hay que devolver todo lo de estos marcos de pila
y la llamada del 10 al SearchHelp tiene que regresar a los días 9, tiene que regresar a la 8a.
Así que no es necesario que ocurra cuando las funciones son cola recursiva.
Y así, lo que hace que esta función recursiva de cola es un aviso de que para cualquier llamada de atención a searchHelp
la llamada recursiva que está haciendo es lo que está regresando.
Así, en la primera llamada a SearchHelp, que sea inmediatamente devolver false,
inmediatamente devolver true, o se hace una llamada recursiva a SearchHelp
donde lo que estamos regresando es lo que esa llamada está regresando.
Y no podríamos hacer esto si lo hiciéramos algo como int x = SearchHelp, return x * 2,
sólo algunos cambios al azar.
>> Así que ahora esta llamada recursiva, esta int x = SearchHelp llamada recursiva,
ya no es la cola recursiva, ya que en realidad tiene que volver
de nuevo a un marco de pila anterior para que esa llamada previa a la función
A continuación, puede hacer algo con el valor de retorno.
Así que esto no es la cola recursiva, pero lo que teníamos antes es bien cola recursiva. Si.
[Estudiante] ¿No debería el caso de la segunda base se comprueba en primer lugar
porque podría haber una situación en la que cuando se le pasa el argumento
ha empezar = fin, sino que son el valor de la aguja.
La pregunta fue ¿no podemos correr en el caso extremo es el valor de aguja
o empezar = fin, apropiadamente, inicie final =
y no se han comprobado que determinado valor, sin embargo,
a continuación, iniciar + final / 2 es sólo va a ser el mismo valor.
Pero ya hemos vuelto falso y que en realidad nunca comprobado el valor.
Así que al menos, en la primera convocatoria, si el tamaño es 0, entonces queremos devolver false.
Pero si el tamaño es 1, entonces comienzo no va a terminar igual,
y vamos a comprobar al menos el único elemento.
Pero creo que tienes razón en que puede terminar en un caso en el inicio + final / 2,
inicio termina siendo la misma que inicio + final / 2,
pero nunca hemos hecho el check ese elemento.
>> Así que si buscamos en primer lugar es el elemento central del valor que estamos buscando,
entonces puede regresar inmediatamente verdad.
Porque si son iguales, entonces no hay razón para continuar
ya que sólo vamos a actualizar a un caso en el que nos encontramos en una matriz de un solo elemento.
Si ese elemento no es el que estamos buscando,
entonces todo lo que está mal. Si.
[Estudiante] El caso es que ya que el tamaño es más grande que el número de elementos en la matriz,
ya hay un offset - >> Lo mismo ocurrirá con el tamaño -
[Estudiante] Di si la matriz era de tamaño 0, entonces el SearchHelp realmente comprobar pajar de 0
en la primera llamada.
La matriz tiene un tamaño 0, por lo que el 0 es - >> Yeah.
Hay otra cosa que - puede ser bueno. Vamos a pensar.
Así que si la matriz con 10 elementos y el del medio que vamos a revisar es el índice de 5,
por lo que estamos comprobando 5, y digamos que el valor es menor.
Así que estamos tirando todo por la borda a partir del 5 en adelante.
Así que empieza a + final / 2 va a ser nuestro nuevo final,
así que sí, que siempre va a estar más allá del final de la matriz.
Si se trata de un caso si era par o impar, entonces podríamos comprobar, por ejemplo, 4,
pero todavía estamos desperdiciando -
Así que sí, al final siempre va a estar más allá del final real de la matriz.
De modo que los elementos que nos estamos centrando, final siempre va a ser el que después de eso.
Y así, si hace arranque termina nunca igual, estamos en una matriz de tamaño 0.
>> La otra cosa que estaba pensando es que estamos actualizando el principio hasta el final se inicio + / 2,
por lo que este es el caso que estoy teniendo problemas con, por dónde empezar + final / 2
es el elemento que está comprobando.
Vamos a decir que tuvimos esta matriz de 10 elementos. Lo que sea.
Así que empieza a + final / 2 va a ser algo así como éste,
y si ese no es el valor, digamos que desea actualizar.
El valor es mayor, por lo que desee ver en esta mitad de la matriz.
Entonces, ¿cómo estamos actualizando principio, estamos actualizando principio para ser ahora este elemento.
Pero esto todavía puede funcionar, o por lo menos, puede hacer start + final / 2 + 1.
[Estudiante] No es necesario que se comience final + [inaudible] >> Si.
Ya hemos comprobado este elemento y sé que no es la que estamos buscando.
Así que no es necesario actualizar principio para ser este elemento.
Sólo podemos saltar y actualizar empezar a ser este elemento.
¿Y hay alguna vez un caso, vamos a decir, que esto fuera final,
así entonces empezar sería esto, inicie + final / 2 sería esto,
empezar final + - Sí, creo que puede terminar en una recursión infinita.
Vamos a decir que es una matriz de tamaño 2 o una matriz de tamaño 1. Creo que esto va a funcionar.
Así en la actualidad, es que inicio y final elemento es 1 más allá de ella.
De modo que el elemento que vamos a comprobar es éste,
y luego, cuando nos ponemos al día de inicio, estamos actualizando principio para ser 0 + 1/2,
que nos va a terminar de nuevo con arranque siendo este elemento.
>> Así que estamos comprobando el elemento mismo una y otra vez.
Así que este es el caso en el que cada llamada recursiva en realidad debe actualizar algo.
Así que tenemos que hacer start + final / 2 + 1, o si no hay un caso
donde no estamos en realidad la actualización inicial.
Todo el mundo ve eso?
Bien.
¿Alguien tiene alguna pregunta sobre esta solución o más comentarios?
Bien. ¿Alguien tiene una solución iterativa que todos podamos mirar?
¿Sabía que todos lo hacen de forma recursiva?
O también supongo que si ella se abrió, entonces usted podría tener anulado su anterior.
¿Se guarda automáticamente? Yo no soy positivo.
¿Alguien ha iterativo?
Podemos caminar a través de ella juntos si no.
La idea va a ser el mismo.
Solución iterativa.
Vamos a querer hacer básicamente la misma idea
dónde queremos llevar la cuenta del nuevo final de la matriz y el nuevo comienzo de la matriz
y hacer eso una y otra vez.
Y si lo que estamos hacer el seguimiento de como el inicio y el final nunca se cruzan,
entonces nosotros no lo encontramos y nos puede devolver false.
Entonces, ¿cómo puedo hacer eso? Alguien tiene sugerencias o código para que yo tire hacia arriba?
[Estudiante] Hacer un bucle while. Sí >>.
Usted va a querer hacer un bucle.
>> ¿Usted tiene un código que podría tirar para arriba, o lo que se le va a sugerir?
[Estudiante] Creo que sí. >> Está bien. Esto hace las cosas más fáciles. ¿Cuál era su nombre?
[Estudiante] Lucas.
Revisión 1. Bien.
Menor es lo que llamamos comenzar antes.
Hasta no es exactamente lo que llamábamos antes de final.
En realidad, está ahora al final de la matriz. Es un elemento que debemos considerar.
Así bajo es 0, arriba es el tamaño de la matriz - 1,
y ahora estamos bucle, y la comprobación se -
Supongo que se puede caminar a través de él.
¿Cuál fue su pensamiento a través de esto? Camina con nosotros a través de su código.
[Estudiante] Claro. Fíjese en el valor pajar en el centro y compararla con la aguja.
Así que si es mayor que su aguja, entonces usted quiere - ¡Oh, en realidad, debería ser al revés.
Usted va a querer tirar la mitad derecha, por lo que sí, que debe ser el camino.
[Bowden] Así que esto debe ser menos? ¿Es eso lo que dijiste? >> [Estudiante] Yeah.
[Bowden] Bueno. Menos.
Así que si lo que estamos viendo es más pequeño que lo que queremos,
entonces sí, queremos tirar la mitad izquierda,
lo que significa que estamos actualizando todo lo que estamos considerando
moviendo bajo a la derecha de la matriz.
Esto se ve bien.
Creo que tiene el mismo problema que hemos dicho en el anterior,
donde si baja es 0 y hasta es 1, entonces bajo hasta + / 2 se va a establecer a ser lo mismo otra vez.
>> E incluso si ese no es el caso, todavía es más eficiente por lo menos
a tiro de lejos el elemento que acabamos de ver que sabemos que está mal.
Así que bajo + arriba / 2 + 1 - >> [estudiante] Eso debería ser al contrario.
[Bowden] O esto debería ser - 1 y el otro debe ser + 1.
[Estudiante] Y debe haber un doble signo igual. >> [Bowden] Yeah.
[Estudiante] Yeah.
Bien.
Y, por último, ahora que tenemos este 1 + - 1 cosa,
es que - puede que no sea - es siempre posible bajo para terminar con un valor mayor de hasta?
Creo que la única forma en que puede suceder - ¿Es posible? >> [Estudiante] No lo sé.
Pero si se pone truncada y luego se hace menos que 1 y luego - >> Yeah.
[Estudiante] Es, posiblemente, llegar en mal estado.
Creo que debería ser bueno sólo porque
para que termine inferior tendrían que ser igual, creo.
Pero si son iguales, entonces no habría hecho el bucle while para empezar
y nos habría devuelto el valor. Así que creo que estamos bien ahora.
Observe que aunque este problema ya no es recursivo,
el mismo tipo de ideas se aplican en el que podemos ver cómo esto tan fácilmente se presta
a una solución recursiva por el hecho de que estamos sólo la actualización de los índices de una y otra vez,
estamos haciendo el problema más pequeño, nos estamos centrando en un subconjunto de la matriz.
[Estudiante] Si baja es 0 y hasta es 1, los dos estarían 0 + 1/2, que iría a 0,
y entonces uno sería + 1, uno sería - 1.
[Estudiante] ¿Dónde estamos comprobando la igualdad?
Al igual que si el medio es realmente aguja?
No estamos actualmente haciendo eso? Oh!
Si es -
Sí. No podemos limitarnos a hacer la prueba aquí porque digamos que la primera mitad -
[Estudiante] De hecho, es como no tirar el encuadernado.
Así que si usted lanza lejos el límite, usted tiene que comprobar primero o lo que sea.
Ah. Si. >> [Estudiante] Yeah.
Así que ahora que hemos tirado la que actualmente mirado,
lo que significa que ahora tenemos que tener también
if (pajar [(baja + hasta) / 2] == aguja), entonces se puede volver realidad.
Y si me pongo más o simplemente si, significa literalmente la misma cosa
porque esto habría vuelto realidad.
Así que voy a poner otro si, pero no importa.
>> Así que si esta cosa, de lo contrario esto, y esto es una cosa común que hago
donde incluso si es el caso en el que todo está bien aquí,
como bajo no puede ser nunca superior a la pata, no es digno de razonamiento acerca de si eso es cierto.
Así que usted puede también decir mientras baja es menor o igual a
o mientras bajo es menor que
por lo que si es que alguna vez sucede igual o menor a dejarla pasar,
entonces podemos salir de este bucle.
Preguntas, inquietudes, comentarios?
Bien. Esto se ve bien.
Ahora queremos hacer una especie.
Si vamos a mi segunda revisión, vemos estos mismos números,
pero ahora ya no están en orden.
Y queremos implementar utilizando cualquier tipo algoritmo en O de n log n.
Entonces, ¿qué algoritmo crees que deberíamos aplicar aquí? >> [Estudiante] tipo de mezcla.
[Bowden] Yeah. Combinar tipo es O (n log n), así que eso es lo que vamos a hacer.
Y el problema va a ser bastante similar,
donde se presta fácilmente a una solución recursiva.
También podemos llegar a una solución iterativa si queremos,
pero recursión será más fácil aquí y debemos hacer recursividad.
Supongo que tendremos una caminata por tipo de mezcla en primer lugar,
aunque hay un video precioso sobre tipo de combinación ya. [Risas]
Así merge sort hay - me estoy perdiendo gran parte de este trabajo.
Oh, sólo hay una izquierda.
Así se fusionan.
Oh, 1, 3, 5.
Bien.
Merge toma dos matrices independientes.
Individualmente esas dos matrices son ambos ordenados.
Así esta matriz, 1, 3, 5, ordenados. Esta matriz, 0, 2, 4, ordenados.
Ahora, ¿qué combinación debe hacer es combinarlos en una sola matriz que es a su vez ordenados.
Por eso queremos una matriz de tamaño 6 que va a tener estos elementos dentro de ella
de forma ordenada.
>> Y así podemos aprovechar el hecho de que estos dos conjuntos se ordenan
hacerlo en un tiempo lineal,
sentido del tiempo lineal si esta matriz es x tamaño y ésta es y tamaño,
entonces el algoritmo total debe ser O (x + y). Bien.
Así sugerencias.
[Estudiante] Podríamos empezar por la izquierda?
Así que voy a poner el 0 abajo primero y luego el 1 y luego aquí estás en el 2.
Así que es algo así como tiene una ficha que se mueve hacia la derecha. >> [Bowden] Yeah.
Para ambos conjuntos si sólo se centran en el elemento más a la izquierda.
Debido a que ambos conjuntos se ordenan, se sabe que estos dos elementos
son los elementos más pequeños, ya sea en matriz.
Así que eso significa que 1 de los 2 elementos deben ser el elemento más pequeño de nuestra gama combinada.
Lo que pasa es que el más pequeño es el de la derecha esta vez.
Así que tomamos 0, insertarlo en la izquierda, porque 0 es menor que 1,
así que 0, la inserta en nuestra posición, y luego actualizamos esta
a centrarnos ahora en el primer elemento.
Y ahora lo repetimos.
Así que ahora comparamos 2 y 1. 1 es más pequeña, así que vamos a insertar 1.
Actualizamos este puntero para apuntar a este chico.
Ahora tenemos que hacerlo de nuevo, así que 2. Esto actualizará, comparar estos 2, 3.
Esto actualiza, luego 4 y 5.
Así que es de mezcla.
>> Debe ser bastante obvio que es el tiempo lineal ya que sólo tiene que ir a través de cada elemento de una vez.
Y ese es el paso más importante para la implementación especie de mezcla está haciendo esto.
Y no es tan difícil.
Un par de cosas de que preocuparse es que vamos a decir que nos fusión 1, 2, 3, 4, 5, 6.
En este caso, terminan en el escenario en el que éste va a ser más pequeño,
luego actualizamos este puntero, éste va a ser más pequeños, actualizar esto,
éste es más pequeño, y ahora usted tiene que reconocer
cuando realmente has quedado sin elementos para comparar.
Puesto que ya hemos utilizado este arsenal entero,
todo este conjunto ahora se acaba de insertar en aquí.
Así que si alguna vez llegas a tener el punto de que uno de nuestros arrays está totalmente fusionado ya,
entonces simplemente tomar todos los elementos de la otra matriz e insertarlos en el final de la matriz.
Así que sólo se puede insertar 4, 5, 6. Bien.
Eso es una cosa a tener en cuenta.
Implementación que debe ser el paso 1.
Combinar ordenar luego en base a eso, es 2 pasos, 2 pasos tontos.
Vamos a dar a esta matriz.
Así merge sort, el paso 1 es romper la matriz recursivamente en dos mitades.
Así que dividir este conjunto en dos mitades.
Ahora tenemos 4, 15, 16, 50 y 8, 23, 42, 108.
Y ahora lo hacemos de nuevo y nos separamos estos en dos mitades.
Yo sólo voy a hacer en este lado.
Así 4, 15 y 16, 50.
Haríamos lo mismo aquí.
Y ahora lo dividimos por la mitad otra vez.
Y tenemos 4, 15, 16, 50.
Así que ese es nuestro caso base.
Una vez que las matrices son de tamaño 1, entonces se detiene con la división en dos mitades.
>> Ahora, ¿qué hacemos con esto?
Terminamos esto también se dividen en 8, 23, 42, y 108.
Así que ahora que estamos en este momento, ahora paso dos de tipo de combinación es simplemente la fusión de pares para las listas.
Así que queremos fusionar estos. Acabamos de llamar a fusionarse.
Sabemos fusión volverá éstos en el orden establecido.
4, 15.
Ahora queremos unir estos, y que devolverá una lista con los registros en orden,
16, 50.
Nos fusionamos aquellos - que no puedo escribir - 8, 23 y 42, 108.
Así que tenemos pares fusionados vez.
Ahora sólo nos queda unir de nuevo.
Tenga en cuenta que cada una de estas listas se ordenan por sí misma,
y entonces solo puede combinar estas listas para obtener una lista de tamaño 4, que se clasifica
y fusionar estas dos listas para obtener una lista de tamaño 4, que está ordenada.
Y, por último, podemos fusionar esos dos listas de tamaño 4 para obtener una lista de tamaños de 8, que está ordenada.
Así que a ver que esto es general n log n, ya vimos que merge es lineal,
así que cuando nos enfrentamos a la fusión de estos, así como el costo total de fusión
para estas dos listas está a sólo 2 porque -
O bien, es de S n, n pero aquí es sólo estos dos elementos, por lo que es 2.
Y estos 2 será 2 y estos 2 será 2 y estos 2 será 2,
así que a través de todas las fusiones que tenemos que hacer, terminamos haciendo n.
Al igual que 2 + 2 + 2 + 2 es 8, que es N,
por lo que el coste de la combinación de este conjunto es n.
Y lo mismo aquí.
Vamos a combinar estos 2, entonces estos 2, y de forma individual esta fusión se llevará a cuatro operaciones,
esta fusión se llevará a cuatro operaciones, pero una vez más, entre todos ellos,
terminamos la fusión n las cosas en conjunto, por lo que este paso toma n.
Y así, cada nivel tiene n elementos se fusionaron.
>> Y ¿Cuántos niveles hay?
En cada nivel, nuestra matriz crece en tamaño 2.
Aquí nuestras matrices son de tamaño 1, aquí son de tamaño 2, aquí son de tamaño 4,
y, por último, son de tamaño 8.
Así que ya que se duplica, va a haber un total de log n de estos niveles.
Así que con log n niveles, cada nivel individual teniendo n total de operaciones,
obtenemos un log n n algoritmo.
¿Preguntas?
¿La gente ya se ha avanzado en la forma de aplicar esto?
¿Hay alguien ya en un estado en el que sólo puede levantar su código?
Me puede dar un minuto.
Este va a ser más larga.
Recomiendo altamente recurrentes -
Usted no tiene que hacer recursividad para fusión
porque para hacer recursividad para merge, vas a tener que pasar un montón de diferentes tamaños.
Se puede, pero es molesto.
Pero recursividad para ordenar en sí es bastante fácil.
Simplemente llame especie literalmente en la mitad izquierda, más o menos en la mitad derecha. Bien.
¿Alguien tiene algo que pueda levantar ya?
O si no voy a dar un minuto.
Bien.
¿Alguien tiene algo que podamos trabajar?
De lo que sólo tendremos que trabajar con esto y luego expandirse desde allí.
>> Cualquier persona que tenga más de esto que yo puedo levantar?
[Estudiante] Yeah. Usted puede levantar la mía. >> Está bien.
¡Sí!
[Estudiante] Había un montón de condiciones. >> Oh, dispara. ¿Puede usted -
[Estudiante] Tengo que guardarlo. Sí >>.
Así lo hicimos hacer la fusión por separado.
Oh, pero no es tan malo.
Bien.
Así clase en sí es simplemente llamar mergeSortHelp.
Explícanos qué mergeSortHelp hace.
[Estudiante] MergeSortHelp prácticamente hace los dos pasos principales:
que es clasificar cada medio de la matriz y, a continuación para fusionar los dos.
[Bowden] Está bien, dame un segundo.
Creo que esto - >> [estudiante] Necesito -
Si. Me estoy perdiendo algo.
En combinación, me doy cuenta de que tengo que crear una nueva matriz
porque yo no podía hacerlo en su lugar. Sí >>. No se puede. Corregir.
[Estudiante] Por lo tanto, crear una nueva matriz.
Me olvidé al final de fusionarse para volver a cambiar.
Bien. Necesitamos una nueva matriz.
En tipo de mezcla, esto es casi siempre cierto.
Una parte del coste de un algoritmo mejor en cuanto a tiempo
es casi siempre la necesidad de usar la memoria un poco más.
Así que aquí, no importa lo que hagas merge sort,
que inevitablemente tendría que utilizar algo de memoria extra.
Él o ella creó una nueva matriz.
Y luego dicen que al final sólo tenemos que copiar nueva matriz en la matriz original.
[Estudiante] Creo que sí, sí.
No sé si eso funciona en términos de conteo por referencia o lo que sea -
Sí, va a trabajar. >> [Estudiante] Bueno.
¿Ha intentado ejecutar este? >> [Estudiante] No, todavía no. >> Okay.
Trate de ejecutarlo, y luego voy a hablar de eso por un segundo.
[Estudiante] Necesito tener todos los prototipos de funciones y todo, sin embargo, ¿no?
Los prototipos de función. Oh, te refieres a - sí.
Ordenar llama mergeSortHelp.
>> Así que para suerte de llamar mergeSortHelp, mergeSortHelp deberán haber sido definido
antes de ordenar o sólo tenemos el prototipo. Sólo tienes que copiar y pegar eso.
Y del mismo modo, mergeSortHelp llama fusión,
pero fusión no se ha definido todavía, así que podemos dejar saber mergeSortHelp
que eso es lo que va a fusionar verá así, y eso es todo.
Así mergeSortHelp.
Tenemos un problema aquí donde tenemos ningún caso base.
MergeSortHelp es recursivo, por lo que cualquier función recursiva
va a necesitar algún tipo de caso base para saber cuándo parar de forma recursiva se hace llamar.
¿Cuál es nuestro caso base va a estar aquí? Si.
[Estudiante] Si el tamaño es 1? >> [Bowden] Sí.
Así que, como vimos allí, nos detuvimos arrays división
una vez que llegamos en matrices de tamaño 1, lo que inevitablemente se están ordenadas.
Así que si el tamaño es igual a 1, sabemos que la serie ya está ordenado,
por lo que sólo puede volver.
>> Tenga en cuenta que es nula, por lo que no devuelve nada especial, simplemente volver.
Bien. Así que ese es nuestro caso base.
Supongo que nuestro caso base también podría ser si nos toca ser la fusión de una matriz de tamaño 0,
es probable que desee detener en algún momento,
por lo que sólo puede decir tamaño de menos de 2 o menos de o igual a 1
a fin de que esto funcionará para cualquier matriz ahora.
Bien.
Así que ese es nuestro caso base.
Ahora, ¿quieres que nos guiará a través de fusión?
¿Qué significan todos estos casos?
Hasta aquí, sólo estamos haciendo la misma idea, la -
[Estudiante] Necesito que me pasa tamaño con todas las llamadas mergeSortHelp.
He añadido un tamaño como principal adicional y no está ahí, como el tamaño / 2.
[Bowden] Oh, tamaño / 2, tamaño / 2. >> [Estudiante] Sí, y también en la función anterior también.
[Bowden] Aquí? >> [Estudiante] Just tamaño. >> [Bowden] Oh. Tamaño, el tamaño? >> [Estudiante] Yeah.
[Bowden] Bueno.
Déjame pensar por un segundo.
No nos encontramos con un problema?
Siempre estamos tratando la izquierda como 0. >> [Estudiante] No.
Eso está mal también. Lo siento. Debe ser inicio. Si.
[Bowden] Bueno. Me gusta más.
Y final. Bien.
Así que ahora quieres que nos guiará a través de fusión? >> [Estudiante] Bueno.
Estoy caminando a través de esta nueva matriz que he creado.
Su tamaño es el tamaño de la porción de la matriz que queremos ser ordenados
y tratando de encontrar el elemento que debo poner en la etapa de nueva matriz.
Así que para hacer eso, primero estoy comprobando si la mitad izquierda de la matriz sigue teniendo elementos más,
y si no es así, entonces hay que bajar a la condición de cosa, que sólo dice
bien, debe estar en la matriz derecha, y vamos a poner eso en el índice actual de newArray.
>> Y a continuación, de lo contrario, estoy comprobando si el lado derecho de la matriz también es terminado,
en cuyo caso sólo hay que poner en la izquierda.
Eso no podría ser en realidad necesario. No estoy seguro.
Pero de todos modos, los otros dos controles que los dos son más pequeñas en la izquierda o la derecha.
Y también en cada caso, estoy incrementando cualquiera que incrementar marcador de posición.
[Bowden] Bueno.
Eso se ve bien.
¿Alguien tiene algún comentario o inquietud o preguntas?
Así que los cuatro casos que tenemos que hacer las cosas en sólo ser - o parece que cinco -
pero debemos tener en cuenta si la matriz de la izquierda se ha quedado sin cosas que tenemos que unir,
si la matriz de la derecha se ha quedado sin cosas que tenemos que fusionar -
Estoy apuntando a nada.
Así que si la matriz de la izquierda se ha quedado sin cosas o la matriz de la derecha se ha quedado sin cosas.
Se trata de dos casos.
También tenemos el caso trivial de que la cosa izquierda es menor que lo correcto.
Entonces queremos elegir lo izquierdo.
Esos son los casos.
Así que esto estaba bien, así que eso es todo.
Matriz de la izquierda. Es 1, 2, 3. Bien. Así que sí, esas son las cuatro cosas que puede ser que desee hacer.
Y no vamos a ir a través de una solución iterativa.
Yo no recomendaría -
Unir tipo es un ejemplo de una función que es a la vez no cola recursiva,
no es fácil de hacer cola recursiva,
pero también no es muy fácil de hacer iterativo.
Esto es muy fácil.
Esta implementación del tipo de mezcla,
fusionar, no importa lo que hagas, vas a construir combinación.
>> Así fusionar tipo construido en la cima de fusión recursiva es sólo estas tres líneas.
Iterativamente, es más molesto y más difícil de pensar.
Pero nótese que no es recursivo cola desde mergeSortHelp - cuando se llama a sí misma -
que todavía tiene que hacer las cosas después de esta llamada recursiva.
Así que este marco de pila debe seguir existiendo incluso después de llamar a esto.
Y luego, cuando se llama a esto, el marco de pila debe seguir existiendo
porque incluso después de esa llamada, todavía tenemos que combinar.
Y es trivial para hacer esta cola recursiva.
¿Preguntas?
Está bien.
Así que volviendo a ordenar - oh, hay dos cosas que quiero mostrarte. Bien.
Volviendo a la clase, vamos a hacer esto rápidamente.
O buscar. Ordenar? Sort. Si.
Volviendo a los comienzos de la especie.
Queremos crear un algoritmo que ordena la matriz mediante cualquier algoritmo
en O de n.
Entonces, ¿cómo es esto posible? ¿Alguien tiene alguna especie de -
Me dio a entender antes de -
Si estamos a punto de mejorar a partir de n log n a O de n,
hemos mejorado nuestro algoritmo en cuanto a tiempo,
lo que significa que vamos a tener que hacer para compensar eso?
[Estudiante] Space. Sí >>. Vamos a estar usando más espacio.
Y ni siquiera sólo más espacio, es exponencialmente más espacio.
Así que creo que este tipo de algoritmo es algo pseudo polinomio pseudo -
pseudo - No puedo recordar. Pseudo algo.
Pero es porque tenemos que utilizar tanto espacio
que se puede lograr, pero no realista.
>> ¿Y cómo se consigue esto?
Podemos lograr esto si te garantizamos que cualquier elemento particular de la matriz
está por debajo de un cierto tamaño.
Así que vamos a decir que el tamaño es de 200,
cualquier elemento de una matriz se encuentra por debajo del tamaño 200.
Y esto es realmente muy realista.
Usted puede fácilmente tener una matriz que ya sabes todo lo que contiene
va a ser menor que cierto número.
Al igual que si usted tiene algún vector absolutamente masivo o algo
pero ya sabes que todo va a estar entre 0 y 5,
entonces va a ser mucho más rápida de hacer esto.
Y la envolvente en cualquiera de los elementos es 5,
por lo que este límite, que es la cantidad de memoria que va a utilizar.
Así que el límite es 200.
En teoría no siempre es un salto desde un número entero sólo puede ser de hasta 4 millones de dólares,
pero eso es poco realista ya que entonces estaríamos utilizando el espacio
del orden de 4 mil millones. Así que eso es poco realista.
Pero aquí vamos a decir que nuestro límite es de 200.
El truco para hacerlo en O de n es que hagamos otra matriz denominada cargos de tamaño OBLIGADO.
Así que en realidad, se trata de un acceso directo - Yo en realidad no sé si Clang hace esto.
Pero en GCC como mínimo - Clang estoy suponiendo que también lo hace -
esto sólo inicializar la matriz completa para ser 0.
Así que si no quieres hacer eso, entonces yo podría hacer por separado for (int i = 0;
i <BOUND, i + +) y cuenta con [i] = 0;
Así que ahora todo se inicializa a 0.
Yo iterar sobre mi matriz,
y lo que estoy haciendo es que estoy contando el número de cada uno - Bajemos aquí.
Tenemos 4, 15, 16, 50, 8, 23, 42, 108.
Lo que estoy contando es el número de ocurrencias de cada uno de esos elementos.
Vamos a añadir un par realmente más aquí con algunas repeticiones.
Por lo tanto el valor que tenemos aquí, el valor de que va a ser matriz [i].
Así val podría ser 4 o 8 o lo que sea.
Y ahora que estoy contando cuántos de ese valor que he visto,
así recuentos [val] + +;
Una vez hecho esto, el recuento se va a ver algo como 0001.
Vamos a hacer recuento de [valor] - SUJETO + 1.
>> Ahora eso es sólo para explicar el hecho de que estamos empezando desde 0.
Así que si 200 va a ser nuestra mayor número,
entonces 0 a 200 es de 201 cosas.
Así que cuenta, se verá como 00001, porque tenemos un 4.
Entonces tendremos 0001 donde tendremos un 1 en el índice de 8 de conteo.
Vamos a tener un 2 en el índice 23 de la cuenta.
Vamos a tener un 2 en el índice 42 del conteo.
Así que podemos usar la cuenta.
Así num_of_item = cuenta [i].
Y si es así num_of_item es 2, significa que desea insertar 2 de la serie i
en nuestra matriz ordenada.
Así que tenemos que hacer un seguimiento de lo lejos que estamos en la matriz.
So = índice 0.
Array - Voy a escribirlo.
Cuentas -
array [índice + +] = i;
¿Es eso lo que quieres? Creo que eso es lo que quiero.
Sí, esto se ve bien. Bien.
Entonces, ¿todo el mundo entiende lo que el propósito de mi cuenta es la matriz?
Se cuenta el número de ocurrencias de cada uno de estos números.
Entonces estoy iterar sobre esa matriz cuenta,
y la posición i-ésima de la matriz de los recuentos
es el número de i es que debería aparecer en mi matriz ordenada.
Es por eso que los recuentos de 4 va a ser un
y los recuentos de 8 va a ser 1, los recuentos de 23 va a ser 2.
Así es como muchos de los que desea insertar en mi matriz ordenada.
Entonces me acaba de hacer eso.
Estoy insertando num_of_item íes en mi matriz ordenada.
>> ¿Preguntas?
Y así, una vez más, este es el tiempo lineal, ya que estamos sólo iterar sobre esto una vez,
pero también es lineal en lo que este número pasa a ser,
por lo que en gran medida depende de lo que su límite es.
De un salto de 200, que no es tan malo.
Si el límite va a ser 10.000, entonces eso es un poco peor,
pero si su límite va a ser de 4 millones de dólares, que es completamente irreal
y este arreglo se va a tener que ser de tamaño 4 mil millones, lo cual es poco realista.
Así que eso es todo. ¿Preguntas?
[Respuesta de los estudiantes inaudible] >> Okay.
Me di cuenta de otra cosa cuando estábamos pasando.
Creo que el problema estaba en Lucas, y probablemente cada uno que hemos visto.
Me olvidé por completo.
Lo único que quería comentar es que cuando usted está tratando con cosas como índices,
usted nunca realmente ver esto cuando usted está escribiendo un bucle for,
pero técnicamente, cuando usted está tratando con estos índices,
usted debe casi siempre tratan con números enteros sin signo.
La razón de esto es cuando usted está tratando con enteros con signo,
así que si usted tiene 2 enteros con signo y sumarlos
y acaban demasiado grande, entonces usted termina con un número negativo.
Así que eso es lo que es de desbordamiento de enteros.
>> Si añado 2 mil millones y 1 mil millones, termino con negativo 1 mil millones.
Así es como funciona en equipos enteros.
Así que el problema con el uso -
Eso está bien, excepto si baja pasa a ser de hasta 2 mil millones y pasa a ser de 1 mil millones,
entonces esto va a ser negativo 1 mil millones y luego vamos a dividir eso por 2
y terminar con negativo 500 millones.
Así que esto es sólo un problema si le sucede que se busca a través de una matriz
de miles de millones de cosas.
Pero si baja + hasta que ocurre el desbordamiento, entonces eso es un problema.
Tan pronto como los hacemos sin firmar, a continuación, 2 millones más mil millones es de 3 millones de dólares.
3 mil millones dividido por 2 es de 1,5 millones de dólares.
Así que tan pronto como estén sin firmar, todo es perfecto.
Y eso es también un problema cuando usted está escribiendo su bucles for,
y, de hecho, es probable que lo haga de forma automática.
En realidad, se acaba de gritar a ti.
Así que si este número es demasiado grande para ser justo en un entero pero cabría en un entero sin signo,
va a gritar a ti, así que por eso nunca te llegas a tener el problema.
Se puede ver que el índice nunca va a ser negativo,
así que cuando usted está interactuando sobre una matriz,
casi siempre se puede decir unsigned int i, pero que en realidad no tiene que hacerlo.
Las cosas van a funcionar más o menos igual de bien.
Bien. [Susurra] ¿Qué hora es?
Lo último que quería mostrar - y yo sólo voy a hacerlo muy rápido.
¿Sabes cómo hemos # define por lo que puede definir # MAX como 5 o algo así?
No hagamos MAX. # Define OBLIGADO 200. Eso es lo que hicimos antes.
Eso define una constante, que sólo va a ser copiado y pegado
donde nos ha tocado escribir OBLIGADO.
>> Así que en realidad puede hacer más con # define.
Hemos # puede definir funciones.
No son realmente funciones, pero llamaremos funciones.
Un ejemplo podría ser algo como MAX (x, y) se define como (x <y y:? X). Bien.
Por lo que debe acostumbrarse a la sintaxis del operador ternario,
pero es x menor que y? Vuelva a, o regrese x.
Así se puede ver que puede hacer esta función, por separado,
y la función podría ser como bool MAX tiene 2 argumentos, devuelva este.
Esta es una de las más comunes que veo hecho así. Los llamamos macros.
Esta es una macro.
Esto es sólo la sintaxis para ello.
Usted puede escribir una macro para hacer lo que quieras.
Se ven con frecuencia para depurar macros printfs y esas cosas.
Así que un tipo de printf, hay constantes especiales en C como subrayan LÍNEA subrayado,
2 subraya LÍNEA subrayado,
y también hay que pensar dos guiones FUNC. Eso podría ser. Algo por el estilo.
Esas cosas se reemplazará con el nombre de la función
o el número de la línea que te encuentres.
Con frecuencia, se escribe printfs depuración que aquí me podría simplemente escribir
DEBUG y se imprimirá el número de línea y la función que me toca estar en
que encontró que la declaración DEBUG.
Y también se puede imprimir otras cosas.
Así que una cosa que debes tener en cuenta es si se me ocurre para definir # DOUBLE_MAX
algo así como 2 * y 2 * y x.
Así que por razón alguna, le toca hacer mucho de eso.
Así que lo convierten en un macro.
Esto es realmente roto.
Yo diría que es por hacer algo como DOUBLE_MAX (3, 6).
Entonces, ¿cuál debe ser devuelto?
[Estudiante] 12.
Sí, 12 deben ser devueltos, y 12 se devuelve.
3 es reemplazado por x, 6 es reemplazado por y, y volvemos 2 * 6, que tiene 12 años.
Ahora, ¿qué pasa con esto? ¿Cuál debe ser devuelto?
[Estudiante] 14. >> Idealmente, 14.
La cuestión es que la forma de hash define el trabajo, recuerde que es una copia literal y pegar
de casi todo, así que lo que esto va a ser interpretada como
es 3 menos que 1 más 6, 2 veces 1 más 6, 2 veces 3.
>> Así, por esta razón por la que casi siempre envuelven todo entre paréntesis.
Cualquier variable que casi siempre envuelven en paréntesis.
Hay casos en los que no tienen que, como yo sé que no es necesario hacerlo aquí
porque menos es casi siempre sólo se va a trabajar,
a pesar de que ni siquiera podría ser cierto.
Si hay algo ridículo como DOUBLE_MAX (1 == 2),
entonces eso va a quedar sustituido por 3 menos 1 es igual a igual a 2,
y por lo que también va a hacer 3 menos que 1, es igual que 2,
que no es lo que queremos.
Así que para evitar cualquier problema de prioridad de operador,
envuelva siempre entre paréntesis.
Bien. Y eso es todo, 5:30.
Si usted tiene alguna pregunta sobre el conjunto de procesadores, háganoslo saber.
Debe ser divertido, y la edición pirata informático también es mucho más realista
que la edición pirata de la del año pasado, así que esperamos que muchos de ustedes lo intente.
El año pasado fue muy abrumador.
>> [CS50.TV]