Timing de informática y notación de Big O

1. Video de introducción: Hola a todos, y bienvenidos a este curso de notación Big O. Este es un gran tema de informática que te ayudará a ser más eficiente en tu trabajo. Y también te ayudará a entender un poco mejor la informática. Esto es ideal para todo tipo de profesiones, incluidos los programadores, así como para cualquier persona en el ámbito empresarial Te ayudará a aumentar tu productividad, ya que entenderás con lo que estás trabajando un poco más, que te dará más información y acción los pasos que podrías necesitar tomar para hacer las cosas más eficientes. Y eso es lo que vamos a estar cubriendo en este curso. Vamos a estar cubriendo la notación detrás de cómo analizamos diferentes algoritmos y escalabilidad Queremos entender si estamos construyendo un programa o una pieza de código o incluso solo una unidad organizativa. ¿Se puede escalar? Si estamos creando tareas y procedimientos que son de naturaleza exponencial, entonces nunca podrán escalar Y eso es lo que queremos poder analizar es ¿ funciona igual si tenemos diez personas o 100 mil personas? Piense si quiere revisar cada archivo en un archivador. Hay una manera en la que puedes sacar cada archivo y mirarlo individualmente, o puedes crear un procedimiento donde esté organizado y ordenado para que sepas a dónde ir para encontrar cosas. Y eso es lo que puedes hacer también en el espacio de programación, pero también con las cosas que nos rodean. Otro ejemplo sería si necesitábamos agregar a alguien a una organización, pero para ello, primero teníamos que contactar a todos los demás miembros de la organización. Esa es una solución inescalable. Es un procedimiento inescalable. Y queremos poder analizar esa reelaboración y convertirlo en un procedimiento más escalable Entonces vamos a estar ambos enfocándonos en el código en esto, pero entendemos que estos principios también se aplican en la vida diaria. Se aplican en las cosas que nos rodean. Así que vamos a saltar a este tema de la informática y echar un vistazo a algunas matemáticas realmente interesantes. 2. Introducción de Big O: Hablemos de nuestro primer tema importante en el análisis de algoritmos, y esa va a ser esta idea de en notación. Entonces, en lo que realmente vamos a estar evolucionando esto es algo llamado notación Big O, que va a verse algo así donde tienes una O, y luego la notación in entra dentro de ella. Pero antes de que podamos hacer eso, necesitamos averiguar qué es exactamente en notación. Entonces en notación está este extraño tipo de relación, donde es una función de in. Ahora, quédate conmigo. Esto es confuso al principio. Así que vamos a tener que desempacar esto un poco Es este tipo de manera donde salida es una función de la entrada, y simplemente pasaron a ser lo mismo. Así que vamos a seguir adelante y crear una especie de modelo visual de esto. Siempre que creamos un algoritmo o un programa, lo que estamos haciendo es crear este tipo de caja negra. Entonces lo que tenemos es que tenemos encima del lado izquierdo es entrada. Tenemos cosas entrando en la caja. Tenemos tal vez sean tus amigos de Facebook, lo mejor es tu Google Drive, todos los datos que le estás enviando. Es Internet. Cuando estás subiendo algo, esa es la entrada Se envía a algún tipo de lógica, algún tipo de programa. Entonces esta es, ya sabes, la lógica o la tasa del controlador aquí. Y entonces tiene algún tipo de salida. Algo pasa porque aquí mismo se ha ido a esta lógica. ¿Algo ha pasado? Algo se ha movido, algo se ha salvado. Eso es realmente lo que está haciendo la lógica. Entonces, por ejemplo, digamos que estamos subiendo fotos. La entrada son las imágenes. Se lo enviamos al controlador. Toma las fotos, lo mejor las escala hacia abajo para que sean más fáciles de almacenar. Entonces toma esas fotos y las guarda en una base de datos. Entonces los pone y los escribe en la memoria física en un disco duro. Y así esa es la salida. Entonces la entrada, las imágenes, la salida son cada una de esas operaciones de guardado en un disco duro. Y entonces lo que estamos tratando de averiguar se le da la entrada en. Entonces esta es la entrada de in. Cuál va a ser nuestra salida. En relación con esto. Un derecho aquí es solo una variable. Es solo porque no sabemos cuántos datos están entrando. Si por ejemplo, tuviéramos un programa que hiciera amigos de Facebook, podría tener tal vez, ya sabes, tal vez tengo 182 amigos de Facebook. Bueno, a lo mejor tienes 1,373, y tu primo lejano tiene 10,157 amigos de Facebook, ya sabes, y así sucesivamente y así sucesivamente Y digamos que no hay límite. Creo que hay un límite. Pero digamos que no hay límite en los amigos de Facebook. Entonces eso significa que podrías tener cero hasta el infinito. Entonces no sabemos qué número va a entrar aquí. Entonces, en lugar de intentar simplemente hacer un número, solo decimos, que solo va a ser el valor del marcador Entonces vamos a poner una entrada de aquí. Puede ser cualquiera de estos números de cero a infinito. Entonces cualquier número. Y entonces va a pasar por nuestra lógica. Y luego al final, vamos a tener cierto número de operaciones. Entonces, entre esta tasa de puntos aquí, vamos a tener lógica y luego operaciones, y luego va a dar salida. Y queremos saber qué está pasando durante este punto. ¿Cómo se relaciona esto con esto? Entonces esto de aquí va a ser la salida o nuestra función. Esta va a ser la notación. Y lo que normalmente escribimos es que en realidad lo escribimos como un in también. Pero lo escribimos en función de, es decir, eso no es lo único que ponemos aquí. De hecho, hay un montón de cosas diferentes que podríamos poner aquí. Entonces, lo que podríamos tener está adentro, y eso solo significa que cada vez que colocamos, digamos, 1,000 datos, solo se necesitan mil operaciones. Por ejemplo, algo como esto es si encuentras un montón de archivos en tu disco duro y quieres moverlos a otra ubicación? Bueno, no hay nada más que realmente tenga que pasar. Tomamos uno, lo movemos por encima. Tomamos uno, lo movemos por encima. Eso está adentro. Por cada dato que incluyas, solo hay una operación más. Ahora, hay cosas diferentes, claro. Entonces, en vez de, podría haber ahí está al cuadrado. Hay algo llamado registro de. Sólo hay tronco de n. Hay cubos. Ahí está la raíz cuadrada de. Y así sucesivamente y así sucesivamente. Así que todo lo que estamos haciendo es que estamos tomando todos estos, y los estamos haciendo una función de la entrada. Esto siempre va a permanecer igual. Esto siempre va a estar dentro. Yo es nuestro insumo. Es la cantidad de datos que están entrando. la derecha está solo la relación, y solo usamos porque nos muestra que de esto es de lo que estamos haciendo una función. Quiero decir, podríamos usar x y la x al cuadrado y luego x log de x y cosas así, y así sucesivamente y así sucesivamente y así sucesivamente Pero el problema es que podrías confundirte como, ya sabes, qué es exactamente x. Y entonces tenemos que poner algo aquí arriba que solo diga: Bueno, x es igual a n, x igual o input. Y entonces sólo estamos pensando, ¿por qué no nos quedamos con N para hacer todo esto? Entonces esa es realmente la mayor parte confusa de la notación es que N parece puede ser la entrada y la salida. Pero lo importante es que es la entrada, y entonces la salida es solo una función de N. Es una representación de cuánto tiempo o cuántas operaciones N debe usar para superarse. A las salidas. Ahora veamos un poco de ejemplo concreto. Volvamos a ese amigo de Facebook porque eso es algo que todos podemos visualizar muy rápidamente. Digamos que tengo un algoritmo aquí mismo. Tengo un algoritmo que toma una cantidad de amigos de Facebook, y los introduce en una base de datos al momento de o la relación de. Y digamos que tengo otro algoritmo aquí mismo. Que hace exactamente lo mismo. Excepto en cambio toma lo mismo de in, entonces toma adentro, pero sale adentro en cuadrado Aquí hay un poco menos de eficiencia. Así que ahora podemos mirar a estos dos y simplemente compararlos un poco. ¿Cuál de estos algoritmos es más rápido? Entonces, si seguimos adelante y acabamos de hacer algunas matemáticas rápidas, digamos que vamos a probar esto con 100 Facebook francia. Entonces en esta primera, bueno, solo va a ser 100 entra en nuestra cajita negra, y sale con 100 operaciones diferentes para hacer lo que sea que haga. Bueno, en el de abajo aquí, tenemos 100 entra en nuestra cajita negra. Recuerda que siempre va a quedar igual, pero nuestra función es n al cuadrado, lo que significa que ahora necesitamos tomar lo que significa que ahora necesitamos tomar en realidad 100 y cuadrarlo, lo que solo resulta ser 100 veces 100, lo que significa que nuestro total va a ser Ups tengo que conseguir los ceros aquí Cuatro ceros o 10,000. Por lo que se puede ver que la primera sólo tomó 100 operaciones, mientras que la segunda tomó 10 mil operaciones. Vamos a meternos en esto un poco más tarde. Sin embargo, los patrones de crecimiento de estos son lo que es importante. Dentro de lo que tenemos es que en realidad tenemos algo llamado lineal, y luego con en cuadrado, tenemos algo que se llama exponencial, lo que significa que el crecimiento va subiendo cada vez más y más con el tiempo Pero como dije, nos meteremos en eso más tarde. Lo que solo quería mostrarte es cómo nos fijamos en esto. Entonces tenemos un valor de entrada y tenemos un valor de salida. Tenemos otro valor de entrada y otro valor de salida, y hay dos algoritmos diferentes, algoritmo A y el algoritmo B. Y podemos decir rápidamente, Bueno, A es definitivamente más rápido que B. A es se podría decir que es mayor que B, o se podría decir que usa menos tiempo que B o como quiera compararlos. Pero esta es rápida y esta lenta por la cantidad de operaciones que realizan. Entonces, ¿cuál es el punto? ¿A qué estamos tratando de llegar aquí? Yo nos permite ver cómo escala un algoritmo con el tamaño de entrada. Si diseñamos un algoritmo, queremos saber, es eficiente con más gente y entrada? Queremos que nuestros programas tengan éxito. Entonces queremos hacer soluciones que escalen. Y esto es algo que escucharás mucho. Queremos hacer soluciones escalables. Y una solución escalable es una solución que no solo funciona para la cantidad exacta de personas que la están usando actualmente en este momento. Entonces, por ejemplo, como dije, vamos a seguir adelante en este ejemplo de Facebook. Imagínese si Facebook usara éste. Imagínese si usara el algoritmo cuadrado porque no pensara que iban a escalar Bueno, la cosa es que somos programadores. Estamos tratando de hacer de nuestro producto el mejor producto que puede ser. Y eso significa que queremos que el producto tenga éxito. Y cuando un producto tiene éxito, más gente lo usa, se ingresan más datos, y el algoritmo tendrá que usar estas nuevas piezas Si no hacemos un programa que sea escalable, nos encontraremos con todo el problema exponencial, donde sí, esto funcionará para 100 y tal vez funcione para 1,000 y bueno, tal vez funcione para 10,000 Pero si te das cuenta esa es una parte muy pequeña de la población. Digamos que tal vez 1 millón de personas. Quiere utilizar nuestro programa. Bueno, ahora, tenemos una solución que no funciona para 1 millón de personas. Si lo hiciéramos 1 millón de veces 1 millón. Bueno, tendríamos un número que es sumamente grande. Un número que ni siquiera es comprendido por nuestros cerebros. Y esto en realidad, vamos a hacer algunas de estas matemáticas un poco más adelante. Un número tan grande termina tardando días o incluso años en ejecutarse. Entonces una computadora, la computadora que pueda, ya sabes, iniciar sesión en línea y hacer todas estas matemáticas rápidas tardará días o años en lograr una tarea sencilla, y eso es porque el programa no es escalable. Entonces esa es la base de la notación. Es estandarizado, forma de notación que nos permite comparar dos algoritmos en un ambiente completamente estéril, lo que significa que no tenemos que implementarlos. Sólo podemos mirarlos. Nos permite compararlos y averiguar cuál es más escalable. Cuál será más rápido cada vez que le agreguemos más personas o más datos o más operaciones. Y ese es el punto de la notación. Y la siguiente conferencia, vamos a seguir sumergiéndonos en esto y vamos a seguir desempacando la caja que es notación para que podamos obtener esta base sólida para poder comparar diferentes algoritmos 3. Notación N: Profundicemos un poco más en la Profundicemos notación final y veamos algunos de los objetivos detrás de por qué nosotros, como informáticos, usamos la notación final y lo que estamos tratando de obtener de ella. Porque la notación final se puede usar de muchas maneras diferentes. Hay un montón de diferentes tipos de combinaciones o piezas de información que podemos obtener de ella usando esta notación. Pero lo que quiero repasar es el núcleo, lo que la mayoría de los informáticos lo utilizan. ¿Y cuáles son algunos de los objetivos? ¿Por qué lo usamos? Entonces, cuando usamos la notación, lo que estamos haciendo es que estamos buscando patrones grandes, y estamos buscando estos patrones en una especie de espacio teórico, lo que significa que en realidad no vamos a tener un programa implementado ni nada por el estilo. Solo estamos buscando esos patrones grandes. Estamos buscando, por ejemplo, si una gráfica va así y la otra va así. No nos importa si en algún momento tenemos esa gráfica en la parte inferior, lo mejor va así , y entonces esta de arriba va así o algo así? No nos importa en este punto que sí, ahí está este punto justo aquí donde cuadré es en realidad sólo un poco más eficiente Eso es para meollo arenoso cuando en realidad tienes un algoritmo frente a ti y estás tratando de optimizarlo Eso es lo que tal vez podría hacer un optimizador de servidores o administración de bases de datos, cosas así Simplemente nos importa eso la teoría en general. Estamos buscando qué ecuación empeora con el tiempo. Entonces, a medida que avanzamos hacia el infinito, a medida que avanzamos hacia la cantidad desconocida de número de piezas de datos que podrían llegar al algoritmo interior, ¿qué va a pasar con nuestra ecuación? Vamos a conseguir esa ecuación que no se puede terminar en este siglo por cuántos cálculos va a tomar, o vamos a conseguir algo como esto, donde no importa cuántos cálculos le demos. Es sólo que va a seguir dando vueltas . Y así es lo que queremos ver. Queremos ver ese cambio importante de eficiencia entre diferentes algoritmos. Ese es el punto de notación y por qué usamos la notación. Entonces con esto debido a esto, hay un par de reglas que solemos usar con notación. Y son sólo una especie de shorthands que usamos para no confundirnos Y otra vez, para llegar a ese panorama general. Así que no pasamos todo nuestro tiempo en el meollo arenoso. De hecho, podemos simplemente mirar dos ecuaciones y ser como , si, esta escala un poco mejor. El primero es que no nos importan los múltiplos. Y lo que eso significa es, por ejemplo, Si tenemos n al cuadrado y luego tres n al cuadrado Estos son, a todos los efectos, iguales. Básicamente son iguales entre sí. No nos importa. Quiero decir, tres, ya sabes, tal vez podrías justificarte a ti mismo. Sí, tres está bien, pero esto podría ser, ya sabes, esto podría ser como 3 millones 3 mil millones, 30 billones, 30 billones Puede ser cualquier número que queramos, y no importa. Tomamos ese múltiplo y lo borramos. No nos importan los múltiplos. Y esto solo se reduce a, de nuevo, lo grande y general, no importa cuán grande sea este número en algún momento entre cero e infinito En algún momento, n al cuadrado va a hacer que este número ni siquiera sea efectivo Imagínese si en algún momento fuera igual a, no lo sé. 300 Google, y Google es 100 ceros al final. Entonces tienes 100 ceros al final de esto. ¿Crees que los 3 millones que se están multiplicando realmente importan en ese momento? Quiero decir, va a ser muy, muy pequeña diferencia en el resultado final. Estamos hablando como Ya sabes, va a ser una diferencia de un número que se ve así o entre un número que tiene esto en él. Ya sabes, un poco más sobre él. No importa en absoluto. Entonces es por eso que en teoría, cada vez que vamos de cero a infinito, no nos importan los múltiplos. Entonces, para comparar dos algoritmos, podría ser de 3 millones al cuadrado, y lo estamos comparando como no el cúbico, no importa Todavía estamos comparando n al cuadrado con n en cubos. Así que siempre eliminas los múltiplos al principio. Ahora bien, ¿cómo conseguimos estos múltiplos? Bueno, digamos que tenemos una ecuación que hace esto. Tenemos la caja negra, así que tenemos los insumos que vienen por aquí. Tenemos una operación al cuadrado. Al siguiente traemos todos esos insumos a otra caja negra, otra operación cuadrada Bien. Y digamos que al final aquí, tenemos otra, pero ésta es sólo una operación in log in. Entonces con un algoritmo como este, en realidad creamos un poco de una ecuación aquí. Hacemos algo como esto. Vamos al cuadrado más al cuadrado más iniciar sesión. Y entonces en realidad podemos combinar estos en un múltiplo. Entonces esto es dos n al cuadrado más iniciar sesión. Y así es como se nos ocurre un múltiplo, y ya sabes lo que hemos estado diciendo aquí es que realmente no nos importa el múltiplo. Puedo hacer esto tantas veces que queramos. Solo estamos viendo ese gran factor de cambio. Entonces esto se vuelve cuadrado más iniciar sesión. Entonces, esto llega a nuestra segunda regla. Tomamos la ecuación más grande. Entonces siempre que tengamos una ecuación como esta, nuevo, esto no va a escalar casi tan rápido como esta. Cuando nos metemos en esos números gigantes con 50 cero, mil millones de ceros al final, quiero decir, son dos y terminan, así que en algún momento puede haber mil millones de ceros Podría haber mil millones de ceros al final de esto, no el número mil millones Estoy hablando de mil millones de cero real. Sería un número tan largo que, ya sabes, no podrías encajarlo alrededor de toda la Tierra. Podría haber un número así. Quiero decir, aquí vamos al infinito. Entonces, en algún momento, esto va a llegar a ser tan salvajemente mayor que este número que no nos importa Esto es solo un pequeño bache en el camino hacia lo que sea que esté siendo este número. Sólo va a afectarlo tal vez un 0.00, 000 1% en algún momento. Es en algún momento, afectado por casi nada. Va a ser un número tan pequeño. Es casi cero. Y por eso, también lo eliminamos del final, y simplemente dejamos una ecuación como esta para decir, Oye, todo este algoritmo de aquí, todo este algoritmo de aquí mismo es en realidad es en realidad solo al cuadrado Y entonces hay un par de reglas de escalado. Ahora bien, si quieres ir técnico, si estamos haciendo optimización de servidor o alguna de esas otras cosas donde realmente tenemos ecuación frente a nosotros, sí, esto es probablemente algo que ecuación frente a nosotros, sí, queremos ver porque si estamos viendo un servidor real y tenemos una ecuación que puede ejecutarlo en y tenemos una ecuación que puede ejecutarlo n cuadrado más iniciar sesión, en lugar de dos al cuadrado más iniciar sesión, en lugar de dos al cuadrado más n iniciar sesión queremos hacer esto porque va a ser más rápido en la práctica real. Pero nuevamente, esto no es práctica. Esto es teoría. Estamos tratando de averiguar solo las diferencias de las aplicaciones a gran escala. Y así en ese sentido, hacemos ambas reglas, las desglosamos en justo lo que es el gran tiempo de ejecución de esto. Y en realidad tenemos pequeños modificadores de O grande y poco O y Beta También vamos a hablar de esos en poco tiempo que harán que esto sea un poco más fácil de entender. Entonces echemos un vistazo a algunos gráficos aquí. Echemos un vistazo a, ya sabes, algo de lo que he estado detallando aquí con todo el asunto de los números, van a superar a sus socios, y así solo nos importan realmente los grandes números Entonces, aquí mismo, tenemos una especie de representación de una gráfica aquí. Tenemos todas las cosas de las que hemos estado hablando. Este es uno, que es tiempo constante. Significa que podríamos poner mil, podríamos poner mil millones, podríamos poner en cualquier número de lo que queramos, y solo tomará alguna vez un número constante de operaciones. Así que sólo tomará tal vez tres. A lo mejor son 62 operaciones diferentes. No importa el número que pongamos, se necesitan 62 operaciones. Entonces eso es lo que es el tiempo constante. Y luego conseguimos ese registro a tiempo, y se puede ver que tiene ese tipo de gráfica que va así. Entonces tenemos apenas la raíz cuadrada de N, que es similar a iniciar sesión, pero va subiendo con el tiempo. Tenemos lineales o. Linar es solo línea recta en ángulo. En log in algo así se ve un poco así, pero luego entra en una línea lineal, tal vez con ligeras tendencias hacia arriba Entonces nos pusimos al cuadrado, lo cual es exponencial. Entonces conseguimos dos n factoriales, que es aún más exponencial y casi apenas va directo hacia arriba en el aire Y luego nos metimos en factorial, que bien podría verse así Va casi hacia arriba en el aire y crea números tan grandes que si alguno de tus programas alguna vez se ejecuta en factorial, está mal Se tiene que hacer de una mejor manera. Sin embargo, echemos un vistazo a los ejemplos de lo que todos estos serían si les agregáramos números, cuáles podrían ser los tiempos de ejecución. Entonces en esta situación, estamos diciendo que podemos ver aquí, es el número de insumos, y en capital en aquí mismo va a ser el número de operaciones. Entonces por aquí, estos son los pequeños ins. Esto es lo que estamos ingresando. Estamos ingresando los 100,000 o 10,000 o 1110 o uno. Y esto es lo que la salida es el tiempo que tardaría en correr. Y te das cuenta en la primera fila, realidad es algo interesante es que con solo una pieza, no importa lo que tengas, siempre va a ejecutarlo básicamente al mismo tiempo. Por supuesto, puede haber algunas diferencias, por ejemplo, tal vez tiempo constante. lo mejor esta es una vez en la que si los tiempos constantes 62, todos estos en realidad correrían un poco más rápido. Pero de nuevo, eso está en el meollo arenoso y eso no nos importa realmente Queremos ver estas tendencias a medida que van a lo largo del tiempo. Entonces, si vamos a factorial, el E plus al final aquí, eso significa que así es cuántos ceros hay al final del mismo Entonces eso significa que esto es 9.3 o nueve tres con 157 o 156 ceros si mueves el decimal En fin, hay muchos ceros al final de esa. Y éste es, ya sabes, son cuatro con 2567350000, 456,000 ceros Y puedes notar lo grande que esto cambia con el tiempo. Y luego tenemos dos aquí. Esto es dos y luego dos algunos factoriales. Entonces, ya sabes, en esta situación, son dos décimas o dos a 100 y así sucesivamente y así sucesivamente y así sucesivamente. Pero de todos modos, se puede notar que incluso estos dos. Estos dos son básicamente rectos en el aire. Hay una gran diferencia. Es la diferencia 400-56 mil ceros y 300 o 30 mil Y luego nos movemos cada vez más y más. Y lo que tenemos es que tenemos abajo a n al cuadrado, lo que hemos estado hablando, hemos estado mostrando lo ineficiente que es Y esto en realidad se ve muy pequeño en comparación con dos al factorial n y n cuando se supera cada vez más. Entonces tenemos N log in. En realidad estamos llegando a números legibles aquí, solo 1,660,000, luego solo n que, por supuesto, va a ser equivalente a cuántos metemos porque N siempre irá solo a N. Eso es lo que representa ahí mismo Y luego empezamos a meternos en estos aquí abajo donde te das cuenta de que estos en realidad son algo geniales. Aquí son algoritmos eficientes. Tenemos ponemos 100 mil y solo hacemos 316 operaciones. Hay un cambio cada vez más pequeño medida que avanzamos con el tiempo. Y esto, se puede notar cómo podríamos obtener algún tipo de algoritmos para ser realmente bastante eficientes. Quiero decir, mira esto. Entonces tenemos la diferencia entre 90 aquí mismo. Y en esa diferencia, subimos por tres operaciones. Ahora, tenemos la diferencia de 900 aquí mismo. ¿Y cuánto subimos? Bueno, sólo por unas tres operaciones. Entonces tenemos la diferencia de 9 mil nuevos datos. ¿Cuánto subimos? Bueno, alrededor de tres operaciones. Y luego subimos por 90 mil es el siguiente paso. Y ¿cuánto tenemos? Bueno, sólo tres operaciones. Es exactamente lo contrario. Cuanto más le sumamos, menos sube. Aumenta cada vez menos con el tiempo. Y en realidad hay algoritmos de los que vamos a hablar a lo largo de este curso que corren así. Utiliza algo llamado como dividir y conquistar donde realmente nos separamos. La información como esta, y de esa manera solo podemos acceder a ella realmente, muy rápido en lugar de tener que pasar por cada pieza para llegar a lo que queremos. Pero de todos modos, eso es solo una especie de resumen de la notación, cómo se escala, y luego algunos de los términos que usamos con notación y escalado En la siguiente conferencia vamos a repasar un ejemplo del mundo real, tal vez agregar un poco de sacar un poco del lado de la teoría y una especie de mirar las diferencias de estos si realmente aplicamos, ya sabes, 0.01 segundos a cada operación. Podemos ver cuán masivos se vuelven estos números y las diferencias entre ellos. 4. Ejemplo de notación N: Vamos a poner algunos números a lo que hemos estado hablando para algo así solo poner esto en un poco de respeto que todos puedan entender. Así que vamos a repasar este problema aquí mismo y echemos un vistazo a las diferencias de cómo se puede ver el inicio de sesión y el cuadrado En la última conferencia, miramos este tipo de esta tasa gráfica aquí. Y entonces lo que estamos viendo es esta tasa aquí, en log in y al cuadrado Y en este tipo de pequeña tasa gráfica aquí, quiero decir, se ven muy cerca el uno del otro, ¿verdad? Parecen que no habría tanta diferencia entre ellos. Y esto es lo que quiero mostrar es que hay grandes diferencias incluso entre estas de aquí arriba, y el cambio de eficiencia es muy importante. Entonces, echemos un vistazo a este ejemplo. Simplemente lo repasará, y ojalá te muestre las diferencias. Entonces tenemos o decimos que cada ciclo de un programa toma aproximadamente 0.001 segundos, lo que creo que es un milisegundo Y entonces lo que estamos diciendo es cuánto más rápido se iniciará sesión tomar que en cuadrado, si se ingresan mil piezas de datos y luego más abajo aquí, si se ingresan 25 mil piezas de datos Y así con esto, lo que vamos a hacer es que sólo vamos a enchufar esto. Vamos a calcular cuántas operaciones lleva, multiplicarlo por milisegundos, y luego vamos a obtener cuánto tiempo tardaría un programa que se ejecutaría así Y así, nuestro primer ejemplo, tenemos eso en log in. Multiplicamos 1,000 por log de 1,000, y estamos usando log basado en dos, recuerda. Entonces estos son todos basados en registros dos. Y entonces lo que obtenemos es que obtenemos 9,960 veces milisegundos, y eso todo sale a 9.96 Entonces, si vamos con el cuadrado, vamos a hacer mil al cuadrado Eso va a ser mil por mil, lo que termina consiguiendo aquí el número 1 millón. Y con 1 millón, multiplicar los milisegundos, y obtenemos 1,000 segundos o 16 minutos. Entonces la diferencia entre usar estos dos algoritmos es que uno tardará 9.96 segundos. Entonces, ya sabes, 10 segundos. No es tanto tiempo en absoluto, y el otro tardará 16 minutos en lograrlo. Imagina que si estás en línea y envías un formulario, y uno de ellos usa el n log in mientras que otro formulario usa n al cuadrado, mucha gente podría esperar 10 segundos para que se envíe un formulario Pero si tuviéramos que esperar 16 minutos, eso no va a pasar. Nadie va a hacer eso. Entonces vamos por un poco más alto de un ejemplo. Digamos que tenemos 25 mil datos. Entonces hacemos las 25 mil piezas. Se trata de 25 veces basado en bitácora dos de 25,000. Obtenemos 365,000 veces milisegundos. Esto luego sale a 6 minutos y 5 segundos. Tenga en cuenta aquí, esto es importante tener en cuenta es que incluso con $25,000 o 24,000 piezas más de datos Esto todavía toma 10 minutos menos que si usáramos n al cuadrado en el anterior En fin, ahora echamos un vistazo aquí abajo al n cuadrado. Entonces hacemos 25 mil veces 25 mil. Eso nos hace multiplicar 625 millones por milisegundos, y aquí obtenemos algo extraordinario Tenemos siete días y 5 horas para lograrlo. Así que son solo 25 mil datos, ahora hemos pasado de pasar de 6 minutos hasta siete días. Y por ejemplo, si hiciéramos 250 mil datos, esta tasa aquí sería algo en los años o los miles de años Sería algo donde no se lograría en nuestra vida, o la vida de los nietos, el sol podría quemarse antes de llegar al logro, antes de que el programa realmente termine Y entonces espero que este pequeño ejemplo de aquí, solo de esta pequeña matemática y sumando los milisegundos aquí, se pueda ver la gran diferencia, aunque se vean un poco iguales aquí y tal vez hasta un poco aquí abajo Cuando escalamos a más y más números, comenzamos a obtener inconsistencias gigantescas Y esas inconsistencias gigantes es de lo que trata el teorema de la informática Es de lo que trata el plan de estudios de informática. Yo solo estamos tratando de encontrar qué tipo de estructura o técnicas de datos debemos usar en cada situación dada para que podamos crear los algoritmos más eficientes posibles para que terminemos logrando las cosas rápidamente en lugar de gastar recursos de tiempo extra o ni siquiera poder lograr ds porque tardaría demasiado Y entonces esto es solo un poco de ejemplo de eso. Bien. 5. Big O: Entonces ahora tenemos una buena comprensión de N y cómo funciona exactamente, y se une a nuestro análisis de algoritmos, podemos comenzar a agregar algo a eso. Entonces sabemos que es una forma de clasificar qué tan rápido se ejecuta un algoritmo, dado un cierto número en cuanto tiempo va a tomar con respecto a ese número Entonces, ¿va a tomar justo a tiempo? Entonces si era 1,000, va a igualar 1,000 o va a tomar algo como n veces al cuadrado, donde cuando es 1,000, va a igualar a 1 millón Y este es un tipo de clasificación realmente importante. Sin embargo, los programas no son tan fáciles. No solo corren a una hora exacta todo el tiempo. Muchas veces tienen un atado. Entonces, por ejemplo, tal vez cuando se está cargando, va a ejecutar un n al cuadrado, pero ejecuta un in, y luego exporta in in log in Y así tenemos que poder mirar esto, y tenemos que mirar el programa y dar una clasificación sobre el programa en su conjunto. Entonces, por ejemplo, este programa, siempre nos fijaríamos en el peor de los casos siempre va al peor de los casos, tomar al cuadrado No obstante, en ciertos pasos, va a correr más rápido. Y por eso, en realidad tenemos aquí este tipo de tasa de sistema, que va a clasificar los límites en nuestro en notación Así que vamos a bajar esto y echar un vistazo a esto. Estos de aquí arriba se llaman Omicron. Tienes a Theta en el medio y luego a Omega, y este es Omega minúsculas aquí abajo Y así se puede ver que son alfabetos griegos, pero solo muchas veces en matemáticas, usamos el griego porque el alfabeto se vuelve confuso Así que usamos el griego para representar simbólicamente las cosas. Y en esta instancia, cada uno de estos símbolos griegos representa simbólicamente un Entonces lo que tienes aquí es que dibujemos, por ejemplo, un encuadernado justo en el medio aquí. Y aquí arriba es más rápido. Entonces voy a decir aquí arriba va a ser más rápido, y abajo aquí va a ser más lento. Entonces, nuestra primera notación es la pequeña O, y puedes ver que simplemente no nos gusta decir Omicron, como una gran notación Omicron que solo Entonces solo decimos poco grande O. Y tan poco aquí mismo. Simplemente significa que va a ser más rápido, lo que significa que el programa siempre será más rápido que este atado. Entonces, por ejemplo, si nuestro encuadernado estaba cuadrado, aquí mismo, si tuviéramos poco O de n al cuadrado Aquí mismo, veríamos que significa que nunca va a tocar n al cuadrado En realidad siempre va a ser más rápido que n al cuadrado. Entonces siempre va a estar justo por encima de esta línea, pero más rápido que n al cuadrado Y entonces lo que podemos hacer es que en realidad podemos usar esto para averiguar el límite. Entonces el siguiente que tenemos es que tenemos grande O. Y grande O significa que va a ser más rápido o igual a. Entonces eso significa que va a tocar esta línea o ser más rápido. Entonces va a ser en el peor, y eso es algo que es muy clave aquí. Esto significa en el peor de los casos. Va a ser en cuadrado. El siguiente que tenemos es Theta, lo que significa que no va a tocar a ninguno de estos dos No va a ir bajo, y no va a ir alto. Lo que va a ir está justo en esta línea. Entonces, no importa lo que vaya a estar en cuadrado, va a estar justo en esta línea en alguna parte Y entonces el siguiente abajo que tenemos es más lento o igual a. Entonces tenemos este es Omega, y este es más lento o igual a. Entonces toca esta línea, y siempre es más lenta. Entonces, ya sabes, llegamos n a la tercera n a la cuarta aquí abajo, aquí arriba, podríamos tener. Entonces siempre es más lento que esto, o igual a n al cuadrado Así que en el mejor de los casos. Entonces este es en el mejor de los casos. Va a correr en esto si pones esto. Entonces, por ejemplo, si escribimos de n al cuadrado así. Cortemos un poco ahí mismo, pero de n al cuadrado así, entonces entendemos que este programa siempre se ejecutará en el mejor de los casos, correrá es n al cuadrado Lo que significa que puede correr peor que eso. Y luego debajo de eso tenemos más lento que, lo que significa que siempre va a correr peor que n al cuadrado Nunca tocará al cuadrado, pero correrá peor que NSquared Y entonces, ¿por qué es esto importante? ¿Por qué queremos enfocarnos en éste de todos estos? Y eso es porque Big O dicta el peor de los casos Y nos preocupa el peor de los casos porque dada la probabilidad y las estadísticas, nuestro programa podría tocar el peor escenario en algún momento, y queremos saber sin duda, ¿cuál es ese peor escenario? Entonces por eso usamos la gran O. Está en el peor, qué va a ser. Y ya pueden ver, voy a volver a sacar el gráfico aquí mismo. Cuando tenemos esta idea, cuando tenemos la capacidad de decir, cuál va a ser nuestro programa, en realidad podemos empezar a llenar esto. Entonces si tenemos, por ejemplo, tal vez grande O de N. Entendemos que en el peor va a estar en. Entonces podría estar en, pero también podría ser cualquier cosa mayor que en. que podamos preparar todos nuestros diagramas de tiempo y bocetos y cualquier cosa por el estilo, partiendo de la suposición de que nunca va a ir este lado de la línea Siempre va a ir de este lado. Y eso es realmente poderoso porque ahora podemos comenzar a comparar programas en los peores casos, y podemos empezar a ver que tal vez cuando un programa escala, por ejemplo, si tuviéramos un programa in log in versus un programa in, podríamos ver que cuando este escala, va a ser peor que este. Así que vamos a tomar vamos a desglosar esto un poco, y podemos ver por qué algunos de estos no tienen sentido Entonces, tenemos un programa que se ejecuta en Little O n cuadrado, que significa que es más rápido que n al cuadrado Entonces eso significa que podría estar en cualquier lugar desde n al cuadrado hasta Básicamente, tiene que ser solo más rápido que eso Entonces no va a ser cuadrado, pero podría ser cualquier cosa más rápido que al cuadrado Y este es algo así como el gran O. Pero la cosa es lo que nos dan, así que es pequeña O de N. En realidad no podemos tocar esto. Entonces solo lo hace un poco confuso. Nos da un encuadernado, pero no nos facilita ver. No podemos inmediatamente mirar esto e irnos, Oh, esto va a correr el tiempo. Tenemos que mirar esto y ser como, Oh, va a correr más rápido que, pero realmente no sabemos dónde. Y realmente no nos da mucho margen de meneo. Y entonces tenemos nuestra gran notación O. Y eso es lo que acabamos de repasar, es que podemos ver esto y vamos a estar como, Oh, en el peor de los casos, se ejecutará al iniciar sesión. Theta sería genial si siempre pudiéramos usar theta. Esto es igual o a veces se usa como promedio, pero la mayoría de las veces, significa igual a. Entonces esto sería genial. Pero el problema es que los programas no siempre funcionan exactamente a lo largo de una línea. A veces pueden correr tal vez en un momento, corre un, pero en un momento, se ejecuta e inicia sesión, y va a cualquier parte entre esto. Entonces Theta es demasiado específica para que realmente nos guste. Y entonces estos son prácticamente sin sentido porque no nos dan mucha información Piénsalo. Este de aquí mismo, que es Omega. Entonces Omega al cuadrado. Eso significa que va a ser más lento o igual a Omega al cuadrado, que es como estás diciendo, nuestro programa va a estar funcionando al cuadrado o va a ser ¿Cómo se supone que planeemos con eso en mente? Porque más lento podría entrar en el infinito. Podría ser lo más lento posible, y nunca podríamos prepararnos para eso porque nunca tendríamos un límite en él. Estaríamos como, Bien, así que va a correr lo rápido que podría tomar n al cuadrado, podría tomar en factorial, podría tomar el infinito No nos ayuda a analizar el programa porque hay este lado infinito en él. Y exactamente la misma idea con el pequeño Omega aquí también, es que se va al infinito en el lado malo, lo que no nos ayuda. Entonces estos nos ayudan porque el lado malo es, déjame correr algo de esto aquí y hacer un poco más de espacio. Entonces estos nos ayudan porque el lado malo. Entonces, digamos que por aquí está fuera al infinito. Nos da un encuadernado. Entonces cualquier cosa, va a estar en el peor justo aquí, pero podría ser mejor. Y no nos importa. Al igual que, si vuelve y corre esa constante, está bien. Eso está perfectamente bien. Eso significa que nuestros programas funcionan muy bien. Claro. Pero podemos planear para eso. Simplemente significa que nuestro programa se va a ejecutar más rápido de lo que esperábamos. Entonces lo que podemos hacer entonces es planear para el peor de los casos. No obstante, si vas del otro lado de esta línea, no puedes planear para el infinito. Entonces es por eso que Big O es tan importante es que es la más útil de todas estas notaciones Nos da un peor de los casos. Y así, tomemos un ejemplo de cómo podríamos aplicar esto a un problema en particular. Entonces, por lo general, lo que siempre haces es usar el peor de los casos, decir, ¿en qué momento del programa, es decir, ¿en qué momento del programa, va a ser el más ineficiente Entonces aquí, por ejemplo, digamos que teníamos grande O de n al cuadrado Tuvimos una gran O de inicio de sesión. Grande O de N y luego grande O de tiempo constante. Y así estos de aquí abajo son geniales. Pero la cosa es, es que pase lo que pase, siempre vamos a ser cuellos de botella por este tipo de por este tipo Y eso es porque nuestro tiempo de carga aquí arriba está en cuadrado, lo que significa que este programa va a rawnet en cuadrado más iniciar sesión, más, más al primero, que me permite mantenerlo algo Iremos más uno. Y podrías estar pensando, ¿por qué estoy haciendo esto? Y eso es porque en realidad puedes sumar cada parte de los pasos juntos. Entonces porque haces esta parte, entonces, haces esta parte, luego haces esta parte, luego haces esta parte. Así que en realidad puedes sumarlos todos juntos. Y recuerdo lo que estábamos haciendo antemano cuando estamos hablando cómo tratamos de ver un programa como va al infinito. Entonces, si nos fijamos en este número, ¿cuál de estos va a superar a los demás cuando vayamos al infinito Bueno, por ejemplo, pongámoslo en 1 millón. Cuán significativo es 1 millón, que va a ser verso 1 millón, va a ser verso, tal vez en algún lugar alrededor de 3 millones, va a ser versículo 1 cuadrillón o tal vez 1 billón, seis uno Este va a ser sustancialmente más grande. Estas van a ser una porción cada vez más pequeña del número ya que va al infinito. Hasta el punto en que éstas irán cerca de cero como significancia. Entonces empezarás a tener, ya sabes, un número de Google, que es 100 cero más tal vez como 8 millones por aquí o algo así. Y eso quiere decir que esta parte de aquí es completamente insignificante en este punto Entonces lo que hacemos es eliminar los inferiores y el tiempo de ejecución de este programa está en cuadrado Y luego, así que vamos a una especie de cemento que con otro ejemplo aquí. Digamos que teníamos gran opinión que teníamos grande O de n al cuadrado. Grande O de n al cuadrado. Big O de llegó a dibujar la s aquí. Grande O de n al cuadrado otra vez, y luego digamos ahora tenemos grande O de n tercero Y entonces ahora lo que tenemos aquí es que tenemos n al cuadrado más n al cuadrado más n al cuadrado más el tercero Y así en realidad podemos combinar estos abajo a tres n cuadrado más n el tercero Y ahora, recuerden de lo que hablamos en la última conferencia sobre la notación final. Estos no importan. La tasa constante aquí no importa porque a medida que entramos en el infinito, ésta se vuelve cada vez menos significativa hasta que una vez que llegamos a un número suficientemente alto, se convierte básicamente en cero. Para que podamos tacharlo. Y así ahora tenemos n al cuadrado más n tercero. Y entonces, claro, éste va a despegar mucho más alto que el otro. Entonces nuestro programa acaba por estar en tercer lugar. Y ahora como todas estas son grandes anotaciones O, sabemos en el peor de los casos, nuestro programa se ejecutará a la tercera, lo que significa que ahora tenemos este límite de tercero e infinito de tiempo de ejecución se apaga de esta manera Y ahora podemos planear eso en el peor de los casos, vamos a tener nd tercero, y podemos planear todo todo el camino de regreso al tiempo constante porque ahora todo lo que tenemos es justo esto atado aquí mismo. Entendemos que, ya sabes, si ponemos 1 millón de datos, puede que no funcione. A lo mejor podemos buscar traer esto, pero nos da un lugar para comenzar. Nos da algún lugar para compararlo con otros. Entonces esa es la notación O grande. Muy importante y con el tiempo, vas a empezar básicamente, esto se convertirá en una segunda naturaleza solo siendo capaz de mirar esto. Realmente nunca vas a ver a estos otros con demasiada frecuencia. Verás éste a veces si dice, como cierto punto de un programa es igual a este tiempo de ejecución, entonces verás éste. Pero aparte de eso, estos dos probablemente nunca verán y probablemente nunca verás al pequeño mercon dos Entonces estas anotaciones de aquí solo las memorizan, entienden lo que significan, y deberías estar listo para ir Empezarás a entender mucho más documentos de informática. 6. Mundo real: Ahora, hemos aprendido mucha teoría. Sigamos adelante y demos un paso atrás y repasemos algunos análisis de código del mundo real. Ahora, no voy a estar usando código complejo ni ningún tipo de código que necesites saber aquí mismo. Todo es pseudocódigo, y voy a estar explicándolo en cada paso del camino como si nunca antes hubieras tocado código porque así es como quiero explicar todo este tipo de curso es que estamos viendo la teoría detrás de todo, no el código Sin embargo, aplicarlo a algo del mundo real puede ayudarte a conocer, a entender algunos de los conceptos, y por eso lo estamos haciendo. Así que vamos a ver nuestro primer trozo de código. Voy a seguir adelante y caminar por esto aquí. Entonces lo que tenemos es que lo tenemos dice, lo escribí en pseudo ese tipo de simplemente lee de la lengua, algo que puedes mirar y entender lo que está pasando Entonces, dice, para cada dato en lista de datos. Así que vamos a crear una lista de datos aquí en un segundo, imprimir datos a la pantalla. Bien, bastante fácil. Digamos que ingresamos en esto, un dato, una lista aquí que tal vez sea tres, dos, diez. Y luego iremos a Búfalo. Entonces esto es tres enteros y una cadena. Así sería técnicamente clasificado, pero ni siquiera vamos a mirar eso. Se trata de cuatro piezas de datos. Y entonces lo que estamos diciendo es que para cada dato, así que por cada dato de nuestra lista, vamos a imprimir esos datos en la pantalla. Entonces, en nuestra situación aquí, ¿qué hay en? Bueno, en esta situación aquí mismo, en iguales, el uno, dos, tres, cuatro, porque tenemos cuatro piezas de datos. Entonces en esta situación, n equivale a cuatro. Entonces ahora veamos cuál sería el tiempo de ejecución de esto. Así que tenemos para cada dato, y luego imprimimos en la pantalla. Entonces, bien, vamos a bajar la lista aquí. Vamos con nuestro primer dato. Entonces nuestro primer dato es tres. Tomamos tres de nuestra tasa de documentos aquí. Entonces esto es esto es cero en una matriz o si quieres pensarlo , esto es uno, dos, tres, cuatro, las computadoras suelen ir con cero, uno, dos, tres, es solo la forma en que funcionan. Así que vamos a agarrar nuestro primer dato aquí mismo, y luego lo vamos a imprimir en la pantalla. Entonces agarramos nuestros tres, imprimimos a la pantalla. Entonces eso es un tiempo de ejecución. Entonces nuestro tiempo de ejecución en este momento es uno. Y luego ahora vamos a agarrar a los dos porque vamos bajando de la lista. Entonces, por cada dato, hemos tocado este. Entonces ahora pasamos a éste. Entonces ahora agarramos dos e imprimimos a la pantalla. Entonces ahora nuestra pantalla se ve así. Y entonces ese es un tiempo de ejecución adicional ahí mismo. Eso es un tiempo de ejecución. Y luego ahora imprimimos nuestro siguiente dato , que es diez. Entonces ahora tenemos tres, dos, diez. Eso es tiempo de ejecución adicional ahí mismo. Y luego ahora imprimimos búfalo, que serían tres, dos, diez búfalos. Así. Y ese es un tiempo de ejecución adicional. Porque todo lo que estamos haciendo es que estamos agarrando el dato y lo estamos imprimiendo. No hay ningún proceso de pensamiento especial entrando aquí. Solo estamos agarrando, imprimiendo, agarrando, imprimiendo , agarrando, imprimiendo Y ahora, si sumamos todo esto, veremos que sale a uno más uno más uno más uno más uno más uno, lo que equivale a cuatro. Y así nuestro tiempo de ejecución en esta situación es cuatro, y verás que nuestro tiempo de ejecución es igual a la cantidad de tasa aquí. Y si solo podemos pensar en esto teóricamente por un segundo, si tuviéramos aquí 1 millón de piezas de datos, habría en ningún momento del programa donde alguna vez tuviéramos que tocar más de 1 millón de piezas de datos Entonces no importa lo que hagamos aquí, ejecución va a ser cualquiera que sea nuestro n, lo que significa que lo que tenemos aquí es un tiempo de ejecución de N. En esta situación particular, podríamos usar Theta como n porque en realidad es igual a n. Aquí no hay ningún tipo de margen de maniobra, pero vamos a seguir adelante y solo decir que en el peor de los casos va a estar porque esa es en el peor de los casos va a estar la notación que nos gusta Entonces este es un ejemplo de un in, que a esto se le llama un bucle de cuatro. Entonces, cuatro bucles suelen ser un ejemplo de un in en una situación. Pasemos aquí a un problema un poco más complejo. Así que permítanme desglosar este también. Lo que tenemos aquí es que dice, por cada dato en una lista de datos. Entonces eso significa que en lugar de llamarlo datos ahora, cada pieza de datos en una lista va a estar en. Comprobar si los datos están en la lista. Entonces vamos a ir por cada dato en la lista de datos, si n es igual a W print true. Así que sigamos adelante y una especie de desglose un poco este, también. Vamos con nuestro mismo ejemplo de antes, que fueron tres, dos, diez Buffalo. Así. Y en esta situación, nuestro in sigue siendo igual a cuatro. Y entonces ahora lo que vamos a hacer es que vamos a ver el primer problema aquí. Entonces echemos un vistazo bien. Ahora, digamos, vamos a agarrar cada uno de estos datos, así que vamos a agarrar los tres, y eso ya está dentro. Y luego ahora para cada dato en esta lista de datos, y se puede ver que estos nombres son exactamente los mismos. Entonces eso significa que esta es la lista de datos. Estamos comprobando por ambos. Entonces tenemos nuestros tres. Tenemos a nuestros tres agarrados. Y ahora estamos tratando de verificar si estos tres de aquí son equivalentes a algo aquí arriba. Y la única manera de hacerlo es la fuerza bruta. Entonces vamos a tomar este tres. Vamos a comprobarlo con el primero. Vamos a comprobarlo con el segundo. Vamos a comprobarlo con el tercero. Vamos a comprobarlo con el cuarto. Entonces eso va a ser una, dos, tres, cuatro operaciones. Así que vamos a romper esto, como, muy lejos aquí abajo. Tenemos nuestros tres. Hemos agarrado a nuestros tres, y ahora lo estamos comprobando, es igual Déjame hacer eso un poco más pequeño porque va a ser un poco más grande de una gráfica. Entonces estamos diciendo hace tres iguales La primera pieza de nuestros datos, que van a ser los tres otra vez porque no le dijimos que comenzara en un número que no es ni ninguna cosa elegante como esa. Sólo estamos revisando esta lista por segunda vez. Entonces tenemos nuestros tres, y estamos comprobando si es igual al primero. Entonces, ¿equivale a tres? Sí, lo hace. Por lo que esto imprimirá un mensaje verdadero. Y esto tomó una operación. Ahora bien, ¿nuestros tres equivalen a dos no lo hace? Entonces no imprimimos nada. Esa es una operación. ¿Nuestros tres equivalen a diez. No lo hace. Entonces esa es una operación. ¿Nuestros tres igualan a Buffalo? No lo hace. Entonces esa es una operación. Y ahora ya terminamos con los tres. Así que hemos seguido adelante. Nosotros nos hemos ocupado de los tres. Así que vamos a crear una segunda aquí abajo. Veamos que T uno va a ser con el que estamos comprobando. Son exactamente lo mismo, pero solo quiero hacer que esto sea un poco más visual para todos ustedes. Entonces terminamos con los tres. Entonces pasemos a los dos ahora. Entonces, ¿dos equivalen a tres? No lo hace. Esa es una operación. ¿Dos es igual a dos? Lo hace. Esa es una operación. ¿Dos es igual a diez? No lo hace. Esa es una operación. ¿Dos son iguales a Buffalo? No lo hace. Esa es una operación. Y luego bajemos por la lista uno más. ¿Diez es igual a tres? ¿No? Esa es una operación. Hace diez igual a dos, no lo hace. Esa es una operación. Hace diez igual a diez. Lo hace. Esa es una operación. Hace diez igual a Búfalo. No lo hace. Esa es una operación. ¿Buffalo? Sólo voy a abreviarlo como B aquí, así que no quiero seguir escribiendo Buffalo ¿Buffalo equivale a tres? No lo hace. Entonces esa es una operación. ¿Buffalo es igual a dos? No lo hace. Entonces esa es una operación. ¿Buffalo equivale a diez? No lo hace. Entonces esa es una operación. ¿Buffalo es igual a Búfalo? Lo hace. Entonces esa es una operación. Y ahora, si sumamos aquí todas estas tarifas arriba, lo que vamos a ver es que esto va a ser uno, dos, tres, cuatro, cinco, seis, siete, ocho, nueve, diez, 11, 12, 13, 14, 15, 16. Entonces en esta situación, nuestro in era cuatro, pero nuestro tiempo de ejecución era aproximadamente 16. ¿Y qué sale a ser eso? Bueno, eso sale a estar en cuadrado. Entonces tomemos si tomamos cuatro y lo cuadramos, equivaldría a 16 Y teóricamente podemos pensar en esto también. Si ampliáramos esto a cinco, no solo tendríamos cinco adicionales aquí, sino que tendríamos que multiplicarlo porque ahora tendríamos que verificar uno adicional también. Entonces cada instancia, tendremos cinco y tendremos otros cinco enteros, lo que lo cuadra. Entonces en esta situación, nuestro tiempo de ejecución está en cuadrado Y la razón de esto es pesar de que tenemos dos cuatro bucles, ahí está lo que se conoce como anidación Hemos anidado un bucle cuatro dentro de otro bucle de cuatro. Entonces esta parte de aquí afuera. Dibujemos esto en rojo. Esta parte de aquí afuera está adentro. Si bien esta parte dentro también está adentro. Entonces lo que hacemos es tomar la entrada por fuera. Lo multiplicamos por la entrada en el interior, y nos metemos al cuadrado Y así ese será nuestro tiempo de ejecución final para esta situación. Entonces, como dije, este curso no está muy designado escribir código o externitmo sino que aún así define la teoría, pero pensé que esto podría ayudar a mostrarte de lo que hemos estado hablando todo este tiempo, cómo el código podría analizarse realmente para que podamos entender estas diferentes piezas Y se puede ver que pase lo que pase, en realidad acabamos de aprender algo muy importante. Cuatro bucles siempre van a estar adentro, pero los cuatro bucles anidados siempre van a estar por muchos anidados que haya Entonces, si esta de aquí anidó una tercera, esta sería una fórmula n al cuadrado, y empiezas a levantarte en números realmente grandes para comenzar a verificar todas estas cosas Entonces espero que este ejemplo práctico te haya ayudado a entender un poco mejor este concepto. 7. Ejemplo de estructura de datos: Entonces ahora vamos a discutir un ejemplo un poco más concreto. Y vamos a estar discutiendo la diferencia entre una matriz y una lista y ¿cómo va a vincularse eso con lo que hemos estado aprendiendo? Y lo que hemos estado aprendiendo es la escalabilidad, almacenamiento de información y cómo reacciona eso con el tiempo de ejecución a medida que llegamos a más y más información Entonces con estos dos ejemplos aquí, vamos a estar viendo una matriz, y vamos a estar mirando una lista, y vamos a estar mirando su acceso y agregaremos a los tiempos anteriores de estas matrices. Entonces con esto, lo que vamos a estar viendo es, ¿cómo escala eso a lo largo del tiempo con estas dos formas diferentes de almacenar datos? ¿Cómo podemos usar ese análisis para averiguar qué solución nos gustaría usar en el futuro Echemos un vistazo rápido. Vamos a hacer una visión general de lo que estas estructuras de datos son una visión general muy ligera. No hace falta saber mucha informática para seguir junto con esta lección, pero va a ser muy importante agregar un elemento concreto a lo que hemos estado aprendiendo. Así que la primera estructura de datos que vamos a ir aquí es la matriz. Entonces, con una matriz, lo que esencialmente estamos haciendo es tomar una pieza de datos continuos de nuestra memoria Ahora bien, el procesador va a estar básicamente diciéndonos dónde vamos a estar agarrando esto Podría ser el carnero, podría ser el cache. Podría ser el disco duro. No importa. En este caso, es la memoria, y eso es todo lo que necesitamos saber. Así que con la memoria, Básicamente, estamos separando toda nuestra memoria en pequeños bloques de datos. Cuando le pedimos al procesador una matriz, va y encuentra un pedacito de memoria para nosotros. Eso es continuo que puede encajar en lo que estamos solicitando. En este caso, estamos solicitando cuatro datos aquí. Entonces es un tamaño de matriz de cuatro. Ahora, cuando hacemos esto, lo estamos creando, es continuo, pero por otro lado, no tenemos acceso a ellos, lo que significa que si necesitamos aumentar el tamaño de esta matriz, tenemos que crear una matriz completamente nueva y copiar cosas sobre ella. Y esa va a ser la desventaja. Así que vamos a repasar nuestros dos aquí, nuestro acceso y nuestro anuncio. Así que cada vez que estamos accediendo a los datos en array, lo genial es que va a ser en tiempo constante porque cada vez que estamos pidiendo esto, es continuo. Por lo tanto, podemos pedir piezas de datos muy específicas dentro de aquí. Entonces, si necesitamos averiguar, si necesitamos agarrar algo de la segunda o en esta posición, el tercer lugar en la matriz, que está indexada por dos Eso solo significa que todo en informática es índice cero, por lo que la primera columna es cero, no una. Podemos ir con esta pequeña tasa de fórmula aquí, que funciona básicamente en cada lenguaje de programación. Solo significa agarrar ese elemento ahí mismo. Nos lo va a devolver en tiempo constante. Básicamente va a escupir lo que hay ahí mismo en tiempo constante Podríamos tener toneladas y toneladas de información. Esto podría tener 2000 de largo. Esto podría ser de 3 mil de largo. Esto podría ser de 20,000 30,000 dólares y así sucesivamente y así sucesivamente. Y si solo ponemos eso aquí, lo recuperaremos constantemente cada vez. Y eso es lo que permite que nuestra matriz tenga un acceso del peor de los casos , tiempo constante. Siempre va a ser constante. Ahora, aquí está el problema. Recuerden cuando dije que cuando agregamos al final de esto, si hemos alcanzado nuestro límite de matriz, hemos llenado la matriz, tenemos que solicitar una matriz completamente nueva, lo que significa que el módulo de memoria es básico va a matar a nuestra matriz anterior y luego encontrar un conjunto más grande en el que podamos poner información. Bueno, para asegurarnos de que no perdemos nuestros datos antiguos, tenemos que copiar cada pieza. Más de uno a la vez. Entonces, si tenemos 300,000, 3 millones, 3 mil millones de entradas, todas tienen que ser copiadas, y cada dato aquí tiene que ser tocado. Y eso es muy, muy importante porque eso significa que a medida que nuestro tamaño de nuestra matriz, medida que aumenta el número de entradas que tenemos, también aumenta el número de operaciones que tenemos que usar. Y aumenta de manera lineal, lo que significa que tenemos un peor escenario de O a la hora de agregar a una matriz. Así que ahora, hemos cubierto bastante bien la matriz. Et 'sake mira aquí abajo a nuestra otra estructura de datos. La lista. La lista es interesante porque lo que estamos haciendo con una lista es que básicamente vamos a nuestro dato aquí. Lo estamos solicitando. Y en lugar de darnos un dato continuo, esencialmente nos da un elemento a la vez. Para que podamos solicitar uno, ya estará aquí. Solicitamos otro. Crea un puntero, y luego va a esa pieza. Queremos otro. Bueno, va a ir por aquí, y así sucesivamente y así sucesivamente. Y se puede ver que no hay una manera realmente establecida de que vaya a estar haciendo esto. Estoy seguro de que, ya sabes, los módulos de memoria avanzados y todo por el estilo tiene una manera eficiente, pero no van a ser continuos. Van a estar por todas partes de la manera más eficiente que considere conveniente. Lo que significa que si estamos tratando de acceder a nuestra información y queremos tomar esta información aquí mismo, bueno, mira este desastre aquí mismo. Tenemos que seguir el punto. Entonces tenemos que empezar aquí e ir aquí. Entonces aquí, luego aquí, luego aquí. Y, Oh, ahí está nuestro dato. Y lo que eso significa es que cuando accedemos a nuestros datos, si estamos tratando de encontrar algo en la lista, algo más lejos, y, ya sabes, podría ser algo así como un número, una letra, una oración, una imagen, cualquier cosa. Vamos a poner PE aquí. Para llegar a P, tenemos que ejecutar toda la lista enlazada para encontrarla. Entonces, ¿cuál es nuestro tiempo de acceso? Bueno, eso no suena constante. Eso suena como a medida que crece el número de elementos, nuestro tiempo de acceso también crece, lo que parece que va a ser acceso del peor de los casos, va a ser tiempo lineal a la entrada. Ahora, la lista tiene una ventaja de la matriz con la adición, siempre y cuando mantengamos lo que se conoce como un puntero hacia atrás, que esencialmente es solo una pieza de datos que actualizamos eso para que sea una flecha directa hacia atrás. Entonces, si añadimos una nueva pieza, esencialmente solo tomamos esa flecha y solo la movemos a la nueva pieza. Si mantenemos eso actualizado, que es solo una sola operación constante, bueno, agregar datos a esto es tiempo constante. Siempre va a ser exactamente la misma operación. Señalamos a la parte de atrás y agregamos a la siguiente otra vez. En realidad, en este caso, no lo hacemos Sí, sí, lo hacemos. Entonces tenemos el puntero de atrás aquí. Entonces, si necesitamos agregar a la parte posterior, seguimos el puntero hacia atrás hasta el final de la lista de enlaces, y luego solo agregamos un nuevo elemento y luego actualizamos el puntero al nuevo elemento. Es una operación constante. A pesar de que hay un par de pasos ahí, siempre va a ser lo mismo. Si hay mil millones de piezas o una sola pieza, tienen que pasar exactamente las mismas cosas. Seguimos el puntero hacia atrás, agregamos uno nuevo, y luego ponemos nuestros datos en él. Entonces eso significa que nuestro tiempo de suma en realidad va a salir como constante. Entonces ahora podemos ver que con estas dos estructuras de datos, tenemos dos posibilidades diferentes de una solución aquí. Si necesitamos tiempo de acceso rápido, así que piensa en la lista en tu teléfono, tu lista de contactos en tu teléfono. Necesitamos un tiempo de acceso rápido con eso. No quieres encontrar a alguien en los zs de tu lista de contactos y tienes que esperar a que busque entre todos los demás datos Eso no suena como que sea muy eficiente en absoluto. Eso sería una tontería. Y no le agregamos muy a menudo. Ya sabes, agregamos un contacto aquí y allá, pero no es algo que agreguemos continuamente una y otra vez. Así que la matriz podría ser la mejor solución para ese problema en particular. Ahora, con una lista, tal vez tenemos una operación que necesita almacenar lotes y lotes y muchos elementos a lo largo del tiempo, pero casi nunca necesita acceder a ellos. Entonces necesitamos constante, ya sabes, agregar tiempo, pero realmente no necesitamos mucho tiempo de acceso. Bueno, entonces estaríamos viendo una lista para esa solución. Entonces, las cosas que estamos aprendiendo en esto pueden ser utilizadas para encontrar mejores soluciones a nuestros problemas. Y en este caso particular, son problemas de almacenamiento en la programación informática. Pero esto puede aplicarse tanto a otras áreas del mundo informático como a la vida real también. La solución que tienes es escalable. Y con esto, podemos ver cuáles son y cuáles no. 8. Video del proyecto: Ahora que hemos pasado por la notación, el bigot, y todo el escalado que ocurre entre ellos El proyecto aquí va a ser tomar todo lo que has aprendido y analizar algo en tu vida y decirnos cuál es su procedimiento, y luego cuál es su firma de cronometraje. Entonces, esto puede estar relacionado con la informática. Podrías hacer un algoritmo, un algoritmo de búsqueda o pensar en, ya sabes, cómo podría funcionar una solicitud de amistad en Facebook o algo así, pero también puede ser simplemente observacional a tu alrededor Puede ser dije al inicio del curso, como un archivador o cómo alguien podría unirse a un miembro de tu organización o cómo podrías buscar y encontrar algo ya sea en un gran conjunto de datos o una agrupación de personas o cualquier cosa de esa naturaleza. Quiero que seas creativo y solo analices el mundo que te rodea con el conocimiento que has aprendido y lo compartas. Es un ejercicio bastante divertido, y es bastante bueno ver que básicamente lo que estamos haciendo es simplemente aplicar matemáticas cada vez que estamos programando o estamos trabajando con este tipo de teoría de las matemáticas en sí. Si lo estamos aplicando, estamos aprendiendo cómo funciona y opera el mundo, y luego nos involucramos con él. Y así de eso se trata este proyecto. Crear un pensamiento crítico y luego analizarlo y como reforzar lo que hemos aprendido. Estoy muy emocionada de ver lo que se le ocurre a todos, y estaré en la sección de proyectos respondiéndoles. Entonces Sea ahí, gracias a todos por unirse a este curso.