Información básica sobre ciencias de la computación: domina la teoría detrás de la programación | Kurt Anderson | Skillshare
Buscar

Playback Speed


  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Información básica sobre ciencias de la computación: domina la teoría detrás de la programación

teacher avatar Kurt Anderson, Computer Scientist, Multi-Media Designer

Ve esta clase y miles más

Obtenga acceso ilimitado a todas las clases
Clases enseñadas por líderes de la industria y profesionales activos
Los temas incluyen ilustración, diseño, fotografía y más

Ve esta clase y miles más

Obtenga acceso ilimitado a todas las clases
Clases enseñadas por líderes de la industria y profesionales activos
Los temas incluyen ilustración, diseño, fotografía y más

Lecciones en esta clase

    • 1.

      Introduction

      4:48

    • 2.

      1-1 Time Complexity Introduction

      2:12

    • 3.

      1-2 Math Refresher: Logarithmic Functions

      11:07

    • 4.

      1-3 Math Refresher: Factorial Functions

      3:19

    • 5.

      1-4 Math Refresher: Algebraic Expressions

      2:47

    • 6.

      1-5 N-notation

      18:55

    • 7.

      1-6 Big O Notation

      12:58

    • 8.

      1-7 Real World Big-O Example

      9:51

    • 9.

      2-1 How is Data Stored

      8:38

    • 10.

      2-2 Fixed Array Introduction

      5:09

    • 11.

      2-3 Fixed Array Run Times

      12:23

    • 12.

      2-4 Binary Search Algorithm (Fixed Array Sorted Search)

      9:59

    • 13.

      2-5 Circular Arrays

      8:00

    • 14.

      2-6 Dynamic Arrays

      15:51

    • 15.

      2-7 Array Review

      7:57

    • 16.

      2-8 Array Real World Examples

      5:42

    • 17.

      3-1 Nodes

      4:19

    • 18.

      3-2 Linked List

      13:36

    • 19.

      3-3 Linked List Run Times

      14:59

    • 20.

      3-4 Doubly Linked Lists

      8:07

    • 21.

      3-5 Tail Pointer

      5:14

    • 22.

      3-6 Linked List Review

      3:31

    • 23.

      3-7 Linked List Real World Examples

      3:00

    • 24.

      4-1 Stacks

      9:41

    • 25.

      4-2 Stack Example

      11:05

    • 26.

      4-3 Queues

      8:48

    • 27.

      4-4 Queue Examples

      9:42

    • 28.

      4-5 Queue and Stack Run Times

      6:03

    • 29.

      4-6 Stack and Queues Real World Examples

      7:01

    • 30.

      5-1 Sorting Algorithm Introdcution

      1:40

    • 31.

      5-2 Bubble Sort

      10:12

    • 32.

      5-3 Selection Sort

      9:49

    • 33.

      5-4 Insertion Sort

      9:03

    • 34.

      5-5 Quick Sort

      14:38

    • 35.

      5-6 Quick Sort Run Times

      10:31

    • 36.

      5-7 Merge Sort

      11:57

    • 37.

      5-8 Merge Sort Run Times

      7:39

    • 38.

      5-9 Stable vs Nonstable

      6:34

    • 39.

      5-10 Sorting Algorithm Real World Examples

      4:01

    • 40.

      6-1 Basics of Trees

      7:37

    • 41.

      6-2 Binary Search Tree

      8:34

    • 42.

      6-3 BST Run Times

      7:36

    • 43.

      6-4 Tree Traversals

      13:04

    • 44.

      6-5 Tree Real World Examples

      4:29

    • 45.

      Timing - Project Prep

      6:47

  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.

8,346

Students

6

Projects

Acerca de esta clase

¡Domina la teoría para convertirte en buen programador! 

Si quieres aprender la teoría que hace a los mejores programadores, ¡has venido al lugar correcto!  Es perfecto para cualquier persona interesada en aprender los fundamentos de la teoría de la informática. 

¡No es necesaria experiencia previa! 

La ciencia y la tecnología de la computación a menudo se consideran cosas solo para mentes análogas. Sin embargo, creo que la tecnología y su teoría son para todos. Así que diseñé este curso para enseñar cada tema de varias maneras fáciles de digerir. A través de estos múltiples pasos de refuerzo, creo que cualquiera puede seguir y tener éxito. 

¿Por qué es importante la teoría de la programación? 

Comprender la teoría de la informática es lo que diferencia a los grandes programadores de la media. La teoría de la programación es algo que trasciende un único lenguaje de programación. Te da habilidades y técnicas que puedes aplicar a cualquier lenguaje de programación que toques. Aprender la teoría de la programación es tan importante, si no más, que aprender un lenguaje de programación singular como Java o C++.

La programación se basa en la resolución de problemas. Analizar un problema y encontrar la manera de que una computadora pueda ayudar con ese problema. La ciencia de la computación es la práctica de este proceso de análisis. Repasa las técnicas y los conocimientos necesarios para diseñar código eficiente y sostenible. 

En esta lección cubriremos lo siguiente: 

  • Sistema de números binarios

  • Notación N

  • Notación de Big O

  • Cómo analizar un programa

  • Arrays y sus ventajas

  • Los nodos y su importancia

  • Listas Linked y sus ventajas e implementaciones

  • Stacks implementados con arrays y listas para enlazarse

  • Colas de trabajo implementadas con matrices y listas vinculadas

  • Diversos algoritmos de clasificación y sus comparaciones

  • Árboles y árboles de búsqueda binaria

  • ¡Y mucho más! 

Meet Your Teacher

Teacher Profile Image

Kurt Anderson

Computer Scientist, Multi-Media Designer

Teacher

Hello, I'm Kurt.

I am a self-taught multi-media designer and computer scientist who has helped bring the creative vision of clients all around the world to life. Having 8+ years of experience in the Adobe Production Suite has given me a strong tool-set to create anything from videos to websites. Along with this, having a degree in Computer Science has given me a strong analytical mind for dealing with complex problems. Through these two disciplines I create a unique blend of efficiency and creativity. I believe anyone can become a designer or programmer. All it takes is practice.

I am also a world traveler and have lived in and learned from many different countries. During a 6 month stay in Japan, I became fascinated with their people's drive and craftsmanship. I try to i... See full profile

Level: Beginner

Valoración de la clase

¿Se cumplieron las expectativas?
    ¡Superadas!
  • 0%
  • 0%
  • Un poco
  • 0%
  • No realmente
  • 0%

¿Por qué unirse a Skillshare?

Mira las galardonadas Skillshare Originals

Cada clase tiene lecciones cortas y proyectos prácticos

Tu membresía apoya a los profesores de Skillshare

Aprende desde cualquier lugar

Ve clases sobre la marcha con la aplicación de Skillshare. Progresa en línea o descarga las clases para verlas en el avión, el metro o donde sea que aprendas mejor.

Transcripciones

1. Introducción: Hola a todos. Y bienvenidos a esta habilidad share Clase de Ciencias de la Computación 101. Este es un video de introducción. Mi nombre es Kurt Andersen. Voy a ser el instructor para tu clase que repasa los conceptos básicos de informática. Una especie de buena visión general de todos los temas que golpea la informática y algunas de las áreas principales , como en notación y tiempo y cosas así. En este curso, vamos a aprender estas siete cosas, y las voy a repasar en sólo un segundo. Pero quiero darle una especie de idea de por qué queremos aprender estas cosas. informática es la forma en que miramos la programación y los algoritmos para que pudiéramos hacerlos más eficientes. Y este término, llamado escalable escalable, significa que nuestros algoritmos se ejecutarán eficientemente si ponemos 10 piezas de datos o si ponemos , por ejemplo, un millón de piezas de datos. Deseamos que nuestros programas funcionen eficientemente con base o esencialmente con la mayor cantidad de datos posible . Piensa, por ejemplo, si estamos construyendo el próximo Facebook, imagina si solo lo diseñaron para 10 personas. Eso sería un problema, porque cuando llegaron hasta 1 millón de personas. De repente hay un gran tema. Hay tiempo, problemas. La gente no puede cargar cosas porque nuestros servidores y son algoritmos son todos ineficientes. Y si es demasiado ineficiente, en realidad podemos crear un algoritmo que haga exactamente lo mismo de dos maneras diferentes. Una de las formas en que podría tardar 10 años en terminar. Y de la otra forma podría tardar 10 segundos. Por lo que no queremos crear los algoritmos que tardan 10 años. Queremos crear los algoritmos que tardan 10 segundos. Estaremos repasando cosas así a lo largo del curso, rompiendo un par de problemas y obteniendo el tiempo para que pueda mostrar la diferencia entre los tiempos en esto, el curso usando estos diferentes algoritmos. Y luego al final del curso, vamos a estar repasando un proyecto. Entonces repasemos esto y hablaré del proyecto. Lo primero que hacemos es un poco de refresco matemático. Sé que podría pasar un poco desde que has estado en una clase de matemáticas, así que solo vamos a cubrir un par de lo básico. Algunas de las cosas que te ayudarán a lo largo del curso. Este no es curso intensivo de matemáticas por ningún medio. Estamos aprendiendo una especie de nuevas áreas, pero te ayudará si tienes una base sólida. Entonces vamos a un rápido refresco de matemáticas sólo para que ustedes puedan recordarlo. Y si tienes un poco de, ah, fondo tembloroso en algo, puedes buscarlo un poco y aprender algo más sobre eso antes de empezar. Entonces tenemos en notación que es una especie de los principios básicos detrás de la informática. Es nuestra herramienta en la caja de herramientas la que nos permite mirar dos algoritmos y decir cuál es más rápido. Entonces si miro a Al Gore que digo que está en log in versus otro algoritmo, que está en cuadrado como una computadora, científicos, sabemos lo que significan esos. Ahora podemos etiquetar las cosas de manera diferente y comunicar las velocidades del dedo del pie de otros científicos informáticos . Eso es lo que el en notación está trabajando sobre el almacenamiento de datos y un aumento. Esta es una forma de almacenar datos, uh, uh, disponibles en cada lenguaje de programación moderno como Java JavaScript, cosas como el desarrollo de IOS, que suele ser Objective C o Swift o Andrew Development, que es trabajo. Son Escocia todo un aumento listas enlazadas, pilas y colas, existen en todos esos. Entonces vamos a repasar nodos y listas enlazadas. Estos ambos hay casi una especie de opuestos el uno del otro. Por lo que hacen cosas diferentes, y te permiten resolver diferentes problemas de diferentes maneras. Pilas y colas que se piensan en un que casi como Cuando estás esperando en fila, hay cosas en cola. Entonces esta persona va, y luego esta persona va, y luego esta persona va, y si la gente entra, todos empiezan a alinearse para que realmente podamos crear eso en un algoritmo, lo que nos ayuda en un montón de situaciones diferentes. Van a ir por encima de los álbumes de inicio. Esta es una especie de línea de base de nuestro contenido en ciencias de la computación. Aquí siempre es donde empieza la gente. Hay un montón de diferentes, y te permite ver una progresión. Iban a ir por algún tipo realmente malo de algoritmos de holograma que tardan demasiado, y vamos a trabajar nuestro camino hasta algunos algoritmos de clasificación realmente buenos que son eficientes pero un poco complejos. Eran ir por encima de los árboles y el árbol de búsqueda binario o el BST. Esos airean dos temas importantes dentro de la informática. Y luego finalmente, vamos a hacer el proyecto. ¿ Fue ese el final del curso? Y el proyecto de producto es esencialmente que vamos a estar tomando todo esto y bajarlo a un solo problema. Hay un problema. Al finalizar el curso, tenemos 10 millones de piezas de datos. Estoy tratando de ordenar esos datos, y quiero que pases por el problema y luego me digas cuánto tiempo tardará en correr. Podrás decírmelo al final de esto y entonces ¿cómo puedes hacerlo más eficiente? Habrá un par de cambios rápidos y fáciles, algunas estructuras de datos. Puedes cambiar cosas así que lo harán más eficiente, y verás que el tiempo va realmente diferente, dependiendo de cómo implementes estos cambios. Entonces esos son nuestros cursos, es lo que vamos a estar aprendiendo. Va a ser un gran viaje. Hay mucho que aprender, y poco a poco comprenderás más sobre el mundo de la informática a medida que lo atravesamos. Gracias a todos, y empecemos con este curso 2. Introducción de la complejidad de tiempo de 1 a 1: Entonces vamos a estar iniciando este curso donde ah comienzan muchos cursos de CS, y eso es en tiempo y complejidad. El motivo por el que empezamos la complejidad del tiempo es porque nos da un estándar, algo con lo que podemos comparar nuestros programas y algo de lo que podemos hablar con otros científicos de la computación. Es una forma en la que pueden, sobre todo los profesores y los que nos enseñan nos pueden comunicar. Por qué un cierto algoritmo de programa, nuestra forma de hacer algo es ineficiente versus otra manera. Por lo que es la forma estándar de comparar diferentes fuera de habitación. A eso es a lo que todo se reduce. Y lo que quiero decir con una forma estándar, es el hecho de que un científico de la computación de digamos, los Países Bajos y de América y de la India todos podrían comunicarse exactamente de la misma manera porque usamos ciertas notaciones como la notación grande O. Entonces, por ejemplo, se vería algo así. Esto es gran notación O, Y así cualquier científico informático entiende lo que esto significa, y más adelante vamos a estar discutiendo eso también y normalmente aprendemos. Utilizas ciertos pequeños aspectos, como en en cuadrado u otros factores escalables. Entonces no estamos usando como si sabes que funciona en 25 unidades tiempo porque no sabemos lo que 25 unidades significan. ¿ Se necesita 25 ciclos de reloj que tardan 25 segundos de la toma? ¿ Se ejecutaría en 25 ciclos en mi computadora verso tu computadora? Es muy difícil comparar cuando vas por eso. Entonces lo que estamos haciendo Estos iban a estar mirando el estándar para esto, una forma que podemos comparar con algoritmos que es completamente independiente de la computadora, que se está ejecutando en la zona, ese mundo, qué tan rápido el La conexión a Internet es sólo poder mirar a dos de ellos y poder compararlos y nos permite descubrir formas en que podemos mejorarnos. Entonces si podemos mirar un cierto tú sabes, una cierta notación, entonces podemos averiguar cómo ser mejor que esa notación y qué cosas son peores que esa notación, y eso nos da mucho margen de maniobra. Nos da la capacidad de mejorarnos un objetivo establecido e investigar en diferentes áreas al igual que cualquier otro aspecto. Cualquier otra ciencia, vamos a estar repasando los fundamentos de esta ciencia y cómo podemos analizarla y tratar de averiguar cómo hacerlo mejor. 3. Refresher: de 1 a 2 Math funciones Logarithmic: la informática se basa en un fundamento de las matemáticas. Básicamente es solo matemática aplicada que arrojas a un procesador y luego lo hace todo por ti. Y ya sabes, puedes seguir construyendo fuera de esto para hacer tus programas. Pero en esencia, es matemáticas, y por eso solo quiero repasar un par de términos matemáticos que se van a utilizar a lo largo del curso. Ahora, no te preocupes. Este no es un curso de teoría matemática pesada como ni nada por el estilo. Ni siquiera va a haber realmente ningún cálculo. No obstante. Vamos a estar haciendo referencia a alguna terminología matemática, alguna nomenclatura matemática, que quería asegurarme de que todos estamos en la misma página antes de avanzar en ese tipo de nomenclatura. Y son sólo algunas cosas que, ya sabes, hemos aprendido tal vez en la preparatoria. O hemos aprendido una o dos veces, y simplemente no usamos realmente en el mundo real. Pero cuando te metes en la informática, se vuelven un poco más prevalentes. Y como dije, no tienes que saber hacerlo todo a mano, sino sólo entenderlos. Eso es lo que quiero llegar al punto de es que puedas entender estas cosas diferentes y donde lo puedes ver como digamos que tenemos un tiempo de ejecución de un algoritmo. Podemos entender lo que significa ese término matemático en relación con el tiempo de ejecución. Y así es en lo que voy a repasar. Esta conferencia sólo está repasando algún material de actualización para que cuando lo volvamos a golpear más adelante en el curso, entenderás a nivel base, y puedes especie de ampliar tus conocimientos un poco más fácil. lo primero que se quiere hablar es de algo que se usa en informática, pero no mucho en otros lugares. Y esa es la idea de log. Entonces aquí mismo se hace referencia, o la nomenclatura para es así. Está basado en registro, algo así como digamos que se basa en de variable aquí o un número es igual a algún otro número. Entonces, por ejemplo, pongamos ocho ahí mismo, y así esta es una función de registro. Ahora, ¿qué es exactamente una función de registro? Bueno, lo que es abreviado es algo conocido como una función rítmica log y una función rítmica log es lo inverso encontrando lo contrario, lo inverso de una función exponencial. Entonces un log es lo inverso de un exponencial. Ahora bien, ¿qué es una función exponencial? Digamos que lo rastreamos a lo largo del tiempo. Seguimos el crecimiento de ambas funciones A lo largo del tiempo. Una función exponencial va un poco algo como esto, donde vas directamente hacia arriba en el aire significa porque después de cada iteración el cambio crece. Entonces, por ejemplo, tal vez de 0 a 1, cambió por uno de 1 a 2. A lo mejor cambió por dos de 2 a 3. A lo mejor cambió por cuatro, luego ocho, luego 16 luego 32 64. Y sigue yendo cada vez más alto y más alto hasta cuando haces uno cambia tus miles de millones o billones de números en movimiento al siguiente. Entonces esa es una función exponencial. Estos son bastante malos en informática. Si estás hablando de tiempos de ejecución porque eso significa que cuantas más cosas le pongas, simplemente sube al infinito de cuánto tiempo va a tardar Now Una función de registro es lo inverso de esto. Es lo contrario de esto, ¿ y cuál sería lo contrario de esto? Bueno, eso es simple. Eso si tomas esto y sabes exactamente lo contrario, así que vamos así en su lugar. Entonces lo que es esto, es que va a tener un gran cambio al principio. Pero con el tiempo, el cambio entre números va a llegar cada vez menos y menos con el tiempo. Entonces donde ésta va casi arriba en una línea vertical recta, ésta va casi hacia una línea horizontal recta. Esto es bueno porque eso significa que cuantas más cosas ponemos en nuestro programa, es casi como si el tiempo de ejecución no estuviera cambiando en absoluto. Se está poniendo cada vez menos y menos hasta que nos está llegando a gustar esa línea horizontal. Y es por eso que las funciones de registro son importantes porque son lo inverso de exponenciales. Y hay algunos algoritmos que se ejecutan en este tipo de tiempo, Así que ese es el lado teórico de la misma. Echemos un vistazo a un par de ejemplos, así que veamos primero. La ecuación para este log de X es igual a nuestro log basado X de por qué es igual a Let's Go b y que, su vez, entra en la función exponencial. Entonces este es un log con mi función. Esta es la función exponencial y la función exponencial es x de B igual. ¿ Por qué? De acuerdo, entonces ensangrémonos algunos números aquí para que salgamos de este tipo de variables abstractas, extrañas y realmente entendemos esto un poco mejor. Entonces si llevamos dos a la B y es igual a ocho, entonces, ¿qué significa esto? Bueno, esto significa que si tomamos dos al algo y si, por ejemplo, lo que estamos diciendo aquí es, por ejemplo, al uno igual 22 a los dos equivale a cuatro. Y eso es porque es sólo demasiado veces para que te lleves 22 veces dos a los tres es igual a ocho. Y eso son sólo dos veces. Dos veces dos estás tomando para multiplicar por sí mismo tres veces equivale a ocho, y así sucesivamente y así sucesivamente. Entonces estamos diciendo es que hay un número ser que existe tal que es igual a ocho. Bueno, por aquí sólo averiguamos eso. Es de dos a los tres igual a ocho. Entonces si enchufamos tres para B, tenemos que a los tres iguales ocho. Este lado equivale a ocho. Esto hace ciclos a. Esa es una buena expresión. Entonces aquí arriba, B es tres. Bueno, ¿cómo nos ayuda esto? ¿ Qué nos dice esto? Bueno, si transformamos esto en una función de registro, en realidad podemos sacar un poco de información de ella. Entonces si obtenemos log of, enchufemos nuestro valor X, nuestra X justo aquí. Entonces es una base larga para. Y entonces ahora enchufemos a nuestros, uh, nuestros escritores B o reales R Y Tanto tiempo, basado dos de ocho. ¿ Qué es eso igual? Bueno, sabemos que es igual a tres. Entonces lo que podemos hacer con la función rítmica log es que en realidad podemos encontrar este número más fácil. Nos confinamos que sea más fácil. Y esto es importante porque con una función rítmica log, podemos enchufar números aquí y podemos conseguir números en el lado derecho donde con una función exponencial, enchufamos números y a la izquierda, y obtenemos números por aquí. Entonces esto nos ayuda porque ahora lo que podemos hacer es que podemos ver la relación de por qué es importante una función de registro. Digamos que tenemos esto o hablemos primero de la base. Entonces, como, ¿por qué? A qué es larga base con base larga 10. El fundamento es justo lo que estamos tomando el número dos. Entonces, por ejemplo, si tendemos a la que tendemos a la a y tendemos a los tres o tendríamos es 10 luego 100 luego 1000 y eso es por esto por aquí tienden a los judíos es 10 veces 10. Así es 110 de los tres es sólo 10 veces 10 veces 10. Es 10 veces tres de sí mismo, así que solo son 1000. Por lo que en esta situación se registraría basado 10 porque el número aquí mismo es un 10 y esto es que no hay importancia esto se puede hacer. Registro basado 27 Log Place 98 Log based 1000 Realmente no importa. Ciencias de la computación. Nos quedamos con el basado en Log, también, y eso lo explicaremos un poco más tarde. Pero sólo se reduce a cómo las computadoras tienen realmente sólo un cero y uno con el que trabajar. Entonces están citando entre comillas dos estados separados aquí, y es por eso que dejamos usar Log base a eso se te pasó por encima de la cabeza. Eso está perfectamente bien. Simplemente entiende que usamos el también. Entonces digamos que teníamos basado desde hace tiempo Digamos que tenemos un algoritmo que se ejecuta en tiempo de registro. Digamos que también hemos basado desde hace tiempo , y esta es la cantidad de información que entra. Entonces digamos que está basado desde hace mucho tiempo. Dos de nosotros tenemos 64. Entonces tal vez tengamos una cuenta de Facebook y estamos ejecutando algún algoritmo en Facebook que pasa por nuestros amigos. Entonces tenemos ¿cuántos amigos en esta situación? Tenemos 64 amigos ¿Y cuánto tiempo va a tardar? Bueno, nuestra ecuación se ejecuta en log, así que completamos ese 60 extranjero, y va a tomar algo de valor por aquí. Y en esta situación, sólo podemos irnos. ¿ Qué será? ¿ Qué es hasta el final que equivale a 64 que sale a ser más o menos dos a la sexta, que es que se puede ver justo aquí abajo. Va a ir 8 16 Así que si vamos al cuarto, van a ser 16 al 5 32 al 6 64 ¿verdad? Al igual que así. Entonces, ¿qué es del 2 al 6? Entonces ahora tenemos a los seis. Y así ahora tenemos por aquí seis. Entonces, en este lado derecho, lo que tenemos es el tiempo de ejecución. Entonces digamos que esto son segundos. Entonces ahora tenemos un algoritmo aquí mismo. Contamos con base de troncos. Dos de 64 piezas de datos equivale a un tiempo de ejecución de seis segundos. Bueno, vamos a hacer que esto vaya. Ah, un poco más en el lado extremo. ¿ Por qué el largo es un algoritmo tan bueno? ¿ Por qué es tan importante en la informática? Bueno, si pudiéramos conseguir un algoritmo que sea así, podemos empezar a ver algunas cosas realmente, realmente aseadas. Entonces sigamos adelante y despejemos un poco de espacio aquí y veamos esto un poco más. Entonces, ¿y si tuviéramos largo de dos de ahora? No lo sé. Uno. Doblemos esto. Entonces 28 Bueno, eso va a igualar siete segundos. Por lo que hemos duplicado la cantidad de información que está llegando, y sólo hemos subido un segundo. Sólo hemos cambiado un poquito. Vamos aún más alto. Digamos que queremos en lugar de duplicar esto o sí, sigamos doblando. Vayamos al 56 aquí mismo y ahora tenemos ocho segundos para que veas que el cambio entre éstos se está haciendo cada vez mayor, pero los segundos sólo van subiendo linealmente. Van por Lee subiendo un segundo cada vez. Vamos a extrapolar esto. Digamos que llevamos dos al no sé, digamos 32. ¿ Y por qué es eso importante? Bueno, a la 32. ¿ Qué es a la 32ª igual? Fue un número muy, muy grande, y ese número pasa a ser de 8 mil 589 mil o 589 millones, 934 mil 592. ¿ Qué tiene de significativo esto? Este es el primer número de esta secuencia que es mayor que la población del planeta . Y si estamos lidiando con Facebook aquí, eso significa que nuestro algoritmo en Max correrá 33 segundos. No irá muy lejos en que no se puede tener más amigos de los que hay gente en el planeta. Entonces simplemente tuvimos esto. Tenemos este increíble algoritmo aquí mismo donde no importa cuántos datos sean. Siempre va a correr 33 segundos o menos ya sean estos milisegundos de aire o estos microsegundos de aire u otro tipo de unidades de tiempo. Esta es una tasa de crecimiento realmente grande. Eso significa que la siguiente versión de esto sería si volviéramos a duplicar esto, por lo que serían 16 mil millones. Entonces tenemos un cambio de un segundo pasando de ocho mil millones hasta 16 mil millones y luego un segundo más para subir a 32 mil millones. Entonces es por eso que los registros son importantes es por esta relación de la que hablamos aquí , cómo no crecen mucho con el tiempo. Y si sigues saliendo al infinito, casi se convierten en una línea horizontal donde puedes poner tantos datos como quieras lanzar y tu algoritmo todavía va a correr básicamente la misma velocidad. Entonces esa es la función rítmica log. Es muy, muy especie de función simple una vez que lo entiendes. Pero sigue siendo bastante raro en el agujero, toda la discusión sobre matemáticas y es algo que realmente no vemos con demasiada frecuencia. Entonces eso es lo primero que quería tipo de tapar justo antes de saltar a ella. Lo siguiente que quiero cubrir es otro que mucha gente ha visto, pero realmente no entienden a nivel base, y eso es algo conocido como factorial 4. Actualización de 1 a 3 Math funciones factoriales: Entonces, ¿qué es exactamente un factorial? Bueno, un poco se veía como algo básico como esto. Faux tres y luego un punto de explicación O tal vez 27 una explicación Punto. Um, ¿qué es exactamente? ¿ Significa un factorial lo que es un factorial? Es justo Si lo desglosas, que sea el número que esté en el spot izquierdo multiplicado por todos los números procediendo. Entonces en este caso, el hecho de tres factoriales va a ser igual a seis. Va a igualar seis, que es una vez 22 veces tres. Por lo que una vez dos equivale a 22 veces tres equivale a seis. Por lo que tres factoriales equivalen a seis. Notarás algo muy importante de esto es que esta tasa de crecimiento es una locura. Entonces si fuimos uno factorial, eso sólo se va a comer uno dos factorial legal una vez 22 Así que es, ya sabes, bastante similar al resto de las tasas de crecimiento. Tres. Fábrica mucho igual seis cuatro factoriales. Entonces tomamos ese seis y lo multiplicamos por un cuatro, que va a ser 24. Entonces en lugar de sólo una vez dos veces tres, tenemos una vez dos veces tres veces cuatro, así que se puede ver que son 24 ahora, cinco factoriales. Vamos a tomar este número, que es este número de aquí multiplicado por cinco. Por lo que sólo podemos hacer unas matemáticas rápidas. ¿ Por qué eso puedes ver que ya estamos sacando el punto en el que vamos a tener que hacer como , um, um, básicamente la mano de matemáticas para que estas cosas se pongan en marcha. Y sólo estamos en el número cinco eran, como con troncos. Podríamos simplemente seguir subiendo y subiendo y subiendo no era demasiado difícil. Seis. Bueno, vamos a pasar por esto por seis. De vez en cuando tenemos 120 así que van a ser 600. Eso me da 720 ahí mismo, ¿verdad? Sí. 720 y se puede ver o 820. Ley No. 7 20 Se puede ver que este número está creciendo en una cantidad sustancial. Cada cambio es cada vez más donde teníamos un cambio de uno justo aquí. Ahora tenemos un cambio de cuatro. Y luego un cambio de, um, aquí abajo tuvimos un cambio de Digamos, vamos a ver 18 aquí. Tuvimos un cambio de 96 aquí. Tuvimos un cambio de 600 se pudo ver que esto se está saliendo de control. Tan factorial ahí algo que nunca queremos encontrar ahí siempre representado por cualquiera como y en, lo que solo significa cualquier número. ¿ Se puede enchufar ahí que solo, como, especie de Si queremos ir genérico, podemos poner una variable en el punto de explicación, o podemos poner un número para obtener una respuesta real. No obstante, esto es lo que es un factorial. Es sólo una multiplicación de cada número procediéndolo Así que como dije, un factorial de un siete es justo o uno son siete. Factorial es sólo una vez dos veces tres veces cuatro veces cinco veces seis veces siete. No hay nada demasiado complicado al respecto. Pero como dije, mucha gente no ve esto, especialmente se les puede ver una o dos veces en clase de matemáticas, pero no de nuevo. En ocasiones hablaremos de factorial es que son algoritmos muy malos. Si tu programa termina en Factorial, pueden tomar Como dije, podrías poner en un programa que quizá sea cuatro factorial y que va a correr muy rápido. Y luego si pones un programa que son, ya sabes, 20 fábricas. Simplemente, ya sabes, 16 piezas más de datos que podría nunca completar. Ya sabes, el tiempo que podría tardar en completar el sol podría quemarse más rápido que eso. Entonces esa es una especie de la importancia de un factorial. 5. Refresher: de 1 a 4 Math expresiones algebraicas: Y luego finalmente, solo quería repasar algún álgebra básico o algunas cosas que podrías ver en el curso. Entonces, por ejemplo, podríamos ver algo como esto, que es N iniciar sesión. Entonces, ¿qué significa esto? Bueno, esto es sólo una especie de función genérica. Es sólo mostrarte lo que una tasa de crecimiento o lo que una función estaba usando en esta situación. Entonces digamos que A es igual a la cantidad de datos, la cantidad de datos. Entonces si tuviéramos una función que es así, todo lo que estamos diciendo es que digamos que nuestra entrada sale a ser 700. No sabemos si va a ser porque, ya sabes, sabes, los programas son dinámicos. Corren en diferentes espacios. En ocasiones una persona podría tener 20 amigos de Facebook. En ocasiones podrían tener 1000. No sabemos cuántos amigos de Facebook van a terminar teniendo. Entonces por eso escribimos algo como esto. Simplemente casi como un marcador de posición. Nos dice lo que vamos a usar cada vez que tengamos este número. Pero antes no sabemos realmente qué es. Este es un principio básico del álgebra, y entonces lo que podemos hacer cuando tenemos una fórmula como esta cuando entendemos el algoritmo, el álbum de computadora o el uso es que una vez que obtenemos un ejemplo concreto, esto es como el abstracto. Esto es algo que aún no sabemos. Podemos enchufar ese ejemplo concreto aquí, y en realidad podemos conseguir un número. Por lo que en esta situación sería 700 veces log de 700. Y digamos que estos base aérea a Vamos con algo que realmente podemos calcular en nuestras cabezas. Digamos que es igual a, um, Vamos con 16 irá un 16. Entonces eso significa que va a ser 16 veces largo, basado dos de 16. Y aprendimos en el último Esto es solo que sale a log de qué? O a la base justo aquí a de lo que equivale a ese 16. Bueno, dos veces cuatro va a igualar 16. Es dos veces dos veces dos veces 22 veces, dos veces dos es igual a ocho. Entonces este es el 48 16. Entonces ahora sabemos que cuatro es la respuesta a esto, por lo que tenemos 16 veces para las que saldrán. Teoh cuatro veces. Entonces van a ser 40 va a ser 64 ¿verdad? Al igual que así. Y entonces eso es lo que tendremos un par de estos. Es decir, se pueden conseguir, ya sabes, se ponen más complicados de lo que podrían estar en cuadrado de log al en tercero o en más para cerrar sesión en más de tres o algo por el estilo. Pero sólo entiende que cada vez que tengas una función como esta, todo lo que significa es que estamos tomando estos dos van a ser el mismo número que ambos son el extremo variable. Entonces ambos van a ser exactamente el mismo número y donde cada vez que obtengamos un número concreto , vamos a enchufar ese número. Creo que eso es bueno. 6. 1-5 N-notation: Por lo que tenemos una buena comprensión de hacia dónde nos dirigimos en esta dependencia. Empecemos a construir ese proceso. Empezar a entender esto un poco más y repasar algo llamado en notación en notación es solo una forma de ver cómo funciona nuestro programa representado como una función de in. Entonces eso es importante aquí mismo. Se representa como una función de en una función de fin. Y entonces lo que esto significa es que vamos a tener un número arbitrario llamado. Entonces, por ejemplo, tenemos justo aquí y ¿en qué está exactamente? Por lo general se juzga por cuántas piezas de datos están siendo procesadas por un programa. Entonces básicamente lo que es un programa es que tienes un montón de entradas aquí mismo, así que llamaremos a estos insumos. Eres un montón de en puntos. Vienen a nuestro programa algo así como una caja negra, si se quiere. Y entonces tienen un montón de salidas aquí mismo. Y así es básicamente como funcionan los programas. Tienes manojo de insumos, se procesan de alguna forma, y luego se almacenan o salen. Ponlo de alguna otra manera. Entonces lo que en es es cuántas entradas estamos obteniendo cuántas veces tenemos que ejecutarlo y en cada proceso. Entonces es básicamente cómo, por ejemplo, en esta situación, es cómo podrían estar los insumos de Maney en cuántos tipos de cálculos necesitamos. Y entonces cuántas salidas salen también podría estar adentro. Entonces es algo que es lo suficientemente arbitrario como para que pueda usarse en cualquier proceso de la ejecución del programa, pero aún así nos permite entender cómo se reaccionaron los programas. Entonces, solo demos un paso atrás y veamos esto de una manera un poco más explícita . Digamos que en esta situación en igual a 100 por lo que ahora realmente tenemos un número aquí. Y así si enchufamos el mental, ya conoces todas estas diferentes versiones por aquí, digamos que esto no está en algoritmo y comparándolo con un algoritmo en cuadrado. Se puede ver que no importa cuál sea este número, este número siempre va a ser mucho, mucho más grande, y en esta situación es mucho más grande, y en realidad es 1000 contra 100. Y la razón por la que no solemos enchufar números explícitamente es porque la cantidad de datos que se están procesando por lo general nunca se garantiza como un número determinado. Por ejemplo, veamos digamos que nuestro programa ingresa la cantidad de amigos de Facebook que tienes. Por lo que nuestro programa ingresa la cantidad de amigos de Facebook que tenemos. Es en poner estos datos en nuestra caja. Pero, ¿cuántos amigos de Facebook tienes? Porque te puedo decir que soy mi número va a ser diferente a tu número. Tu número va a ser diferente a probablemente mucha gente tomando esta clase. Entonces si estamos construyendo un algoritmo para específicamente 250amigos, no va a funcionar para la mayoría de los casos. Entonces lo que hacemos es construir algoritmos que pueden tomar una cantidad arbitraria de datos. Y en esta situación, eso es exactamente lo que en realidad llamamos. Y así se puede tomar en cantidad de datos. Y luego una vez que lo procesa y sale, se va a dar salida en cantidad de datos. Y así con estos, este tipo de clasificación fueron capaces de comparar la de al Berlin sin entender nunca cuántos números van a poner. Y eso es sólo porque aquí estamos viendo órdenes de magnitud. No estamos viendo la diferencia entre 10 y ya sabes, nueve unidades de tiempo o lo que sea. No obstante, sale que estamos mirando en verso en cuadrado. Entonces, por ejemplo, en esta situación, digamos que si ponemos en cantidad de amigos de Facebook que va a llevar en cantidad cuadrada de tiempo. Y ahora entendemos que tal vez si tuviera 10 amigos, esto funcionaría bien y sería solo, ya sabes, saldría a, como, como, ¿qué, 100? Pero, ¿qué pasa si tuviera un 1,000,000 de amigos, entonces cuál saldría a ser ese número? Sería un número absolutamente masivo, y la diferencia de cálculo sería enorme en comparación con si se tratara sólo de una entrada fuera. Y así vamos a echar una especie de vistazo a esto un poco más en profundidad, y se puede ver que hay un montón de maneras diferentes que podemos representar aquí mismo , y esta es una gráfica de su escala a lo largo del tiempo. Y entonces lo que estamos tratando de averiguar es cómo lo hace en escala hacia el infinito? Entonces la razón por la que estamos en cuestión importante es porque, como escala hasta el infinito es la posibilidad de lo que nuestro programa podría ingresar. Entonces no estamos mirando ¿Cómo escala a 100 o 1000 que estamos mirando? Si ponemos un 1.000.000 de piezas de datos o un 1.000.000.000 de datos en esto, ¿cómo va a reaccionar? Y estas gráficas cuentan la historia. Entonces aquí abajo tenemos algo llamado tiempo constante, que es este corchete o esta Ah, columna justo por aquí. Y tan tiempo constante significa que si ponemos el 1110 1 pase lo que pase, siempre va a correr a la misma hora exacta, no hay fin involucrado. Porque pase lo que pase, va a salir exactamente a la misma hora, entonces el de arriba que en realidad es log base to of in. ¿ Recuerdas cuando hablamos del sistema binario? No usamos registro basado 10 como la mayoría de las matemáticas porque no estamos tratando con el sistema de números de decenas . De lo que estamos tratando aquí es el sistema de números de dos. Entonces usamos base larga para y luego por aquí tenemos la raíz cuadrada de in in in log event en cuadrado dos D y en factorial y se puede ver que hay una gran, gran diferencia entre estos dos justo aquí y estos dos justo aquí. Y se puede ver que el ángulo se hace más grande y más grande a medida que esto sube directamente al infinito. Y si realmente sacaste esto, ambos hasta el infinito, esto parecería como si fuera casi recto en el aire. Bueno, esta casa se vería como si estuviera, ya sabes, todavía en el ángulo de 45 grados. Y así es en eso en lo que estamos tratando de enfocarnos. Aquí está, cuando los comparamos, ¿cuánto diferente se van a conseguir con el tiempo? Por ejemplo, esto podría parecer un cambio muy pequeño, pero si ponemos estos números en infinito, empezarás a ver que la diferencia empieza a salir. Entonces echemos un vistazo a un par de ejemplos. Por aquí tenemos el número es cero, um, um, 10 101,000 en igual a 10 1 Así que en esta situación, lo que tenemos aquí es que tenemos el número de la izquierda y luego un algoritmo que corre tiempo de fin y los tiraré que corre en tiempo cuadrado en un algoritmo que se ejecuta en log in time y luego por aquí está el tiempo constante. Entonces si ponemos en una sola pieza de datos, notarás que lo que tenemos es básicamente todos son exactamente iguales y cero no siempre tiene sentido. Por lo que el registro es un poco complicado. En ese sentido , pondrá un cero o indefinido en ocasiones. Pero sólo significa que corre en una sola vez, Así que todos estos son exactamente iguales. Ahora empezamos a escalar más allá de uno. Verías, todos empiezan exactamente en el mismo lugar. Empezamos a escalar más allá de uno en nuestro 10. Entonces, ves, todos están empezando aquí y ahora nos estamos moviendo al 10 que es justo aquí. Empezarás a ver que las diferencias salen, va a apenas 10 en cuadrado, llega a lo más alto de esta tabla a los 100. Por lo que ya hay una gran diferencia aquí. Y luego terminar Log of end se pone hasta alrededor de 33. Ya puedes ver que es justo por ahí Ahora, si subimos una unidad más de Decca a la derecha, digamos que nuestro número está 100 bien adentro. Sube hasta 100 en cuadrado sube hasta 10,000 lo cual es, si pones 100 de estos y los apila encima uno del otro. Es lo grande que se pone el número. Ahí es donde está allá arriba. Entonces esta es una de ellas y hay que poner 100 más de éstas. Entonces esto pasaría por mi techo y luego arriba en el cielo, como probablemente dos o tres pisos recién comparados con los 100 de aquí, que es, ya sabes, justo aquí. Podrías incluso grande en eso en 1000. Y lo que tenemos es en lugar de los 1000 aquí mismo, que nos da así que si solo escalamos esto con el tiempo, probablemente estaría en algún lugar poniendo todo lo grande aquí arriba. Este es un millón, que es si tomaste 1000 de estos y los apilaste uno encima del otro y seguías subiendo al cielo. Entonces esto es como un edificio de 25 pisos. Así que en comparación con como tal vez como aquí, en comparación con una tasa de 25 pisos más, como aquí, tal vez un poco más lejos en esta dirección, comparación con un edificio de 25 pisos. Esa es la diferencia. Y este número sube y sube y sube y sube, sobre todo si consigues unos números realmente grandes, como un 1,000,000 porque entonces éste será un 1,000,000 entonces éste estará en algún lugar , como un par de uno billón o tal vez 100 billones en algún lugar alrededor de esa zona. Y entonces lo que tienes aquí es que tienes una especie de número diferente, y te das cuenta de que estos dos parecen muy, muy similares. Pero cuando comienzas a levantarte en números realmente grandes, la diferencia comienza ahí realmente sale. Entonces verás justo aquí que 10,000 contra 664 y luego un millón contra 9909 165. Hay una diferencia muy, muy grande. Y así que eso es todo lo que estamos tratando de hacer con N es, lo que estamos haciendo es que estamos mirando ecuaciones estaban tratando de saber como y va al infinito . ¿ Qué ecuación es mejor? Y si tenemos una ecuación que está en verso cuadrado, una ecuación que está en, entendemos que ésta va a ser sustancialmente mejor, más eficiente que ésta, y así que yo sólo como que quería repasar si tú no entendía qué registro era realmente rápido. Qué log es Y eso es, por ejemplo, tenemos una gráfica exponencial. Esto es como en cuadrado justo aquí. Por lo que arranca cero. Y luego con el tiempo, su ritmo de cambio sube mawr y mawr y más hasta que es casi una línea recta. Entonces esto de aquí está en cuadrado. Lo que es una gráfica de leyes es que es exactamente lo contrario de eso. Entonces surge realmente rápido, y luego se pasa y casi se convierte en una línea recta con el tiempo. Y, ya sabes, tenemos nuestros ejes aquí mismo. Lo mismo para por aquí. Tenemos algunos ejes, pero básicamente la razón de esto es porque log es lo inverso de un exponencial. Entonces con el tiempo, donde esta la tasa de cambio. Entonces estas pendiente de ella a k cuánto va de aquí a aquí versus aquí para escuchar esto se va a hacer más grande y más grande y más grande hasta que casi va directo al aire mientras que este de aquí se está haciendo más pequeño y más pequeño y más pequeño tiempo. Entonces eso significa que si ponemos este a, ya sabes, un 1,000,000 Cada vez que sube uno este número podría crecer en un mil 000.000.000 o un billón. Bueno, en este caso, una vez que lleguemos al número realmente, realmente grande, podríamos estar yendo de 8.1 a 8.0 05 Ya sabes, algo así, donde el cambio va a ser extremadamente diminuto, y así es como funciona el log. Simplemente piénsalo como el inverso de una función exponencial y notarás que en realidad hay un pequeño tipo de cosa ordenada que sale. Ese entendimiento es que si volvemos a la gráfica aquí, puedes notar que tenemos registro de fin y en tiempo constante y porque éste con el tiempo casi se convierte en una línea recta donde sólo nos estamos moviendo, ya sabes, tal vez 10.1 decimal. Todo el mundo a través de iniciar sesión y temporizador constante en realidad generalmente trataban uno de la misma porque, como dije ahí, su tasa de cambio se ralentiza donde estos ángulos en realidad no lo cambian mucho todo. Donde en lo contrario sucede con en cuadrado a medida que vamos cada vez más lejos y más lejos, el ángulo empieza a cambiar hacia arriba en un punto donde es casi un cambio de 90 grados porque simplemente va recto en el aire. Entonces solo quería explicar que si no entendías lo que significaba un registro, es lo inverso de un exponencial. Y así cuando vamos al infinito, tenemos que pensar en alguna otra una idea diferente. Y ese es el hecho de que si te das cuenta y de que no estábamos hablando, ¿cuál es la diferencia entre dos en verso en? Y eso se debe a que la constante el número al frente no importa. ¿ Por qué no importa? Echemos un vistazo aquí arriba. Entonces lo que tenemos es que tenemos en cuadrado y tenemos que en cuadrado. Y a medida que te haces más grande y más grande, la diferencia entre estos dos comienza a disminuir, donde el número el cambio en él no es tan significativo como solía ser. Y esto todo tipo de bajan fracciones de Teoh y, ya sabes, una especie de números como este. Pero lo que estamos tratando de ver aquí mismo es que comparamos con cosas que no estaban tratando de comparar es un extremo cuadrado adverso y en cuadrado. Mejor porque sabemos que ambos son inherentemente probablemente bastante malos. Lo que estamos tratando de comparar es Es esto en cuadrado Mejor versus un fin. Entonces en esta situación notarás que no importa qué número pongamos frente a aquí, todavía va a ser sustancialmente mayor que este número de aquí. Y así no importa qué constante tengamos al frente Cuando va al infinito, la constante no importa, y sólo miramos a la variable misma, aunque sepa que esto es un poco confuso. Aunque tengamos un 1,000,000 en verso en cuadrado, en cuadrado, seguirá siendo el peor de los casos. Y como dije, esto es un poco confuso al principio solo para envolver realmente la cabeza. Pero todo se reduce al infinito, y el infinito es un número al que nunca se puede alcanzar por lo grande que es una vez que llegamos a ir al infinito. Una vez que lleguemos a un infinito cercano, la constante no significará nada porque este número aún superará a un 1.000.000 veces en él seguirá superando a mil 000.000.000 el billón de veces en algún momento. Entonces tienes que pensar realmente teórico aquí, pero todo se reduce a esta simple regla. Si lo sabes, si no puedes meter la cabeza en torno a la teoría, solo piensa en esta regla civil. Si hay un número al frente, deshazlo. No importa en nuestras comparaciones. Entonces ahora hagamos un ejemplo aquí mismo. Vamos a divertirnos un poco. Y vamos a crear una especie de ejemplo donde realmente podamos ver esto en un aspecto del mundo real . Entonces si cada ciclo de un programa toma 0.1 segundos Así que en esta situación, lo que estamos viendo es nuestro cada ciclo de un programa así están en es que ya sabes, cuando hicimos esa caja están en esta situación es los ciclos y lado o algún tipo de cosa dentro de esta caja, ese es nuestro dentro. Por lo que cada ciclo de un programa tarda 0.1 segundos. ¿ Cuánto más rápido se ejecutará el programa ejecutándose en inicio de sesión que un programa que se ejecuta en cuadrado? Si llegan 1000 piezas de datos y así es realmente donde llega donde realmente se puede ver la diferencia. Entonces, solo pasemos por esto. Tenemos 1000 piezas de datos que vienen a través. Se trata de N iniciar sesión, lo que equivale a que reemplazamos nuestros extremos por lo que están en tarifa se dio aquí. Por lo que son 1000 piezas de datos, que es la que tomará 1000 ciclos de calcetín. Entonces en esta situación, nuestro en es igual a 1000. Por lo que ahora podemos hacer las matemáticas detrás de ella. Nosotros decimos que va a tomar 1000 veces log de 1000 y eso nos va a dar 3000 veces 30000.1 que a su vez nos da 30 segundos. Ahora, vamos a comparar eso con en Squared, que va a ser 1000 a la segunda, equivale a un millón de veces 0.1 segundos porque cada ciclo de reloj toma 0.1 2da Así que por eso nos estamos multiplicando al final ahí. Y lo que obtenemos son dos horas y 46 minutos. Entonces debido a que esos programas lo ejecuta en cuadrado en lugar de en, inicia sesión. Y volvamos a nuestra gráfica aquí mismo y echemos un vistazo. Recuerda, estos dos se veían bastante cerca el uno del otro, pero no lo son. Entonces volvamos a nuestra gráfica nuestro ejemplo aquí porque corrió en cuadrado. Va a tardar dos horas y 46 minutos, o dos horas, 45 minutos más que este de aquí. Y llevemos esto a un número aún mayor. Digamos que tiene en el registro de en tan de 25,000 EU ahí en igual a 25,000 aquí mismo. Por lo que en igual 25.000. Ahora realmente empezarás a ver la diferencia. Entonces en esta situación en Logan equivale a 25,000 veces log de 25,000 que va a águila en algún lugar alrededor de 109,948 veces 0.1 Así que va a igualar a la derecha alrededor de 18 minutos y 32 segundos. Pero echemos un vistazo al final de cuadrado. Por lo que esta lista, ya sabes, se ve larga y mirando hacia otro lado más de 30 segundos. También notamos que es mucho menos que hasta 24,000 menos datos 300.7 al cuadrado. Si vamos a terminar al cuadrado, son 25,000 cuadrados, que Águilas 625 millones veces 0.1 que águilas seis millones, 250,000 segundos, que son 72 días. Por lo que se puede ver que este número realmente empieza a despegar justo por aquí. Y sólo estamos en 25 mil piezas de datos. Hay cuántas personas en Facebook en este momento, Y sus datos hay algoritmos probablemente tienen que correr con cuántas personas hay en Facebook. Entonces imagínate si trataras de poner el uno era que creo que tal vez mil millones cantidad de personas ahí ahora mismo a través de este programa tomaría esto subiría a los miles de millones de años que nunca terminaría. Y así es aquí donde se puede ver como la diferencia de los extremos. Y así, básicamente, todo esto es sólo tratar de reducirse a un par de hechos clave. Fin son sólo cuatro comparaciones. Entonces esa es una especie de nuestro primer hecho está en es sólo para comparar dos programas. Es para comprobar el tiempo de ejecución de dos programas. No es para uso práctico, lo que significa que no vamos a estar corriendo en algoritmo en un, ya sabes, un programa y ver si puede devolver cosas dentro, ya sabes, 20 segundos o algo así como eso. No podemos hacer eso dentro. Y la razón de eso está en es solo un estándar es una forma en que podemos ver un programa una independiente apagado si la computadora es rápida o lenta, donde la conexión a Internet es más rápida, lenta Podemos compararla con otro programa, como en cuadrado o en Iniciar sesión, y podríamos empezar a entender qué algoritmos son los mejores y cuáles no escalarían correctamente. También tenemos que entender que no está mal tener números más grandes. A veces es inevitable. Entonces no solo pienses que ya sabes, la idea de una ciencias de la computación es nunca volver a encontrar en cuadrado. No se supone que use con fines prácticos que estamos tratando de hacer es que estamos tratando resolver teóricamente diferentes problemas. Y así, por ejemplo, todas las espadas de comparación no pueden hacer mejor que en iniciar sesión. Entonces volvemos a este gráfico aquí mismo. Ya verás que todos los tipos de comparación caen en esta línea, así que están ahí en algún lugar de este lado. No están en el resto de esto más fácil, tipos de gráficos y de comparación más rápido son como te gustaría, gustaría, ordenar un montón de números así que incluso como el uso diario, especie de algoritmos aún caen en el inicio de sesión. Además, los múltiplos caen mientras comparan así que entienda de nuevo en esta lección que los múltiplos no importan y luego es exponencial puede ser realmente, realmente peligroso con el tiempo. Y nuestros cerebros realmente no tienen la capacidad de entender las diferencias. Y simplemente te muestra en este donde no pensaríamos que esto sería de 72 días versículo 18 minutos. Sólo porque pasamos de esta gráfica a esta gráfica pero las horas extras exponenciales son realmente, realmente, muy fuertes. 7. Notación de 1 a 6 grandes: Entonces ahora tenemos una buena comprensión de en y cómo funciona exactamente, y se vincula a nuestro análisis de algoritmos. Podemos empezar tipo de sumar a eso. Entonces sabemos que en es una forma de clasificar qué tan rápido en exterior corren, dado cierto número en ¿Cuánto tiempo se va a tomar con respecto a ese número? Entonces, ¿se va a llevar justo a tiempo? Entonces si lo fue, 1000 va a igualar 1000 o va a tomar algo así como en tiempos cuadrados donde cuando es 1000 va a igualar? UM, un millón, y este es un tipo de clasificaciones realmente importante. No obstante, los programas no son tan fáciles. No sólo corren a una hora exacta todo el tiempo. Muchas veces han abundado. Entonces, por ejemplo, tal vez no cargarías. Se va a ejecutar y en cuadrado, pero ejecuta un fin, y en él, ya sabes que exporta en log in y así tenemos que poder ver esto, y hay que mirar el programa y dar una clasificación sobre el programa en su conjunto. Entonces, por ejemplo, este programa, siempre miraríamos el peor de los casos es siempre ir de pie. peor de los casos toma al cuadrado, sin embargo, a ciertos pasos va a correr más rápido. Y por eso, en realidad tenemos este tipo de sistema aquí mismo, que va a clasificar los, um, los límites en nuestra notación. Entonces, solo bajemos esto y echemos un vistazo a esto. Estos de aquí arriba se llaman omicron. Te has desvanecido en el medio y luego omega, y esto es minúscula de mega aquí abajo y así puedes ver que son alfabeto griego. Pero sólo muchas veces en el griego de Matthew porque el alfabeto se vuelve confuso. Entonces usamos el dedo del pie griego, especie de representar simbólicamente las cosas, y en esta instancia, abundan todos estos símbolos griegos simbólicamente. Entonces lo que tienes aquí es dibujar, por ejemplo, por ejemplo, un encuadernado justo en el medio aquí y aquí arriba es más rápido, así que diremos aquí arriba va a ser más rápido y abajo aquí va a ser más lento. Entonces nuestra primera notación es poco. Ah, y se puede ver que simplemente no nos gusta decir omicron como gran notación omicron que sólo toma mucho. Entonces solo decimos el pequeño Oh, grande oh, y tan pequeño Oh, justo aquí. Simplemente significa que va a ser más rápido, que significa que el programa siempre será más rápido que este encuadernado. Entonces, por ejemplo, si nuestro Barón estuviera en cuadrado justo aquí, si tuviéramos poco, oh, de en cuadrado justo aquí, veríamos que significa que nunca va a tocar y al cuadrado. En realidad siempre va a ser más rápido que en cuadrado, así que siempre va a estar justo por encima de esta línea, pero más rápido que en cuadrado. Y entonces lo que podemos hacer es que en realidad podemos usar esto para averiguar el rebote. Entonces el siguiente que tenemos es que tenemos grande Oh, y Big O significa que va a ser más rápido, tu igual a. Entonces eso significa que va a tocar esta línea o ser más rápido, así que va a ser en el peor de los casos, y eso es algo que es muy clave aquí. Esto significa, en el peor de los casos, que va a estar en cuadrado. El siguiente que tenemos son datos, lo que significa que no va a tocar ninguno de estos dos. No se va a bajar. No se va a subir. Lo que se va a ir está justo en esta línea. Entonces no importa lo que vaya a ser en cuadrado, va a estar justo a lo largo de esta línea en alguna parte. Y entonces el siguiente abajo que tenemos es más lento o igual a lo que tenemos. Este es Omega, y éste es más lento igual a por lo que toca esta línea y siempre es más lento. Entonces, ya sabes, nos metimos como en tercero en cuarto aquí abajo, aquí arriba podríamos tener como dentro. Por lo que siempre es más lento que esto, o igual a n cuadrado. Entonces en el mejor de los casos, Así que este es en el mejor de los casos, va a correr a esto si pones esto. Entonces, por ejemplo, si tenemos derecho de n cuadrado, como así cortamos un poco justo ahí pero de en Cuadrado como así entonces entendemos que este programa siempre se ejecutará, o en el mejor de los casos se ejecutará es en al cuadrado, lo que significa que puede correr peor que eso, y luego por debajo de eso tenemos más lento de lo que significa que siempre va a correr peor que en cuadrados. Poco nunca tocan y cuadrada, pero correrá peor que en cuadrado ¿Y entonces por qué es esto importante? ¿ Por qué queremos enfocarnos en este de todas estas? Y eso es porque Big O dicta el peor escenario de casos y nos preocupa el peor escenario de casos porque dada la probabilidad y las estadísticas son, programa podría tocar el peor escenario de casos en un momento y queremos saber, sin duda, ¿cuál es ese peor escenario? Entonces por eso usamos el grande Oh, es ver en lo peor. ¿ Qué va a ser? Y ya puedes ver que voy a volver a subir 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 una especie de llenado de este fin. Entonces si tenemos, por ejemplo, um, um, tal vez big o of in. Entendemos que en el peor de los casos, va a estar adentro por lo que podría estar dentro. 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 de este lado de la línea. Siempre va a ir de este lado, y eso es realmente poderoso porque ahora podemos empezar a comparar programas, peores casos, y podemos empezar a ver que puede ser cuando un programa escala el por ejemplo, Si tuviéramos una en iniciar sesión programa versus un en programa, pudimos ver que cuando éste escala, va a ser peor que éste. Así que tomemos, uh, uh, vamos a descomponer esto un poco y podemos ver por qué algunas de estas no tienen sentido . Entonces tenemos un programa que corre ese pequeño oh en cuadrado, que significa que es más rápido que en cuadrado. Entonces eso significa que podría estar en cualquier lugar desde en cuadrado todo el camino hasta básicamente como simplemente más rápido que él. Por lo que no va a ser en cuadrado, pero podría ser cualquier cosa más rápida que en cuadrado. Y este es algo así como grande Oh, pero la cosa es, nos importa lo que nos dan, así que es un poco oh de adentro. En realidad no podemos tocar esto, así que simplemente lo hace un poco confuso. Nos da un atado, pero no lo hace fácil. para que lo veamos. No podemos inmediatamente mirar esto y irnos, Oh, esto va a correr a tiempo. Podemos mirarlo. Tenemos que mirar esto y ser como, Oh, va a correr más rápido que el final. Pero realmente no sabemos dónde, y en realidad no nos da mucho espacio para moverse. Y entonces tenemos nuestra gran notación O y eso es lo que acabamos de pasar es que podemos mirar esto y estaremos como, Oh, Oh, en el peor de los casos, se va a correr en largo en Fada sería genial si siempre pudiéramos usar datos. ¿ Cuál es el? Esto es igual o a veces se usa como el promedio, pero la mayoría del tiempo que significa igual a fin, Así que esto sería genial. Pero el problema es que los programas no siempre se ejecutan exactamente a lo largo de la línea. A veces podrían correr, ya sabes, tal vez en una parte corre un fin. Pero en un momento se ejecuta, inicia sesión y va a cualquier lugar en el medio. Este dato es simplemente demasiado específico para nosotros, todavía realmente como. Y entonces estos no tienen sentido porque no nos dan mucha información . Piénsalo, Este de aquí, que es Omega Tan omega en cuadrado. Eso significa que va a ser más lento o igual a omega al cuadrado, que es como estás diciendo que nuestro programa va a estar o ejecutándolo en cuadrado o va a ser más lento. ¿ Cómo se supone que vamos a planear con eso en mente? Porque más lento podría entrar al infinito. Podría ser lo más lento posible, y nunca podríamos prepararnos para eso porque nunca habríamos abundado. Sería como, De acuerdo, así que sólo va a correr a lo rápido que podría tomar en cuadrado. Podría tomar en factorial. Podría llevar a fin el infinito. No nos ayuda a analizar el programa porque hay lado infinito al mismo. Y exactamente la misma idea con la, um, pequeña Omega aquí también es que se va hacia el infinito por el lado malo, lo que no nos ayuda. Entonces estos nos ayudan porque el lado malo es dejarme borrar 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í se va al infinito. Nos da un atado así que cualquier cosa va a estar en el peor aquí mismo. Pero podría ser mejor y no nos importa como si vuelve y corre esa constante, eso está bien. Eso está perfectamente bien. Eso significa que nuestros programas en una gran camisa, pero podemos planear para eso. Simplemente significa que nuestros programas pasando, ya sabes, se ejecutan más rápido de lo que esperábamos. Entonces lo que podríamos hacer entonces es simplemente 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 por eso Big Oh es tan importante es que es lo más útil de todas estas notaciones . Nos da un peor escenario, y así es como tomar un ejemplo de cómo podríamos aplicar esto a un problema en particular. Entonces generalmente lo que siempre haces es usar el peor escenario, significa en qué momento del programa no va a ser el más ineficiente. Entonces aquí, por ejemplo, digamos que teníamos grande o de en cuadrado. Teníamos un gran, uh in log in big O of in, y luego grande O de Constant time, y así estas de aquí abajo son geniales. Pero la cosa es, es que pase lo que pase, siempre vamos a ser embotellados por este tipo de aquí. Y eso se debe a que nuestra tasa de tiempo de carga aquí arriba está en cuadrado, lo que significa que este programa lo va a ejecutar en cuadrado más en inicio de sesión más en más O dos, el primero, que hace mantenerlo una especie de constante. Aquí iremos más uno. Y podrías estar pensando: ¿Por qué estoy haciendo esto? Y eso es porque en realidad se puede agregar cada parte de los pasos juntos. Entonces porque haces esta parte, entonces haces esta parte. Después haces esta parte, luego haces esta parte para que realmente puedas agregarlas todas juntas. Recuerda lo que estamos haciendo de antemano cuando estamos hablando de cómo estos cómo tratamos de mirar un programa a medida que va al infinito. Entonces si nos fijamos en este número, cuál de éstos va a superar a los demás cuando vayamos al infinito? Bueno, por ejemplo, pongámoslo en un 1,000,000. Cuán significativo es un millón, que está en lo correcto uno va a ser verso un millón va a ser verso. Tal vez en algún lugar alrededor de tres millones va a ser verso uno cuadrillón o tal vez un billón 60 se sienta fue uno y 12 ceros. Este va a ser sustancialmente más grande. Estos van a ser una porción cada vez más pequeña del número ya que va al infinito hasta el punto donde éstos se acercarán a cero como significancia. Entonces empezarás a tener, ya sabes, un número de Google, que es de 100 ceros más quizá, como ocho millones por aquí, algo así. Y eso significa que esta parte de aquí es completamente insignificante en este punto. Entonces lo que hacemos es eliminar a los más bajos, y el tiempo de ejecución de este programa está en cuadrado. Y así vamos a sólo una especie de cemento que con otro ejemplo aquí, digamos que teníamos Big O. Así que tuvimos una gran O de en cuadrado grande O de En Cuadrado Big O de Petróleos aquí Vigo de In Squared otra vez. Y veamos ahora tenemos gran O de fin del tercero. Y así ahora lo que tenemos aquí es que tenemos n cuadrada plus en cuadrada plus en cuadrada plus en el tercero, y así podemos realmente combinar estos abajo a tres y cuadrado plus en el tercero. Y ahora recuerden de lo que hablamos en la última conferencia sobre el en notación. Estos no importan. El constante aquí mismo no importa. Porque a medida que nos adentramos en el infinito, esto se vuelve cada vez menos significativo. Hasta que una vez lleguemos a un número suficientemente alto, se convierte básicamente en cero para que podamos tachar ese. Y así ahora tenemos en cuadrado plus en el tercero. Y entonces, por supuesto, este va a despegar mucho más alto que el otro programa Una llaga acaba por estar en tercer lugar. Y ahora, como esas son todas grandes oh, notaciones que conocemos en el peor de los casos, nuestro programa lo ejecutará en tercero, que ahora estamos. Tenemos este límite de en tercero y el infinito de tiempo de ejecución se va de esta manera, y ahora podemos planear que en el peor de los casos vamos a tener en el tercero. Y podemos planear todo el camino de regreso al tiempo constante, porque ahora todo lo que tenemos es justo aquí. Entendemos que, ya sabes, si ponemos una pieza de 1 millón de datos, podría no funcionar. A lo mejor podemos buscar traer esto, pero nos da algún lugar para empezar. Nos da algún lugar para compararlo con otros. Entonces esa es una gran notación O. Muy importante. Y con el tiempo vas a empezar. Básicamente, esto se convertirá en segunda naturaleza. Tan solo poder mirar esto. En realidad, nunca verás a estos otros. Demasiado a menudo. Verás éste. A veces. Si dice como un cierto punto de un programa es igual a este tiempo de ejecución, entonces verás este. Pero aparte de esa tesis, probablemente nunca verás y probablemente nunca verás al pequeño Omar Khan a. Entonces estas notaciones de aquí solo las memorizaron, entienden lo que significan, y deberías estar bien para ir. Empezarás a entender mucho más de especie de documentos de informática. 8. Ejemplo de gran mundo de 1 a 7 real: no lo es. Hemos aprendido mucha teoría. Sigamos adelante y tomemos un revés y repasemos algún análisis de código del mundo real. Ahora bien, no voy a usar código complejo o cualquier tipo de código que necesites conocer aquí mismo. Todo es pseudo código, y voy a estar explicándolo. Cada paso del camino es si nunca has tocado código antes porque así es como quiero explicarlo. Todo este tipo, por supuesto, es que estamos viendo la teoría detrás de todo. No el código, sin embargo, aplicarlo a algo riel mundo puede ayudar, ya sabes, una especie de averiguar algunos de los conceptos, y por eso lo estamos haciendo. Entonces, solo echemos un vistazo a nuestra primera pieza de código. Voy a seguir adelante y caminar por esto por aquí. Entonces lo que tenemos es que lo tenemos dice lo escribí en pseudo. Esa clase de simplemente lee de la lengua, algo que puedes mirar y entender lo que está pasando. Por lo que dice para cada dato en la lista de datos, por lo que crearemos una lista de datos aquí en una segunda impresión. Datos a pantalla OK es suficiente. Digamos que introdujimos en esto un pedazo de datos una lista aquí que tal vez sea de tres a 10 y luego simplemente iría búfalo. Por lo que se trata de tres enteros y una cadena. Es así como sería técnicamente clasificado. Pero ni siquiera vamos a ver eso. Se trata de cuatro piezas de datos. Y entonces lo que estamos diciendo es que por cada dato, Así que por cada dato de nuestra lista, vamos a, um, imprimir esos datos en la pantalla. Entonces en nuestra situación aquí, ¿en qué hay? Bueno, en esta situación aquí mismo en iguales, el 1234 Porque tenemos cuatro piezas de datos. Entonces en esta situación en igual a cuatro Así que ahora veamos cuál sería el tiempo de ejecución de esto. Por lo que tenemos para cada pieza de datos y luego imprimimos en la pantalla. Entonces bien, vamos a bajar la lista. Aquí. Vámonos ahí. Primera pieza de datos. Por lo que nuestra primera pieza de datos es de tres. Agarramos tres de nuestra tasa de documentos aquí, Así que este es el número cero. Una matriz, o, si quieres pensarlo, es 1234 Los ordenadores suelen ir con 0123 es justo la forma en que funcionan. Entonces vamos a agarrar nuestra primera pieza de datos aquí y luego vamos a imprimir a la pantalla. Por lo que agarramos a nuestros tres que imprimimos en la pantalla. Entonces ese es un tiempo de ejecución. Así son el tiempo de ejecución en este momento es uno. Y entonces ahora vamos a agarrar el a porque vamos a bajar la lista. Por lo que para cada pieza de datos, hemos tocado este. Por lo que ahora pasamos a este. Por lo que ahora agarramos dos e imprimimos en la pantalla. Entonces ahora nuestra pantalla se ve así. Y así que eso es tiempo de ejecución adicional justo ahí. Eso es un tiempo de ejecución. Y entonces ahora imprimimos nuestra siguiente pieza de datos, que es 10. Por lo que ahora tenemos 32 10. Eso es tiempo de ejecución adicional justo ahí. Y entonces ahora imprimimos búfalo, que sería de 3 a 10 búfalo. Al igual Y ese es un tiempo de ejecución adicional porque todo lo que estamos haciendo es agarrar la pieza de datos y lo estamos imprimiendo. No hay un proceso de pensamiento especial entrando aquí sólo fueron agarrar, imprimir, agarrar, imprimir, agarrar, imprimir. Y ahora si sumamos todo esto, veremos que sale a uno más uno más uno más uno más uno, que equivale a cuatro y así lo son el 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 fin aquí mismo. Y si solo podemos pensar en esto teóricamente por un segundo, si tuviéramos un 1,000,000 de piezas de datos aquí, no habría, en ningún momento el programa en el que alguna vez tendríamos que tocar más de un 1,000,000 de piezas de datos . Entonces no importa lo que hagamos aquí son tiempo de ejecución va a ser cualquiera que sea nuestro fin, que significa que lo que tenemos aquí es un tiempo de ejecución de en esta situación particular, realidad podríamos usar a Fada como en porque en realidad es igual a terminar. No hay ningún tipo de, uh, espacio de meneo aquí, pero vamos a seguir adelante y sólo decir que va a peor, porque esa es la notación que nos gusta usar. Entonces este es un ejemplo de un en el que esto se llama un bucle for. Por lo que cuatro bucles son típicamente, por ejemplo, horno final en una situación. Vayamos a un problema un poco más complejo aquí. Entonces déjenme desglosar este también Lo que tenemos aquí es que dice para cada dato en una lista de datos. Entonces eso significa que en vez de llamarlo papá y ahí fuera, cada pieza de datos de una lista va a estar en jaque si los datos están en la lista. Entonces vamos a ir después por cada dato W en las listas de datos. Si n es igual a w print. Cierto. Entonces vamos a seguir adelante y una especie de derribar este un poco también. Vamos con nuestro mismo ejemplo de antes, que era tres coma, dos coma, 10 coma búfalo como así. Y en esta situación, nuestro en sigue siendo igual a cuatro. Y entonces ahora lo que vamos a hacer es que vamos a ver el primer problema aquí, Así que echemos un vistazo ahora mismo. Digamos que vamos a agarrar del pie cada una de estas piezas de datos, así que vamos a agarrar los tres y eso ya está dentro. Y entonces ahora, por cada pieza de datos en esta lista de datos y se puede ver estos nombres son exactamente los mismos. Entonces eso significa que esta es la lista de datos. Estamos revisando los dos, así que tenemos nuestro tres camino tenemos a nuestros tres agarrados. Y ahora estamos tratando de comprobar si estos tres de aquí es equivalente a algo aquí arriba, y la única forma en que podemos hacerlo es citar la fuerza bruta sin comillas. Entonces vamos a llevarnos estos tres. Vamos a revisarlo con el 1er 1 Vamos a revisarlo con el 2do 1 Vamos a revisarlo con el 3ro 1 Vamos a revisarlo con el 4to 1 Así que van a ser 1234 operaciones . Entonces primero, vamos a romper esto, como, realmente muy lejos aquí abajo. Tenemos a nuestros tres. Hemos agarrado a nuestros tres, y ahora lo estamos revisando. ¿ Es igual? Déjame hacer eso un poco más pequeño va a ser un poco más grande de una gráfica. Entonces estamos diciendo, ¿tres iguala la primera pieza de nuestros datos, que va a ser la tres otra vez? Porque no le dijimos que empezara con un número que no lo es o cualquier cosa elegante como esa . Solo estamos revisando esta lista por segunda vez. Entonces tenemos a nuestros tres y estamos revisando. No es igual al 1er 1 Así que igual a tres. Sí, sí lo hace. Entonces esto es esto imprimirá un verdadero mensaje, y esto tomó una operación. Ahora sí lo hace. Son tres iguales a no lo hace. Entonces no imprimimos nada. Esa es una operación. ¿ Nuestros tres equivalen a 10? No lo hace. Entonces esa es una operación. ¿ Son nuestros tres búfalos iguales? No lo hace. Entonces esa es una operación, y ahora terminamos con los treses. Por lo que hemos pasado. Nos hemos encargado de los treses, así que vamos a crear un 2do 1 aquí abajo. Veamos esto. ¿ Qué? Va a ser el que estamos revisando con su exactamente lo mismo. Pero solo quiero hacer que esto sea un poco más visual para todos ustedes. Entonces terminamos con treses. Entonces pasemos a los dos ahora. lo hace demasiado igual. Tres. No lo hace. Esa es una Operación hace para igualar a ella hace. Esa es una operación hace para igualar 10. No lo hace. Eso es lo que hace la operación para igualar búfalo. No lo hace. Esa es una operación, y luego vamos a bajar la lista. Uno más hace 10 igual tres No eso es uno Operación hace 10 igual a no eso es lo que hace la operación. 10. Igual 10. Sí lo hace. Ahí es cuando la operación hace 10 igual a Buffalo. No lo hace. Esa es una operación lo hace Buffalo. Simplemente lo voy a abreviar como estar aquí, así que quiero seguir escribiendo. Buffalo. ¿ Búfalo es igual a tres? No lo hace. Entonces esa es una operación que sí. Búfalo igual a ella no lo hace. Entonces esa es una operación. ¿ Es igual Buffalo? 10? No lo hace. Entonces esa es una operación. ¿ Búfalo iguala a Buffalo? Sí lo hace. Entonces esa es una operación. Y ahora si sumamos todos estos aquí mismo, lo que vamos a ver es que esto va a ser 123456789 10 11 12 13 14 15 16. Entonces en esta situación, nuestro en fue de cuatro, pero son tiempo de ejecución fue aproximadamente 16. ¿ Y qué sale a ser eso? Bueno, eso sale a estar en cuadrado. Entonces digamos que si tomamos cuatro y lo cuadramos, equivaldría a 16. Y teóricamente podemos pensar en esto también. Si ampliamos esto a cinco, cada uno tendría no sólo cinco más aquí, sino que tenemos que multiplicarlo porque ahora tenemos que revisar uno adicional también. lo que cada instancia individual, tendrá cinco y tendrá un otro cinco entero, que lo cuadra por lo que en esta situación son runtime está en cuadrado. Y la razón de esto es a pesar de que tenemos 24 bucles, existe lo que se conoce como anidación. Hemos anidado 14 bucle dentro de otro bucle de cuatro. Entonces esta parte de aquí afuera, dibujemos esto y leamos esta parte aquí afuera está adentro mientras esta parte adentro también está dentro. Entonces lo que hacemos es tomar el final por fuera, lo multiplicamos por el final, dentro, y nos metemos al cuadrado. Y así será nuestro último tiempo de ejecución para esta situación. Entonces, como dije, este curso no está fuertemente designado en escribir código o hacia afuera, y todavía se define la teoría. Pero pensé que esto podría ayudar a mostrarte de lo que hemos estado hablando todo este tiempo. Cómo se podría analizar realmente el código para que podamos entender estas diferentes piezas. Y se puede ver que pase lo que pase, en realidad acabamos de aprender algo muy importante. Siempre van a estar cuatro bucles, pero anidados para bucles siempre van a ser por muchos anidados que haya. Entonces si este de aquí anidó 1/3 1 esto sería una fórmula en cuadrado, y se empieza a subir en números realmente grandes para empezar a revisar todas estas cosas. Por lo que espero que el este ejemplo práctico te haya ayudado a entender un poco mejor este concepto . 9. 2-1 de cómo se guardan datos: Entonces, empecemos a saltar a uno de los próximos temas principales de la informática, y esa es la capacidad de entender y manipular las estructuras de datos. Las estructuras de datos son la forma de tomar datos básicamente, organizarlos y poder agarrar el acceso, guardarlos de ciertas maneras que encajan con nuestro objetivo. Por lo que algunos son más rápidos que otros en ciertos aspectos. Entonces, por ejemplo, algunos de ellos vamos a ocupar más espacio mientras somos de acceso realmente, muy rápido. Algunos de ellos no ocuparán mucho espacio en absoluto, pero podría tardar un poco en acceder. Algunos de ellos tienen inserciones más rápidas. Algunos de ellos tienen más rápido remover ALS. Todo se reduce a lo que exactamente quieres lograr en tu programa o teoría o cualquier tipo de sección de informática en la que estés entrando. Entonces lo primero que pensamos antes de entrar en esas estructuras de datos, es que necesitamos entender cómo, exactamente se almacenan los datos, porque eso nos ayudará a empezar a entender estas estructuras de datos y por qué uno podría tomar más largo que el otro y por qué uno podría ocupar más espacio que el otro. Entonces lo primero que tenemos que hacer es que primero necesitamos. Como dije, entender los datos. Entonces lo que son los datos es Es igual que, por ejemplo, es algo algún tipo de ceros y unos que significan algo. Entonces, por ejemplo, un tres podría ser una pieza de datos o un texto completo, O tal vez un documento completo podría ser una pieza de datos. Y lo que sucede en una computadora es que este tipo de datos se almacenan en, por ejemplo, como un disco duro, que está en sección en diferentes pequeñas partes y esas partes de sección en las aún más partes Y luego dentro de uno de esos, tienes como cúmulos, que tipo de salen a lucir así aquí mismo. Entonces, por ejemplo, tal vez esto representa todo esto aquí mismo y lo que cada uno de estos representa es una pieza de datos. Y así cada uno de estos tendrá en realidad una dirección en la memoria, como una dirección para donde está tu casa. Si desea enviar un paquete, el equipo utiliza exactamente lo mismo. Por ejemplo, quizá éste. Por lo general usa Hexi decimal para que así voy a usar Tal vez este sea 00 y así éste sería entonces 01 Y este símbolo cero con poco X al lado usualmente significa Hexi Decimal. Entonces eso es lo que estoy usando para esto. Por lo que seguiría continuamente aquí abajo. Esto sería 020304 etcétera. Y entonces por qué esto es importante es porque una vez que tengamos la dirección, realidad podemos agarrar lo que está en esa dirección. Entonces, por ejemplo, si tomamos una pieza de datos, digamos que teníamos una cadena o una pieza de datos que era tres y cuatro, así Y digamos que tres se almacenaron. Cero x 00 y cuatro se almacenó en cero x 01 Así que ahora si queremos agarrar estas piezas de datos, lo que podemos hacer es crear una tabla con este tipo de datos y sus asociaciones. Entonces, por ejemplo, nuestra mesa puede decir tres. Está almacenado aquí. Esto se almacena aquí, excepto que normalmente sería lo inverso. Diría lo que está a las 00 y sería algún tipo de dato. ¿ Qué es eso? 01? Y sería algún tipo de datos. Y así Ahora, cuando realmente queremos recuperar estas piezas de datos, podemos buscar la dirección o viceversa. Si queremos ver qué hay en ello, podemos ir a él y averiguarlo. Entonces digamos que queríamos recuperar. Tres. Queremos recuperar los tres en nuestro conjunto de datos. Por lo que tres se encuentra justo aquí y cuatro se encuentra justo aquí. Y así queremos recuperar tres. Entonces básicamente lo que hace nuestro programa detrás de bambalinas. Muchas veces, a menos que tu programa a un nivel muy bajo, lo que significa dedo del pie muy cercano como máquina, manipulando la máquina completa y totalmente dentro de ti mismo, usualmente lenguajes ensambladores y cosas así. Entonces todo lo que tenemos que hacer es decir, ya sabes, solo var X equivale a tres y con la máquina lo está haciendo diciendo, Vale, ahora estamos asociando X con la dirección cero x 00 Así que en cualquier momento el usuario usa o llama a X , vamos a agarrar lo que alguna vez está en cero x 00 Ahora el usuario entra aquí y él entonces, ya sabes, crea una nueva variable. Por qué es igual a cuatro, Y así ahora por qué se asocia ID con vino cero x cero. Eso es lo que hace el programa es digamos que teníamos que ir el programa. ¿ Qué es X plus? ¿ Por qué? ¿ Qué es eso igual? Bueno, lo que hace es que va OK, entonces X esta a las 00 Vamos a agarrar lo que nunca? A las 00 y vamos, escanea hasta el disco duro. Va todo el camino y encuentra 00 y va, Hey, aquí hay un tres. Por lo que luego se llama a los tres, traídos todo el camino de vuelta en el procesador, y luego se almacena en Ram, que es una memoria más cercana a la computadora real. Pero eso es una especie de eso se está poniendo realmente, realmente nit exigente y cómo funcionan las computadoras. Pero todo lo que hace es agarrar eso y dice, Este es un tres. Y entonces así ahora decimos que queríamos sumar al por qué y así hace exactamente lo mismo . Pasa por su lista. Se encuentra el sector, el clúster, lo que sea que baje y diga: Oh, Oh, es dirección o uno que devuelve. Ah, ¿qué es la dirección o qué cuatro va todo el camino de vuelta arriba y regresa antes Y por supuesto, hace esto en tiempo casi instantáneo, y entonces así entonces podría hacer los cálculos que llamó. Son dos piezas de datos aquí mismo. Y así ahora hace el cálculo de siete. Y así eso es en una base de cómo se almacenan los datos en una computadora. Es sólo un Siri básicamente de una especie de estas direcciones, y hay diferentes formas en que puedes almacenar este tipo de datos. Entonces, por ejemplo, esto es más una forma directa de almacenarlo donde podemos llamar específicamente a la dirección. De qué manera se dijo Queremos asignar, Vamos a eliminar un par de cosas aquí. En realidad, lo que podemos hacer es duplicar esta diapositiva aquí mismo y nos moveremos hacia abajo. Por lo que ustedes tendrán este topside, se duplicarán y luego una especie de borrarlo y hacer un segundo ejemplo aquí. Entonces esa fue una forma muy directa de decir lo que era. Si dijimos que tenemos estos datos, esta estructura que va a estar entre aquí y aquí y su dirección en su conjunto va a ser cero X 00 ahora Si llamamos a cero x 00 digamos, Bueno, pongamos algunos datos aquí. Si llamáramos a cero x 00 no habría datos específicos aquí. Estamos llamando a toda esta entidad, para que eso no nos ayude en absoluto. Entonces lo que podríamos hacer es aquí donde empezamos a una especie de meternos. La siguiente parte es que en realidad podemos especie de en pequeños mini nombres a cada uno de estos pequeños segmentos. Entonces esto es solo 12345 Y podemos usar estos tipos realmente básicos de clasificaciones porque tenemos nuestra dirección principal aquí mismo. Y ahora, ya que tenemos nuestra dirección principal, lo que vamos a hacer es ir a la dirección principal, y luego vamos a usar uno de sus pequeños mini nombres para encontrar cualquier dato que estemos buscando. Y esto es lo que se llama una matriz. Y la próxima conferencia. Realmente vamos a empezar a llevar esto al siguiente nivel, pero esto se llama matriz. Entonces lo que podemos hacer es que podríamos crear, salvar a nuestra X igual y luego crear algo como esto. Y entonces ahora es almacena esa pieza entera de datos en esta pieza de memoria y que ahora si dijimos Retorno X de lo que sea que sea pequeño mini nombre. Entonces digamos X de uno. Ahora ya va a venir. Se va a ir al cero x 00 y luego va a ir al mini nombre de uno, que es un dos. Entonces va a volver a y así esa es una forma diferente de mirar. En lugar de tener acceso directo, podrías tenerlo segmentado en piezas como esta. Y lo que resulta ser es que en realidad suele ser la más común. Porque si tuviéramos una dirección directa para cada pieza en la memoria, estaríamos desperdiciando mucho espacio y seríamos algunas mesas realmente, realmente grandes, porque hay que pensar que la memoria no puede Ah, computadora no puede crear memoria sobre la marcha como no puedes simplemente almacenarla en tierra imaginaria. Si quiere almacenar cada una de estas relaciones, tiene que tener toda una otra sección de memoria que designe específicamente para almacenar memoria. Entonces si intentas hacer almacenar cada pieza de datos como esta, tu espacio empieza a ser realmente grande, y estos son todo concepto. Vamos a empezar a descomponernos a medida que vamos más allá. Pero solo quería una especie de mostrar esto en un nivel superior hacia abajo para que puedas empezar a entender cómo funciona la memoria. Y luego cuando nos metemos en estas estructuras de datos como un aumento, como árboles como listas enlazadas, podrías empezar a entender cómo podría funcionar bajo el tipo de capó encendido. Podemos meternos un poco más de, ya sabes, sólo ese entendimiento, y una vez que lo entiendas, puedes usarlo mejor. Se puede manipular mejor. 10. Introducción de Arques fijos: Entonces vamos a repasar nuestra primera estructura de datos importante, y esa va a ser la matriz y en esta situación, la matriz fija. Entonces, ¿qué es una matriz? Bueno, en una redada, por definición es un Siris ordenado de arreglo. Y así todo lo que eso significa es que es una agrupación de una especie de elementos similares juntos. Y en esta situación, los elementos similares sólo significa que hay pieza de datos así que en un rayo en el mundo de las ciencias de la computación es sólo una recopilación como de datos o una realmente sólo una recopilación de datos que está todos al lado otro. Y lo que quiero decir con eso es que repasaremos diferentes estructuras de datos más adelante donde podrías tener un pedazo de información aquí en un disco duro y luego otra pieza por aquí y luego otra por aquí y por allá, acaba de enlazar junto con algo llamado Pointers. Entonces es como, digamos, si quisiéramos representar lo de abajo aquí abajo, tendríamos algo como esto. Pero podría haber, ya sabes, un montón de piezas diferentes en el medio, y un montón de piezas diferentes en el medio también. Y eso no es lo que en una carrera eso es algo llamado lista enlazada. Entonces en un rayo es cuando están todos juntos y obtienes ciertos beneficios de eso, obtienes ciertas desventajas de eso. Pero una especie de matriz se ve así cada vez que lo representas. Visualmente, tienes este segmento de memoria, y cuando creas una matriz, normalmente siempre asignas cuánto tiempo quieres. Estás preguntando a la computadora. Yo quiero una sección de seis piezas de datos y la computadora esta va a buscar a través de su disco duro, y luego va a encontrar un lugar de seis, y te va a dar esa ranura. Entonces, por ejemplo, en nuestro disco duro, si pedimos un lugar de tres, miraría a través, miraría ahí y como, Oh, aquí mismo tenemos una sección de tres. Por lo que te daría estas tres piezas de datos, y eso sería todo en código. Típicamente está representado por una declaración de corchetes como ese. Entonces dirías algo como X es igual a thes brackets, y esto significa una matriz vacía. Y luego, si quieres ponerle información, podría ser algo así como X equivale a 123 Y eso sólo va a crear una matriz que se ve un poco como esto, donde tienes el primer lote de uno, la segunda ranura de a y la tercera ranura de tres como así. Entonces así es como se representaría en código. Ahora bien, ¿cómo cuenta una matriz? ¿ Qué es? ¿ Sabes qué? ¿ Para qué se utiliza? Una de las partes más importantes es que la matriz comienza en cero. Se llama indexación cero. Eso significa que siempre que queremos agarrar el primer elemento cada vez que queremos agarrar este elemento o en esta situación, este elemento alguna vez querría agarrar uno de esos desarrollos. Tenemos que empezar a cero. Tiene que ser este cero aquí mismo. Esto se debe a que ah, muchas fórmulas informáticas funcionan con cero. En realidad hay discusiones en línea enteras de por qué seguimos usando cero basing. Antes había, ah, ah, un montón entero de diferentes tipos de razones para ello y la razón que empezó a caerse. Pero sea lo que sea ahora mismo, seguimos usando cero basing. Por lo que en array siempre está empezando por cero. Y eso significa que el final es algo llamado en menos uno lo que está en menos una media terminará en esta situación es sólo la longitud de la matriz. Entonces eso significa que el último va a estar en menos uno. Serán sólo seis. Por lo que esto, como se puede ver, sostiene siete pieza de información. 1234567 Sin embargo, si queremos agarrar la última pieza de información, no agarramos siete. Agarramos seis, un poco confuso al principio. Y muchas veces, incluso veteranos científicos informáticos, se equivocan todo el tiempo. Pondrán, pondrán , ya sabes, si están tratando de agarrar el último elemento, pondrán X de siete. Y eso va a devolver algo llamado falla de segue, que es sólo la computadora diciéndote, Hey, estás accediendo a la memoria fuera de los límites. Estás accediendo a la memoria. No te he dado control sobre y más débil lenguaje o lenguajes que no tengan salvaguardias en él. Bueno, en realidad, solo devuelve cualquier basura que haya ahí, así que eso se llama en realidad Ah, ataque de desbordamiento de búfer es que si atacas ese lado derecho, puedes hackear las cosas con eso. Pero eso es lo que les gusta a los lenguajes realmente básicos como C, ya sea en un montón de tipo de salvaguardas. Pero siempre que tratemos de hacerlo en algo así como, Java nos va a decir que la segunda falla estaban accediendo a memoria que no se ha concedido en el disco duro, hay algo más ahí que no deberíamos estar tocando. Y para que, como dije, se llama un apagado por un solo aire. Pon la parte importante que necesitas para salir de esta conferencia. Esta introducción para arreglar un aumento es que uno en array es solo una recopilación de datos en el mismo lugar en el disco duro irá por encima de la ventaja de que en la próxima elección hablamos de los tiempos de corrida. Pero esto es lo que es. Se trata de una recopilación de estos datos juntos. Lo siguiente que sabemos es cuál es la parte fija de esto iba a hablar de diferentes matrices. La parte fija de la misma sólo significa que nunca va a cambiar. Entonces en esta situación, si creamos una matriz de talla cuatro, siempre va a seguir siendo tamaño porque no hay código para hacer un go más grande y hacer ir más pequeño. Una vez que lo llenamos, se llena. O tenemos que sobrescribir algo o eliminar algo o mover algo en otro lugar para poner más información disfrutada. Pero de todos modos, esa es la introducción a las matrices fijas, realmente , realmente necesitan estructuras de datos, y vamos a saltar a algo más de la nitty gritty de cómo realmente usas estas cosas y cuál es su ventajas son. 11. Tiempos de Array fijo: Echemos un poco de un vistazo más profundo a las matrices fijas y veamos su tiempo de ejecución, realmente usando las cosas que aprendimos en la última unidad, ya sabes, el análisis de tiempo mumbo jumbo vamos a estar tomando que estamos en realidad va a estar implementándolo y mirando las velocidades de diferentes tipos de funciones dentro de la matriz. Y entonces podremos tomar ese tipo de velocidades y podremos mirar diferentes estructuras de datos podrán compararlas juntas. Entonces eso es lo que estaremos haciendo. Vamos a estar viendo algunas de las ventajas. Vamos a estar viendo algunas de las desventajas, y sólo vamos a ser una especie de inmersión profunda en lo que es la matriz fija y por qué podrías usarlo. Lo primero que vamos a repasar es la inserción aleatoria. Entonces hay algo con lo que tenemos que juntarnos. lo que vamos a estar hablando cada vez que hablemos de una inserción, de una eliminación o incluso de buscar lo que queremos decir con una inserción es si tenemos un conjunto de datos que queremos mantener en el relativamente el mismo tipo de orden Entonces, por ejemplo, todos los datos son importantes en todos nuestros ejemplos. Entonces si tenemos uno a dos o tres, no tenemos. Cuando decimos insertar, no queremos decir dedo del pie sobrescribe algo que se llama reemplazar. Entonces no estamos hablando de, ya sabes, sólo cambiar esto a un dos. Entonces es de 2 a 3 o cambiando este 1 a 2 o, ya sabes, haciendo lo que sea. No se trata de que una inserción esté insertando entre aquí o insertando en un lugar a su alrededor . Entonces, por ejemplo, en inserción sería Este es un espacio en blanco y queremos insertar un tres aquí. O la inserción podría ser que después de uno, queremos insertar un tres. Entonces, ¿cómo vamos a hacer eso? El producto final? Lo que queremos es que queremos es algo que salga como 132 y así que ese es el en búsqueda, y eso es lo que queremos decir con una inserción aleatoria. Entonces, ¿cuál es el momento de esta inserción aleatoria? ¿ Qué se necesita si queremos insertar al azar algo aquí? Y sigamos adelante y eliminemos ah, par de los elementos traseros. Entonces tenemos algo con lo que trabajar aquí y así Ahí vamos. Entonces, ¿cuál es el tiempo que va a tardar en insertar algo en una matriz fija? Bueno, el tiempo termina siendo O hasta el final o hasta el final. Entonces, ¿por qué exactamente es o hasta el final? Bueno, echemos un vistazo a esto. Este ejemplo aquí mismo tipo de lo muestra. Siempre que estamos insertando al azar, tenemos que asumir que no sabemos dónde va a estar insertando. Podría estar insertando aquí. Podría estar insertando aquí. Podría estar insertando al final o al principio. Pero lo que sí sabemos es que a menos que seaal final, al final, vamos a tener que mover algunos datos. Entonces vamos a tener que tomar estos datos, y queremos cambiarlos todos hacia abajo para que quepan esta otra pieza de datos. Entonces, por ejemplo, digamos que en este ejemplo, aquí arriba tenemos un vamos a extender esto hacia afuera, y digamos que queremos insertar otro número que queremos aquí. Queremos insertar un cuatro. ¿ Qué vamos a tener que hacer, qué cantidad de trabajo o vamos a tener que hacer para meter a esos cuatro ahí para hacer esto, vamos a tener que llevarnos los tres. O en realidad, normalmente vamos a empezar el final aquí. Entonces nos vamos a llevar los dos. Vamos a moverlo, vamos a tomar los tres, vamos a moverlo, y luego vamos a tomar los cuatro, y vamos a insertarlo. Entonces eso va a tomar cuántas operaciones lo harán al máximo, va a tomar toda la matriz. Vamos a tener que mover cada elemento y luego más la adición del nuevo elemento. Entonces, ¿cuántos elementos de eso? Bueno, esa es nuestra confianza en que tenemos uno. Recuerda que en es la longitud de nuestro el tamaño de todas las piezas de datos que estamos tratando insertar. Entonces, ¿cuántas operaciones iban a hacer? Bueno, toda la pieza de datos actual va a requerir una Operación un movimiento para mover tres, mover por movimiento. Entonces eso va a estar dentro. En el mejor de los casos. Va a ser sólo una constante de inserción regular, así que va a ser sólo una. Pero aquí es donde se pone complicado. Tenemos que mirar el promedio. ¿ Cuál es el tiempo promedio que va a tomar para seguir insertando en una gráfica o en una matriz aquí, y ahí es donde obtenemos nuestro escribió el final aquí mismo. ¿ Es ese el tiempo promedio que va a tomar? Es algo así como, Oh, en más de dos y se puede pensar en eso. Si promediamos sobre una distribución normal, ya sabes, los ponemos en un punto aleatorio diferente. Estadísticamente y probabilidad sabia, los va a insertar al, uh, menos la misma cantidad para cada una de las células. Entonces digamos que lo insertamos. No lo sé, 12 veces probabilidad sabia, deberíamos llegar a aquí a aquí, a aquí, a A bajar la lista fuera de lugar diferente para insertar. Y eso significa que aquí arriba, va a tomar tiempos cada vez. Y entonces aquí va a tomar en menos uno en menos dos en menos tres y menos cuatro y menos cinco en menos seis. Entonces va a tomar tiempo constante, y para que eso promedia a todos ellos combinados sobre a lo que nos va a dar luego nuestro en más de dos. Y recuerda, estamos hablando de tiempos de corrida. Tenemos que tachar lo que sea que tengamos. Esto es sólo un 1/2 en el frente. Entonces simplemente lo tachamos. Y entonces eso significa que nuestro tiempo promedio termina siendo justo eso en. Por lo que una inserción aleatoria es a tiempo. Entonces, ¿qué En qué es la inserción al frente? Pero estamos hablando de eso, y esa es en realidad la parte lenta de nuestras inserciones. Inserción al frente va a ser o a la N también. Déjame deshacerme de esto por aquí. Entonces en cierto del frente va a ser O hasta el final. ¿ Recuerdas cuando estábamos hablando del ejemplo justo antes? Dijimos que si nos insertamos en el frente, ese va a ser nuestro peor escenario. Vamos a llevarnos todo y moverlo por uno. Entonces esa va a ser la O hasta el final. Ahora bien, ¿qué pasa si insertamos a la parte de atrás? Entonces, ¿vamos a insertar a este spot aquí mismo? Bueno, esta es una inserción muy fácil. Podemos simplemente poner un tres aquí. Si te queríamos y lo hemos insertado. Es un tiempo constante. Todo lo que se necesita es una sola operación que es tomar número. Ponlo en. No importa cuántas piezas tengamos. Esto podría ser, ya sabes, esto podría ser cero y luego 10 2030 40 50. Y en esos puñado de números en el medio, no hay importa. Sólo vamos a decir, ya sabes que X de 50 equivale a tres y ahora es igual a tres. Siempre es tiempo constante. Entonces por eso, con una inserción de matriz en la parte posterior también es tiempo constante. Ahora, entonces, delish en una eliminación significa que vamos a eliminar el elemento. Pero hay que recordar, mantener la integridad. Levantemos todos los ceros aquí abajo para volver. Eso significa que tenemos que mantener la integridad. Y entonces, ¿qué significa eso? Eso significa que si le quitamos un siete, si quitamos los siete desde el principio, lo que tenemos que hacer es realmente necesitamos asegurarnos de que el resto de éstos caiga hacia atrás hacia eso. Entonces sigamos adelante y nos hagamos un pequeño ejemplo aquí arriba. Digamos que tenemos un montón de números, como así nos dieron una matriz 1234 que es tamaño para, pero la indexación recordar es comienza en cero. Entonces digamos que queríamos eliminar uno de nuestro conjunto de datos. Bueno, lo que sea que eliminemos el del conjunto de datos, no podemos simplemente dejar aquí un espacio vacío que no mantenga la continuidad de nuestros datos . Si tratamos de agarrar el primer elemento, solo asumimos que, ya sabes, tal vez tenemos un algoritmo y siempre intenta agarrar el primer elemento así. Se va a salir al aire. Ahí no hay nada. Entonces lo que tenemos que hacer cada vez que eliminamos del frente es que tenemos que hacer exactamente lo mismo . Tenemos que retroceder, retroceder, retroceder. Y como se puede ver de lo que hablamos antes, cualquier cosa que nos va a requerir que retrocedamos un montón de veces va a ser O hasta el final. Delish al azar también es ir al final también. Entonces si solo tomamos cualquier tipo de borrado aleatoriamente aquí, se le debía. El final ahora en array también tiene ese bonito beneficio de poder eliminar de atrás en tiempo constante porque no tenemos que cambiar nada. Entonces si queríamos simplemente borrar los cuatro de atrás, todo lo que tenemos que hacer es simplemente borrarlo. Entonces en código, ya sabes, podría ser algo así como X de tres iguales no son cotización vacía o lo que sea para hacerlo vacío. Entonces, de todos modos, así de sencillo es. Se Zingale operación. Nada más tiene que entrar, así que también le debe a la mujer tiempo constante. Entonces estos aire estos aire, el corto plazo, que usaré a veces es tiempo lineal. Por lo que todos estos son tiempo lineal. Esto es tiempo constante, lineal, constante. Y yo sólo quiero enseñarte ese voto ahora porque, como dije, podría intercambiarlos en el futuro y diciendo: Oh, Oh, al 10 al N Cada vez se pone un poco aburrido. Por lo que mucha gente solo dirán Constante, Dirán, lineales esos tan exponenciales. De todos modos, veamos nuestro último. ¿ Cuánto tiempo se tarda en buscar algo? El listado de búsqueda y sin clasificar. Esto de aquí está sin clasificar. Tenemos siete. Tenemos 89 10 y luego uno. Entonces no hay ningún tipo de orden aquí. Realmente no conocemos el orden. Entonces, ¿cuánto tiempo va a tardar? Digamos que queremos ver es a es un nueve presente. Bueno, no hay riel. Forma rápida de hacer esto. Lo que tenemos que hacer es hacer el método de la cuarta fuerza bruta bruta. Eso significa que tenemos que empezar aquí. ¿ Se niega este mal? No. Pasar al siguiente. ¿ Es esta secuela esta noche? No. Pasar al siguiente. ¿ El sencillo es el nueve? Sí, lo es. Pero si estamos, por ejemplo, buscando 90 estaríamos como, Nope. No, no. Y vamos todo el camino abajo de la lista hasta que nos quedamos sin. Hasta que lleguemos a un espacio aquí mismo que no tenga información alguna. Y entonces volveríamos. No, no es igual a 90. Por lo que esa operación termina siendo como el resto. Ah, el final. Porque en el peor de los casos, vamos a tener que bajar cada uno de estos y hacerlo todo el camino hasta el final para averiguar si realmente existe dentro de la matriz, podríamos tener suerte. Por supuesto que a veces podría ser al principio mismo. ocasiones podría ser de dos o tres elementos en, pero en promedio, el peor de los casos es que se va a deber hasta el final. Entonces ese también va a ser tiempo lineal. Y luego la última, la última vez. En realidad vamos a decir para la próxima conferencia porque esto va a funcionar previo, un poco de especie de inmersión profunda en por qué sale una matriz ordenada de búsqueda para iniciar sesión. Y así podrías estar mirando eso ahora mismo siendo como, ¿Qué significa eso? Por eso vamos a sumergirnos en profundidad exactamente por qué esa búsqueda ordenada registro igual de fin. Pero sólo quería repasar una o dos cosas más en esta conferencia, y luego vamos a seguir adelante y saltar a esa conferencia. Lo último que quiero repasar es ¿qué nos dice todo esto? ¿ Qué nos dice esto de las ventajas y las desventajas de una matriz podemos ver inmediato del bate que por almacenar datos que todos tienen una especie de integridad para ellos, tal vez en una tasa no es lo mejor para como si tuviéramos Ah, programa que necesita insertar y elite constantemente porque cada vez que insertemos borrar, se va a deber hasta el final, sobre todo si estamos insertando al frente o al azar dentro de él. Y en realidad tenemos otras estructuras de datos que pueden hacer que esos todos los tiempos constantes. Entonces tal vez algo así no es muy importante. Y algo que tipo de no está por aquí pero hemos estado dando por sentado es la capacidad simplemente comprobar lo que hay en cada uno de estos elementos. Yo sólo puedo decir, ya sabes, puedo llamar menos tres. Puedo llamar a este elemento, y me va a decir instantáneamente que hay 10 ahí. Eso es algo más que es una ventaja muy grande para una carrera. ¿ Es este tiempo de acceso constante? Eso es algo más que tal vez no comparamos con otros tanto. Pero se llama tiempo de acceso. ¿ Cuánto tiempo se tarda en llegar a un elemento dentro de la matriz y en esta situación, todos estos tiempos de aire constante? Eso es lo que te da una matriz es la capacidad de simplemente empezar en algún lugar y luego ir a cualquiera de estos elementos y llegar a él de inmediato. Entonces el tiempo de acceso es constante, y eso es muy importante. Si, por ejemplo, digamos que no tenemos un programa que saca e inserte mucha información con el programa que de vez en cuando hace eso. Pero la mayoría de las veces es sólo revisar diferentes lugares. Solo estamos almacenando información diferente aquí, y entonces somos como entonces los programas como, Vale, Vale, necesito el número tres, ¿qué hay en el número tres? Y el número cuatro? Lo que está en el número cuatro y luego es constantemente una especie de mandar esa información de ida y vuelta . Pero la mayoría de las veces. Esto se mantiene cotizar uncomillas estáticas, lo que significa que no cambia. Ahí es donde una matriz puede ser útil. Tenemos ese tiempo de acceso realmente rápido, y hará que todo vaya mucho más rápido. No obstante, como dije, si estamos insertando en liderar todo el tiempo, tal vez quieras mirar una estructura de datos diferente de todos modos, vamos a saltar a eso realmente necesita ejemplo de la búsqueda ordenada, y veamos por qué eso sale para iniciar sesión 12. Algoritmo de búsqueda de Search de 2 o 4 de la barra fija: Entonces repasemos de lo que hablamos en la última conferencia. Y esa va a ser la búsqueda de matriz fija ordenada. Entonces, ¿por qué esto es diferente? ¿ Por qué esto nos ayuda a llegar a ese interesante runtime de log in que es sustancialmente más rápido que el O hasta el final. La versión sin clasificar. Esto va a ser mucho más rápido que por qué cuando lo ordenemos, ¿Tenemos esta ventaja? Y eso es porque hacemos algo llamado tipo binario. Entonces va a ser un algoritmo de clasificación binario o un algoritmo de búsqueda binaria. Mi mal. Algoritmo de búsqueda binaria. El motivo por el que esto nos permite hacer un algoritmo de búsqueda binaria es por la forma en que se configuró. Entonces imagina la antigua forma de hacerlo. Y ese es el método de la fuerza bruta. Digamos que estamos tratando de encontrar ¿existe 19? Entonces estamos tratando de descifrar es 19 existir como Así que para hacer eso con un método de fuerza bruta, sólo vamos desde el principio. ¿ Está aquí? No. No, no, no. Y sólo seguimos bajando por la lista. Y por supuesto, podría no estar en la lista y Por lo tanto, tenemos que pasar por toda la lista para averiguarlo. O podría estar a mitad de camino de la lista o cerca del final, o tal vez justo al principio. De cualquier manera, en el peor, va a tomar Esa lista entera va a llevar O a la hora del final. No obstante, con una búsqueda binaria, podemos garantizar que está en Lee Going to take log of end time and log of in time es como dije, es mucho más rápido. Recuerda cuando estás hablando de iniciar sesión y de los tutoriales anteriores, va así, lo que significa que el al principio mismo, el número fuera del número de elementos que tenemos. Entonces digamos que esto yendo a la derecha aquí, este acceso va a ser el número de elementos en que tenemos. Y así es el tiempo que lleva. El tiempo de búsqueda o de ejecución son tiempo de ejecución. Y entonces lo que eso nos va a decir es que con el Mawr en que conseguimos esta carrera, tiempo se ralentiza para que en algún momento salgamos como 32,000 y va a ser básicamente el mismo tiempo de ejecución a 64,000 que es básicamente el mismo tiempo de ejecución que 128,000. Va a subir más lento y más lento y más lento cada vez. Y así sucede esto por la forma en que funciona la búsqueda binaria. Entonces sigamos adelante y pasemos por ese ejemplo. ¿ Cómo pasaríamos? ¿ Cómo buscaríamos una matriz fija? Bueno, lo que hacemos es seguir adelante y hacemos esta pequeña fórmula. Se llama izquierda más derecha a. Entonces tomamos a la izquierda más a la derecha, y luego vamos adelante y dividimos eso por dos. Entonces esa es nuestra fórmula. Entonces sigamos adelante. Tomemos eso Y en realidad movamos eso ahí arriba porque vamos a estar referenciando mucho a esto mientras hacemos esto. Entonces izquierda, plus, derecha a. Entonces lo que quede a la izquierda va a seguir adelante y ser la porción muy izquierda. Va a ser el número que nos quede de la izquierda, si eso tiene sentido. Entonces en esta situación, es una matriz completa. Están a la izquierda, es cero y están a la derecha es la derecha completa de la derecha aquí, que es el 10. Vamos a tomar esos dos números, vamos a sumar juntos, y luego nos dividiremos por dos. Y ese es el índice Vamos a buscar al principio. Entonces eso significa nuestro primer paso aquí mismo. Vamos a tomar la izquierda. Mantengamos los números iguales aquí. Vamos a tomar la izquierda, que va a ser cero, y luego vamos a seguir adelante y sumar a la derecha, que es la 10. Y lo iban a dividir por dos. cual, por supuesto, sólo sale a 10 dividido por dos, que es cinco. Entonces nuestro primer paso, agarramos el índice cinco aquí mismo. Entonces vamos adelante y agarramos el índice cinco. Vamos adelante, lo tomamos, lo traemos de vuelta y echamos un vistazo. ¿ Qué es? Entonces, ¿qué es ex de cinco? Bueno , regresa 12. Por lo que ahora nuestra próxima decisión es 12. Menos o es mayor que el número que buscamos? Bueno, 12 es menos que el número que buscaban. Y recuerda, esta es una matriz ordenada. Entonces si 12 es menor que el número que buscamos, ¿por qué alguna vez buscaríamos de este lado? Ya sabemos que esto está ordenado, así que me refiero a que todo antes de esto va a ser menor de 12 y sabemos que nuestro número es en realidad mayor a 12. Sabemos que 19 es mayor a 12. Por lo que 19 tiene que estar de este lado. Entonces, por tanto, sólo tomamos todo este lado por aquí y acabamos de salir. Ni siquiera lo miramos. No lo vamos a tocar. No vamos a verificar lo que hay ahí porque confiamos en que esta matriz ordenara. Por lo tanto, vamos a seguir adelante y a ir a la derecha. Vamos a echar un vistazo al lado derecho, y luego vamos a hacer nuestra pequeña fórmula una vez más. Entonces vamos a seguir adelante y tomar la izquierda y la izquierda ahora es un cinco. Normalmente, sin embargo, ya hemos buscado esto. No necesitamos hacer Mira esto. Entonces en realidad vamos a hacerlo ya que es mayor de lo que le agregamos uno. Si fuera menos de lo que nos llevaríamos uno. Pero vamos a seguir adelante y empezar con seis ahora, así que vamos a seguir adelante y seguir con seis, y luego vamos a sumar un, uh, más el lado derecho, que sigue siendo 10. Divide eso por dos. Y esta situación, en realidad vamos a conseguir un 16 dividido por dos, que va a igualar ocho. Y para que veamos aquí la sección ocho o el índice ocho, vamos a decir, ¿Qué es eso? Índice ocho. Echamos un vistazo. Y, por supuesto, X de ocho. Bueno, eso devuelve un 20. Bueno, es 20 mayor que o es menor que nuestro 1920 es mayor que 19. Por lo que nuestra segunda búsqueda fue justo aquí. 20. Echamos un vistazo. Nos damos cuenta de que es lección. Entonces vamos a la izquierda. Y eso significa que Hey, no necesitamos toda esta sección por aquí. Entonces ahora vamos a seguir adelante y tomar el ocho menos por uno, y luego vamos a tomar lo que quede. Por lo que la parte izquierda de esto es seis. La parte correcta es siete. Entonces vamos a seguir bajando la fórmula. Entonces vamos adelante y tomamos el seis y luego lo sumamos a los siete en esta situación sumados a siete. Entonces dividimos eso por dos, y nos sacamos 13 divididos por dos. Ahora bien, esto es importante. Tenemos 13 divididos por dos. Con esto, típicamente hacemos algo llamado truncamiento donde esto no equivale a 7.5 en esta situación . O en realidad, nada de esto sería 6.5. Esto no es igual 6.5 y no lo redondeamos. No lo redondeamos todo. Hacemos lo que le llamamos truncamiento, que es Acabamos de truncar el back end. Sea lo que sea esto, lo borramos y tomamos lo que sea el entero. Tomamos cualquiera que sea el número al principio es el número entero. Entonces, por ejemplo, si tuviéramos un 7.9 , seguiría siendo siete. Teníamos 7.3. Seguirían siendo siete. Si tuviéramos 7.98 seguirían siendo siete. Eso es lo que es truncar. Entonces eso es lo que hacemos. Sea lo que sea que hagamos esta fórmula. Entonces truncamos y comprobamos seis. Vamos adelante y echamos un vistazo a seis. Echamos un vistazo a seis y nos sacamos el número 17. Volvemos a hacer nuestro pequeño proceso. Bueno, sabemos que es correcto de ello y en realidad podemos hacer la fórmula una vez más aquí y por lo general tener como un cheque. Si es el último elemento, basta con mirar el elemento del mismo. ¿ Está ahí? ¿ No es seguir adelante? No obstante, podemos volver a hacer todo el asunto. Podemos hacer. El siete es a la izquierda. Más siete es la derecha dividida por dos. Entonces eso es 14 dividido por dos, lo que equivale a siete. Entonces hacemos nuestra fórmula comprobamos es siete. Aquí mismo es 19 igual a 19. Lo es. Eso significa que aquí mismo vamos adelante y sólo lo comprobamos. Es así que eso es lo que hace esta fórmula. Se lo toma y cada vez que lo divide por la mitad. Y esa es una especie de la parte importante aquí. Entender es que cada vez que dividimos el problema y 1/2 así que eso significa, por ejemplo, si empezamos con oh, no lo sé, como 128 artículos diferentes después de la primera generación solo estaban revisando 64 ítems. Después de eso, estamos revisando 32 artículos y después de eso estamos revisando, ya sabes, 16 y en ocho y luego cuatro y luego dos y luego uno. Y la cosa es, es porque esto se duplica cada vez, el número de pasos sólo aumenta. Aumenta más lento y más lento. Entonces, por ejemplo, cada uno de estos es un paso. Por lo que tenemos 123456 y íbamos a repasar esto múltiples veces a lo largo de este curso porque es tan importante en tantas áreas diferentes. Pero lo que tenemos aquí es que 128 equivale a Onley seis pasos. Ahora, si duplicamos eso, si vamos un paso más allá Así que en lugar de 128 ítems, tenemos 256 ítems Will 256 solo equivale a siete. Sólo hacemos un paso más para llegar allí. Y entonces, claro, podríamos bajar otra, que va a ser 512. Y eso es sólo un ocho igual y así sucesivamente y así sucesivamente y así sucesivamente. Entonces conseguimos que esa gráfica de la que estamos hablando no no no tan fea. Tener una gráfica. Obtenemos esa gráfica de la que estamos hablando, donde sube y termina donde el número de en que obtenemos el cambio, el tiempo de ejecución, este es el tiempo de ejecución de la izquierda se pone cada vez menos y cada vez menos y menos y menos con el tiempo. Y que este patrón aquí, esto se llama Iniciar sesión. Y si realmente aplicamos, si realmente ponemos en registro de 512 realmente nos consigue. Da salida ocho. Eso es lo que es el patrón. Esto es Esta es justamente la forma en que los matemáticos representan. Este patrón es a través de esta cosa llamada log. Y por eso sale el tiempo de ejecución para iniciar sesión. Porque este pequeño patrón complejo aquí, realidad no es demasiado complejo. Una vez que te conectas a una computadora, es como seis líneas de código. Pero este patrón aquí mismo realmente hace todo el asunto. Lo hace y lo corta a la mitad cada vez para que tengamos el log in tiempo. Y por lo tanto, ya que podemos hacerlo ahí dentro, podemos usar esta búsqueda binaria para hacerlo. Nuestro peor caso, tiempo de ejecución, se puede bajar a solo log de n 13. 2-5 Arrays circulares: en la última lección, discutimos un aumento y cómo podríamos sumar restar. Y entonces también discutimos el tiempo de estos rayos, ¿ como qué? Todo tipo de operación, lo que cuesta. Entonces si quisieras contestar al azar, podríamos hacerlo básicamente al instante. Pero si quisiéramos insertarlo en el frente con respecto a, como el resto de la carrera, tenemos que empujar al resto del rayo hacia atrás en realidad tendría que ir todo adentro. Y todo este tipo de, ya sabes, asumen que no estamos anulando. Cosas en las que asumen que estamos gestionando nuestros datos de manera efectiva sobre no estamos borrando o anulando o yendo demasiado lejos de nuestros límites de matriz. Entonces estos son básicamente los límites de la matriz que hemos creado, pero en realidad podemos mejorar en uno de ellos, Y ese va a ser éste de aquí mismo, el inserto al frente creando algo que se conoce como una matriz circular. Entonces, en teoría, lo que estamos haciendo es la matriz y la memoria siempre va a verse así. Siempre va a ser una cuadra que va a ir desde, ya sabes, el mismo principio, todo el camino hasta el final como así se va a asignar y luego se va a llenar, y eso es sobre eso. Realmente no se puede hacer como cualquier otra cosa. Pero teóricamente lo estamos haciendo es que vamos a averiguar una forma de que podamos llevar esto llegar y podríamos convertirlo en un rayo circular, que es así. Entonces, por ejemplo, evidente en este momento y ahora realmente vamos a tomar este array, y vamos a convertirlo en este círculo aquí mismo. En beneficio de eso es ahora que si queremos insertar algo, digamos que tenemos 123 si queremos insertar algo al frente. Entonces digamos que este es el frente. Todo lo que tenemos que hacer es simplemente mirar uno hacia atrás e insertarlo ahí mismo. Y qué rápido con eso. Eso fue tiempo constante, lo que significa que en realidad podemos mejorar la inserción en el frente como tiempo constante creando esta matriz circular. Y entonces lo que vamos a dio es que esto es un poco difícil implementar en código, pero la teoría detrás no es tan difícil. Entonces vamos a tener lo que se conoce como Punteros. Vamos a tener uno que apunte a la parte superior justo aquí. Y iban a tener uno que apunta al fondo justo aquí. Y ambos van a apuntar en el mismo lugar exacto ahora mismo porque este top uno, este top one, va a ser el frente de nuestra derecha. Vamos a tener algo que nos diga que este es el frente, y vamos a tener algo que nos diga que esta es la parte de atrás. Y así ahora, cada vez que insertamos en la matriz y estamos diciendo que no estamos haciendo inserciones aleatorias solo estaban haciendo inserción en la parte posterior o inserción de la parte frontal de la matriz. Entonces estamos insertando en la parte trasera ahora mismo, o en el frente. Ambos están apuntando exactamente el mismo lugar. Vamos a seguir adelante un inserto, un número aquí mismo. Y así ahora que hemos insertado un número en nuestra matriz, entonces podemos tomar la espalda y dependiendo de cómo lo implemente. Entonces, por ejemplo, siempre podríamos insertar uno más lo que sea que se señale la parte posterior, o bien podemos apuntar la espalda al siguiente espacio disponible. Voy a apuntar al siguiente espacio disponible Así que llenamos este ahora y en la parte de atrás en realidad se mueve por aquí. Entonces ahora está señalando por aquí como así Y así ahora tenemos esto están de vuelta, se señala aquí, y así vamos a seguir adelante e insertar otro número. Entonces nuestro programa, podemos simplemente en realidad, si escribimos esto en un programa, realidad podríamos hacer algo como esto. Podríamos volver X atrás, y en realidad nos apuntará al lugar exacto que queremos llenar. Entonces vamos X atrás igual a seis. Y así ahora podemos poner un seis aquí. Vamos a hacer exactamente lo que acabamos de hacer antes. Vamos a seleccionar esto aquí mismo. Déjame obtener una selección aquí mismo para que pueda seleccionar en absoluto. Vamos a agarrar este elemento, y luego lo vamos a mover a la siguiente parte por aquí, y de alguna manera parte de mi flecha no lo logró con eso. Entonces vamos bien, parte de eso me iba a quedar ahí. Entonces lo que tenemos ahora es que la espalda se mueve sobre una. Por lo que ahora están de vuelta se señala aquí, y así todo va bien. Pero lo que podemos hacer ahora es porque tenemos estos punteros diciéndonos a dónde se dirige exactamente todo. En realidad podemos insertar del frente sin hacer um sin tener que empujar todo hacia adelante. Y eso es porque en lugar de empujar todo hacia adelante, sólo vamos a mover el puntero hacia atrás. Entonces insertemos del frente ahora sigamos adelante e insertemos el frente. Entonces, por ejemplo, podríamos ir, um, vamos x de frente equivale a algún número, pero notarás que en esta situación el frente realmente está apuntado al frente. Entonces lo que podemos hacer es que podríamos ir x de frente menos uno, y eso nos va a llevar al lugar justo al lado. El menos un spot. Y pudimos haber hecho lo que hicimos con la espalda donde lo quitaron y dijimos haciendo eso. Pero quería hacer las dos vías aquí, Así que estamos haciendo X de Frente menos uno es igual a siete. Y así eso nos va a conseguir ex de negativo uno igual siete. Pero eso no funciona. No podemos agregar uno negativo inju. Nuestro rayo obtendrá una segunda caída. Iremos fuera de nuestros límites. Los números negativos no aparecen en un aumento. Entonces lo que podemos hacer y decir es que en realidad va a hacer este algoritmo aquí donde vamos a tomar el número cualquiera que sea. Entonces insertamos en uno negativo y vamos a sumar sin embargo muchos, um, spots que haya aquí dentro y así se puede ver hay 123456789 10 11 12 Porque recuerda, esto es en menos uno. Por aquí, esto está en menos uno. Entonces eso significa nuestro en igual a 12. Entonces lo vamos a hacer es que vamos a tomar el atado ilegal y vamos a sumar en él. Y en este caso, Así que es negativo uno más y así estamos sumando como 12. Y así eso nos va a dar la posición de 11. Entonces ahora cuando vayamos a este negativo, vamos a volver a asociarlo, y en realidad vamos a insertar esto en la parte de atrás, ¿ verdad? Al igual que, inserte este siete aquí mismo en la parte posterior del rayo. Y ahora lo que vamos a Dio es que vamos a tomar el este elemento y lo vamos a arrastrar por aquí así Y ahora el frente de nuestro rayo es Déjame ir adelante y correr eso ahí para que no lleguemos a ninguna flechas aquí dentro. Entonces ahora la parte trasera o la delantera de nuestra tarifa está en realidad en la parte trasera de nuestra derecha, y así esto se pone un poco confuso. Eres como, ¿Cuál es el frente? ¿ Cuál es la parte de atrás? Entonces ya no tenemos que pensar en esto así, esta línea recta. Tenemos que pensar en ello como si lo acurrucáramos en círculos. Entonces lo estamos haciendo es hacer que emule ese curl es que realmente estamos tomando el frente y la parte trasera los estamos haciendo un seguimiento, y esto nos permitirá insertar en ambas posiciones simplemente llamando a un número determinado e insertando ahí. Y esto va a seguir así mientras éste va a seguir así. Y, por supuesto, podrías llegar a un punto en el que empiezan a anularse unos a otros. Y de nuevo, eso no es algo que estamos tratando de tratar contigo. Eso es un error. Si alguna vez tienes tu frente y tu espalda algo así como tratar de atacar exactamente la misma zona. Eso es un error de tu parte en la implementación de tu programa y tendrá que ser abordado en alguna parte en el abrigo. Pero esto no se trata del código. Se trata de la teoría. Entonces con esto, lo que hemos creado aquí con este rayo circular agregando los punteros delantero y trasero y, ya sabes, podrían ser sólo variables que literalmente nuestros números. Por lo que ahora podríamos decir frente equivale a 11. Si bien podríamos decir atrás equivale a dos y luego si alguna vez quisiéramos insertar, podríamos simplemente ir x de atrás como lo hicimos ahí arriba equivale a algo. O podríamos ir x de frente menos uno. Y yo hice los dos del menos uno y el exacto en esto porque, como dije, solo quería mostrarles a ambos los caminos, pero quizá quieras mantenerlos como similares. Um, por lo que debe ser atrás menos uno y frente menos uno o atrás y frente. Simplemente será confuso si uno de ellos es diferente al otro. Pero lo que estoy tratando de decir aquí es ahora que tenemos estas variables y son realmente fáciles hacer un seguimiento. Después de crear algo, solo decimos frente más una espalda más una o lo que sea. Nuestro frente menos uno atrás más uno Y entonces podemos seguir simplemente llamándolo. Empezando por la parte posterior en la parte delantera de este rayo, lo hacemos circular. Y a través de todo eso creamos, podemos tachar el o de adentro y con un rayo circular son el tiempo de inserción realmente se convierte en o de uno. 14. 2-6 Arrays dinámicos: hasta llegar a este punto, como que ignoramos caso importante. Y ese es el hecho de que un aumento puede llenarse y lo que hacemos, ganar un aumento, llenarse. Hemos estado discutiendo antes de este punto básicamente lo que se conoce como arreglos fijos, que se plantean que una vez que llegan al final, una vez que están llenos de capacidad, no pasa nada más. Vas a tener que sobrescribir alguna duda, una subvención para eliminar algunos datos. De alguna manera se tiene que hacer un compromiso que va a tener que cumplir. No obstante, existe una especie de matriz que puede crecer con su programa, y esto se denomina matriz dinámica. Y entonces lo que vamos a discutir en esta conferencia es plantear dinámicamente cómo funcionan y algunos de los tiempos de corrida que podrían estar asociados con tal aumento. Entonces lo primero que necesitamos entender es que un lado y Ray se llena. Entonces digamos que tenemos en un rayo justo aquí y una vez que se llena de números o pieza de datos. Entonces tenemos, como, un tres aquí un dos, tal vez un 1 1007 ya sabes, no importa una vez que está lleno. Una vez que nuestro Ray aquí arriba está lleno lo que hacemos para sumar a eso. Muy bien, Entonces si nosotros, ya sabes, etiquetamos aquí abajo las ciertas las áreas aquí. Entonces tenemos la columna 01 234 La única otra forma que podemos sumar a esto es que tenemos que sobrescribir algo. Y si queremos sumar al final, entonces llegamos a un gran problema porque no podemos sumar al y no hay fin. Se va a decir, um, por ejemplo, si tienes un programa que solo incremente ID por uno cada vez, queríamos sumar al final. Una vez que lleguemos a este punto y tratamos de sumar al final una vez más, se va a conseguir una segunda caída. Vamos a tener algo como, ya sabes, um oh, tenemos que sumar hasta ex de cinco ahora es igual a siete. Eso no va a funcionar. Eso va a terminar en una falla de segue porque aquí no hay cinco. Aquí no hay cinco a la derecha, por lo que se va a tratar de tocar datos que no tenga la capacidad ni el conocimiento para tocar, lo que establecerá falla el programa. Se saldrá al aire y nunca se ejecutará. Entonces, ¿qué hacemos en esta situación? Lo que podemos hacer es que en realidad podemos aumentar dinámicamente el tamaño de la matriz. Ahora el problema es, es que una vez que se crea una matriz, se crea el tamaño. Si recuerdas, se creó de nuevo para tener una memoria , por ejemplo, teníamos un montón de segmentos y digamos en cada uno de estos segmentos creó esta matriz aquí mismo. Pero el problema es que este es segmento ya estaba asignado y después de esto fueron datos adicionales . Por lo que no puedes simplemente aumentar el tamaño de la matriz. Eso no funciona porque estarías anulando algunos otros datos quizá críticos del sistema por aquí. Y eso es un problema. No queremos estar haciendo eso. Entonces lo que se puede dio es en lugar de simplemente agregar al final, se puede hacer una nueva matriz y copiar toda la información por ahí una matriz nueva, más grande. Y así esa es la técnica común que se suele usar. Y así ahí. Sabes que hay un par de maneras diferentes de hacer esto. Digamos que en lugar de un cinco, array quería agregar uno hasta el final. Entonces ahora lo que tenemos que dio es crearnos en un raro aquí mismo. Digamos que es en lugar de cinco bigotes, seis grandes. Entonces está aquí. Aquí, aquí, aquí, Aquí estaba ese 123456 Ok, Y entonces así entonces copiamos sobre un dato. Entonces tenemos tres y esto aguanta el problema aquí ¿Es eso lo que tenemos para crear una nueva matriz? Porque de lo que acabamos de hablar, no podemos hacerlo más largo. Entonces tenemos que crear una nueva matriz, pero no hay aumento vacío. Ahora en realidad vamos a tener que entrar y agarrar cada pieza de datos y copiarla . Y así cuando hagamos eso, lo que va a terminar siendo es que vamos a tener que ir una transacción. Entonces un costo aquí es tres, luego un costo para obtener el costo 21 para obtener el costo 11 para obtener el costo 10 1 para obtener el siete y luego el inserto aquí. Entonces, por ejemplo, vamos a crear una inserción. Ahora crea ex de cinco. Dijimos que igual a siete. Y así conseguimos que siete insertados. Pero notarás que en lugar de la inserción normal hasta el final con la que estamos tratando, recuerda, de vuelta en todo esto, dentro a la espalda debe ser tiempo constante. Entonces el Ray dinámico el problema es, es que cuando intentamos insertar a la parte posterior de una matriz que ya estaba llena, agregamos una adicional, pero tomó tiempo. ¿ Por qué tardó en tiempo? Porque ahí en números aquí hay 12345 Así que en esta situación están en nuestro en igual cinco . Pero tuvimos que tomar. Agregamos uno a nuestros extremos con una R N se convirtió en seis, y se necesitaron seis operaciones para copiar todo. Y así imagina si esto fuera una matriz de, digamos, 100 de estos aquí mismo. Se necesitaría 100 operaciones para copiar todo sobre. Entonces eso significa directamente proporcional a cuántos números tenemos aquí. Qué maney dentro tenemos aquí. Eso es exactamente cuántos, um, operación va a tomar. Entonces en lugar de nuestro olor rápido primero, o son tiempo constante ya no es que este inserto realmente se convierte en o de tiempo final, y esto es un problema porque insertar en una carrera debe ser rápido. Esa es una de sus ventajas. No obstante, si llegamos al final de tiempo que algunas de nuestras otras opciones empiezan a volverse mucho más apetitosas, porque ya no tenemos inserciones instantáneas. Entonces, ¿qué nos dio? En realidad hay una manera de sortear esto. Hay una manera para que no tengas que hacer esta implementación para que no tengas que cambiarla de punta o hasta el final. Se puede mantener relativamente esto aquí mismo, y todo se reduce a algunos promedios. Entonces digamos que en lugar de hacerlo de la manera ingenua, que sería insertar una nueva caja cada vez. Entonces si necesitábamos seis, tomaríamos Insertaríamos una caja aquí al final, que hicimos justo aquí. Y si necesitábamos uno, creamos una matriz completamente nueva aquí abajo, y entonces tiene ya sabes, es B B 7 grande, y podríamos seguir haciendo eso. Pero todo lo que el tiempo que hacemos que sí se le debe el final, así que podemos hacer en su lugar debilitar hacer en su lugar es que es el doble del tamaño de la matriz ahora. Entonces si tienes una matriz que se ha creado, pasemos por el doble tipo de gráfico aquí. Entonces tienes una matriz. Ahora está lleno de uno. Ahora insertas hasta el final. Ahora, ahora lo duplicamos. Es demasiado de cuatro que ocho en 16 que 32 en 64 1 28 y así sucesivamente. Sube que le estamos haciendo a Exponential está aquí para hacer la X justo aquí arriba. Eso es lo que estamos haciendo aquí es cada vez que se llenan los cohetes, vamos a duplicar el tamaño de la matriz y la forma en que la razón por la que esto ayuda es porque si notan hay una menor cantidad de tiempo que tenemos que usar sobre el fin. Entonces, por ejemplo, verás que en cada uno de estos puntos, tiene que ser O hasta el final. Tenemos a ti. Tenemos que copiar sobre la totalidad de los datos de lo anterior. Tenemos que copiar sobre los datos anteriores en el nuevo. Pero también notan algo aquí es que hay una cantidad creciente de distancia entre cada uno de estos números. Cada vez más, cada vez es más largo, más largo y más largo, que significa que si no tenemos que redimensionarlo, no tenemos que cambiar el tamaño justo aquí o aquí aquí. Lo que significa entre por ejemplo, 65 65 a 1 27 No tenemos que redimensionarlo, lo que significa que todas esas operaciones un camino al uno porque solo estamos haciendo inserciones regulares en ese punto. Entonces eso es una especie de lo que esto de aquí abajo representa el de abajo justo aquí es Lo que estoy representando aquí es que estamos tomando este tamaño y en lugar de tenerlo cinco, lo estamos duplicando a 10. Por lo que ahora copiamos los datos aquí mismo y vamos a tres, 21 10 107 y a los siete. Y ahora, en lugar de tener que hacer sobre el final para las próximas cuatro operaciones, estos anuncios serán todos oh, al uno porque no tenemos que redimensionarlo debilitarse. Simplemente insertarlo como una matriz normal. Y así esta fue la O hasta el final. Y luego si lo traemos de vuelta, si miramos aquí arriba, podemos pensar en esto para que éste hubiera tenido que ser o hasta el final para insertar, y luego tuvo que duplicar. Por lo que éste hubiera estado fuera hasta el final. Pero entonces tenemos un spot de 02 con uno oh al uno y luego tendríamos un doble. Este era cinco. Deberían ser cuatro. Si lo estamos haciendo de esta manera, veremos que empieza a conseguir cada vez más cantidad de la O a los unos. ¿ Y por qué es tan importante esto? Porque eso significa que en lugar de que toda nuestra operación sea O hasta el final, realidad podemos crear en una especie de promedio. Entonces echemos un vistazo a este promedio. Entonces entramos aquí y pasemos por algún simulacro de creación aquí. Entonces tenemos un inserto 23456 Sólo voy a bajar la lista aquí mismo. Sólo vamos a crearnos aquí una pequeña mesa. De todas las inserciones posibles que podríamos hacer hasta cierto punto y empezarás a ver el patrón aquí, empezarás a entender por qué esto en realidad es realmente bueno hacerlo para duplicar la matriz dinámica , y subiremos hasta 25 aquí mismo. En realidad vamos a subir a 32 porque ese es uno de nuestros bits son uno de nuestros puntos dobles . De acuerdo, entonces cuando insertemos 12 aquí, va a ser una operación constante. Tenemos una matriz. Vamos a crear nuestro derecho y va a ser F talla uno. Entonces esto va a ser constante va a ser uno aquí mismo. Ahora, una vez que llegues a este punto, se correrá con el espacio, así que tuvimos que duplicarlo. Entonces ahora es demasiado grande. Entonces esto fue una oda a la operación en, que, en realidad, fue en realidad un no a la única operación porque sólo teníamos una pieza de datos que teníamos que transferir . Pero técnicamente es una oda al final, así que vamos a sentarnos sin ti ahí dentro. Ahora tenemos un espacio abierto aquí, Así que si solo piensas en esto, voy a dibujar el cuadro por aquí un poco al principio para una especie de ilustrar lo que estamos haciendo aquí. Entonces tuvimos un spot. El problema fue que queríamos insertar un 2do 1 No quedan manchas. Entonces lo que hicimos fue duplicar, copiar los datos. Entonces ahora ya hay suficientes manchas. Ahora queremos ir a tres. El problema es que cuando llegamos a tres, necesitamos duplicarlo nuevamente porque no hay plazas disponibles. Ahora vamos a duplicar otra vez, y vamos a llenar que la insulina va a ser otra O hasta el final. Pero ahora el número cuatro para llenar el cuarto puesto, es Está abierto, así que podemos simplemente ir al que no tenemos que hacer ninguna duplicación de este spot aquí mismo. El índice spot aquí está abierto, y así seguimos adelante, y notamos que cinco van a necesitar duplicarse porque hemos corrido en los spots para poder seguir adelante y duplicarlo de nuevo. Copia todos nuestros datos a la nueva matriz. Y así ahora sigamos adelante y eliminemos la ambigüedad ahí mismo. Y así ahora tenemos todos nuestros datos. Nuestros datos en este punto están llenando este y éste y éste éste éste y cinco, Y ahora, Y ahora, una vez que lleguemos a pelear. Para que esa cinco operación que nos llevó vaya hasta el final, y ahora Una vez que lleguemos a seis aquí arriba, podemos llenarla de inmediato. Entonces ir a la 17 es exacta misma manera sobre la una y son lugar tiene ocho lugares. Entonces es o hasta el final justo aquí o mi mal, mi mal. Sigue siendo uno más con uno porque sí tenemos un espacio abierto aquí con otro O al uno. Entonces ahora tenemos la totalidad de la matriz llena una vez más, esto es 12 12345678 Está lleno, y ahora tenemos que duplicar una vez más, así que lo duplicamos de nuevo. Y entonces ahora lo que tenemos que hacer es crear un no al en operación, y voy a seguir dibujándolo ahora porque ahora se puede ver un patrón. Aquí está así lo hemos duplicado. Y ahora está bien hasta 16 spots, así que podríamos salir con uno. Ah, el que tiene uno. Podemos seguir bajando a esto hasta que lleguemos a la siguiente doble parte. Y entonces ahora estamos a los 16. Entonces ahora se va al final, y luego vamos a seguir adelante Tiempo constante, tiempo constante, tiempo constante, tiempo constante, tiempo constante, tiempo constante, tiempo constante. Ya no voy a escribir Theo. Simplemente voy a arreglar los tiempos constantes constantes, constantes, constantes, constantes, constantes, constantes. Y luego hasta si hicimos 32 constante 33 in y así sucesivamente. Y entonces, ¿por qué es esto importante? Bueno, te darás cuenta al principio, teníamos un montón de operaciones O a la N. Pero después de eso se estaba volviendo cada vez menos así hasta el final. Y cada vez más cabaña de troncos o cada vez más, mawr tiempo constante. Nosotros, por ejemplo, aquí mismo Tenemos tres constantes que un tiempo lineal. Así se llama. Vamos a empezar a llamarlo lineal un tiempo lineal, luego un montón de tiempos constantes, un tiempo más magro que una cantidad extraordinaria de tiempos constantes que una vez. Y lo que sucede es con el tiempo estos tiempos constantes o estos no constantes estos tiempos lineales van a quedar superados en número. Se van a superar. Y eso es porque el hecho de que estamos duplicando en cada vez, así que cuando lo duplicamos, en realidad estamos creando un log ocurrencias rítmicas de O hasta el final. Entonces estamos creando una ocurrencia como esta se puede ver que leer. Al principio, tenemos un montón de deshacernos del principio. Tenemos un montón de diferentes. Va de, como, como, cero dedo del pie. 1234 llamadas de logueado. Pero después de eso, cinco llamadas están por aquí. Seis llama su camino por aquí. Siete llamadas está completamente fuera de la pantalla. Y así se pone cada vez menos con el tiempo. Y todo esto se reduce a una especie importante de, um, una realización importante. Y eso es dejadme seguir adelante y hacer algo aquí mismo. Y ese es el hecho de que si lo duplicamos cada vez que lo doblamos, lo que realmente estamos haciendo es que estamos creando log of en el tiempo, un log de un promedio de cuatro nuestros extremos, lo que significa que este tipo de se mete en algún poquito de un complicado Matthew. Entonces solo voy a decírtelo y sólo una especie de entenderlo. A lo mejor adjuntaremos un documento que entienda un poco más. Pero lo que pasa aquí es ese registro de fin, porque en está asociado a eso, porque nuestras llamadas, porque nuestras llamadas a porque nuestras llamadas a fin comienzan a entrar en un log de in. En realidad podemos bajar esto a tiempos constantes. El promedio se convierte en tiempo constante, lo que significa que el peor escenario general se convierte, para todos los propósitos intensos, tiempo constante. Ahora es un toque por encima del tiempo verdadero, constante, pero para fines relacionales compararlo con otras cosas podemos entender y debilitar. Y se cree muy ampliamente que este inserto se convierte en tiempo constante. Y así, a través de todo esto, solo se puede pensar en ello. Hay un par de maneras diferentes en las que se podría implementar una matriz dinámica, pero hay una forma muy eficiente de hacerlo. Y notarás que mucha informática tiene cosas como esta donde hay una forma muy eficiente de implementar estos diseños y estos patrones. Y hay una manera muy ineficiente. Y así en esta situación, duplicar en cada tiempo es muy suficiente en el hecho de que sale a tiempo constante todo el camino al final por este cambio rítmico log. Y por eso es comprensivo. El matemático es algo importante, porque a través de esto, Matthew podría entender que cuando creas este largo promedio de cadenas a lo largo del tiempo que tu operación realmente especie de promedios a tiempo constante, y que sería la forma más eficiente de hacerlo. Entonces eso es arrays dinámicos y un poco de la teoría detrás de ellos. Un poco de matemáticas detrás de ellos y sólo una especie de buena introducción a cómo funciona el aumento dinámico y cómo se podría crear una especie de tasa dinámica, que es solo crear una nueva y luego duplicar el tamaño y luego llenar todo el información en cada vez que duplica. Entonces esos son dinámicos elevan su realmente, realmente cool porque eliminan parte de esa limitación del tamaño del espacio teniendo que ser constante , y te permiten solo tener mucha clase de flexibilidad ah en tu programación. , 15. Revisión de Array de 2a 7: Por lo que hemos cubierto mucho sobre un aumento en apenas estas pasadas dos conferencias. Y así que un poco quería sólo dar un paso atrás y simplemente volver a repasar todo realmente rápido y especie de empate todo esto juntos en 11 video. Entonces vamos a estar simplemente yendo rápido. Lo que hemos aprendido en las lecciones anteriores una especie de re, ya sabes, re ilustrando lo que hemos aprendido y luego simplemente atar todos estos aspectos juntos para que realmente podamos tener una buena comprensión de un aumento, cómo funcionan lo que sus tiempos de carrera, etcétera. Entonces lo primero que tenemos que hacer es solo recordar cómo funciona la carrera. Entonces raise son solo un punto de datos dentro de nuestro disco duro o nuestro ram o algún otro punto de nuestra computadora. Y esos datos se introducen en un segmento cada vez que creamos una matriz apuntaban a la pieza de datos en su conjunto, y le estamos dando un nombre. Entonces, por ejemplo, tiene una dirección física, una dirección de computadora, pero podríamos estar simplemente declarándola como una variable como, digamos, X es igual a una matriz de lo que es una longitud de rango cinco. Y así en esta situación podríamos estar declarando nuestra matriz del nombre de X mientras en la charla de computadora. Es encontrar una dirección de lugar y memoria específicos, y luego una vez que llamemos a esa dirección, nos va a llevar luego a la matriz misma. Y la matriz tiene estos muchos nombres, que me gusta llamarlos, que son sólo el tipo de la parte de la matriz que queremos contactar. Y entonces así podemos contactar a todos estos y suelen ser como que podrían incluso ponerse en el extremo aquí mismo. Entonces esto podría ser cero etcétera. No obstante, la computadora hace ese tipo de fuera del alcance de este curso, Pero la computadora hará lo suyo para que podamos acceder a cada uno de estos puntos instantáneamente solo dándole su nombre completo. Y luego son muchos nombres. Entonces en esta situación, si quisiéramos, si llenamos la tasa sin pecado y de datos aquí, Entonces, por ejemplo, tenemos, ya sabes, sólo algunos números aquí, y queríamos agarrar un punto específico o un lugar específico aquí. Todo lo que tenemos que hacer es sólo darle el nombre y luego el mini nombre en esta situación, también. Y luego recuperaremos nuestros resultados. Entonces, por ejemplo, esto sería ajustarlo a 10 y luego recuperarlo, diríamos que simplemente lo llamaríamos y lo devolvería y nos daría 10 porque iría. Este es su nombre principal. Está agarrando su nombre melena. Se utiliza en su nombre muchos, y luego obtiene nuestra pieza de datos así y así un aumento también puede tener propiedades adicionales , la matriz en esta situación. Lo que estamos haciendo es que en realidad sólo vamos de una a otra a la siguiente, y lo estamos llamando arbitrariamente diciendo a Debería ser 10 3 debería ser 44. No obstante, si quieres añadir un poco más de un estilo una estructura a esto, podemos empezar a añadir a la parte trasera o añadir al frente y solo por sí mismo. En esta situación, empezamos a meternos en el problema donde si queremos sumar al frente, vamos a tener que tomar todos nuestros datos y cambiarlos hacia abajo por uno porque no hay manera que pudiéramos simplemente asociarnos. Pero este es el frente. Este es el fin. No podemos ir a uno negativo. Negativo es una falla de la SEC que no existe en nuestro programa. Entonces tendríamos que bajar todo. Y eso trae un problema para que podamos dio para arreglar eso. El problema es que podemos empezar a crear una especie de aspecto adicional honore. Entonces si queremos hacerlo circular, recuerda, recuerda, esto fue conferenciado a Si quieres hacerlo circular, solo agregamos un puntero frontal y un puntero posterior sobre él y esto emulará una matriz circular . Emulará este tipo de cosas donde la matriz es en realidad circular en que lo hará si quieres agregar al frente todo lo que tienes que hacer es mover una a la izquierda, saliendo hacia atrás. Todo lo que tienes que hacer es mover uno, o en esta situación, contrario a las agujas del reloj o en sentido horario. Si quieres sumar a la espalda y así podemos entonces mover estos punteros lo que hay en todo podemos entonces mover estos punteros de un área a la siguiente. Si así lo elegimos una vez añadimos un elemento aquí. Podríamos asociar la parte de atrás aquí. Podríamos asociar la espalda a justo aquí. Y luego podemos sumar a la espalda en tiempo instantáneo y sumar al frente y al tiempo instantáneo también . Pero entonces nos encontramos con el caso donde, por ejemplo, son array podría quedarse sin espacio. Entonces, por ejemplo, podríamos tener este derecho, y podría llegar a ser demasiado grande. Y así si nuestro rayo termina haciéndose demasiado grande, lo que en realidad podemos dio es que podemos seguir adelante cuando podemos duplicar su tamaño. Entonces esto lo convierte en una matriz dinámica, debilitar hacer realmente, alguna forma de hacerlo más grande? Podríamos hacerlo ir, por ejemplo, Um, sólo añadir uno hasta el final. Pero aprendimos que eso no lo hace eficiente. Eso en realidad lo hace realmente ineficiente. Entonces si tuviéramos una matriz de a, así podríamos duplicar el tamaño una vez que lleguemos a un punto inválido y podríamos convertirlo en un array de cuatro como este y seguiremos doblándolo arriba y arriba, y veremos que poco a poco se hará más grande y más grandes y más grandes para ajustarse a nuestros datos tiempo, a lo largo del tiempo, y esto nos permitirá crear una tabla o una matriz, que con el tiempo agrega una inserción del final de O de uno por promediar. Entonces tendremos un par de instancias estas instancias aquí mismo donde va a estar en donde va a ser un tiempo lineal en cada una de estas instancias, y eso solo llega al hecho de que tenemos que copiar todos nuestros contenidos de cada vez re tamaño lo. Tenemos que copiar nuestros contenidos de la A más antigua al nuevo rayo y luego agregar nuestro número adicional . Y así cada vez que tengamos que ampliar esto, vamos a terminar teniendo que copiarlo por todas partes, que va a estar en, um, procedimiento. Entonces va a ser un en trámite cada vez que tengamos que hacer eso. Pero si lo duplicamos cada vez que esto en procedimiento se vuelve cada vez menos común hasta que sube un punto infinito en el que básicamente se convierte, vamos a tener que redimensionarlo. Vamos a tener que usar las casi cero veces así que pensando si vamos al infinito en algún momento, va a haber un tiempo en el que estamos usando,ya sabes, ya sabes, un 1,000.000.000 de operaciones constantes y luego una en operación. Y si tomas uno y lo divides por un mil 000.000.000 obtienes un número que es tan pequeño que bien podría ser cero. Y por eso, promedia que los extremos como van al infinito, extremos aquí como van al infinito, realidad terminan convirtiéndose en cero, y se vuelven básicamente inútiles. Ya no los miramos. Entonces sólo miramos el que tipo de uno fuera, y ese es el uso constante del tiempo constante. Entonces si duplicamos nuestro aumento A cada vez que se quedan sin datos, podemos conseguir un inserto de tiempo constante a la parte posterior, y eso hace que nuestro programa sea mucho más eficiente. Entonces eso es sólo una especie de análisis de lo que hemos estado cubriendo en estas últimas conferencias sobre un raise, cómo podrías hacerlos circulares, cómo podrías hacerlos dinámicos, y en algunos de los tiempos asociarte con cada de estos rayos. Entonces esto va a estar probando una especie de estos datos en el siguiente tipo de lección, donde en realidad estamos haciendo un pequeño quiz aquí de sólo una especie de asegurarnos de que todo esto esté cementado en sus mentes y usted entiende al menos lo básico. No tienes que entender todo esto al 100%. Muchos científicos informáticos no entienden todo este asunto al 100%. Nosotros sólo queremos tener una buena comprensión de ello para que si nos olvidamos de algo, podamos ir a buscarlo. Y tenemos una base suficientemente buena para entender lo que no entendemos. Si eso tiene sentido, entendemos la parte de que estamos teniendo problemas para mirar hacia arriba. Y si sólo entendemos un poquito, si tenemos una base que podamos continuar nuestro aprendizaje. Me emociona que hayamos llegado tan lejos que chicos hemos empezado a aprender tu primera estructura de datos en un aumento, y no puedo esperar a verte en la siguiente unidad donde vamos a estar discutiendo listasenlazadas listas 16. 2-8 de la de los ejemplos de mundo real: Ahora que tenemos una buena comprensión de un raise y cómo funcionan teóricamente, veamos algunos ejemplos del mundo real de dónde podríamos haber interactuado con una matriz sin siquiera saberlo. El ejemplo más común, o algo que se usa muy comúnmente es en nuestros smartphones. Ah, muchas veces tanto las listas aquí como el tipo del diseño de APP están todas basadas en array. Entonces lo que hacen es una tormenta en un aumento. Y cada vez que haces clic en esto, llama al comando cualquiera que sea la matriz que tengas. Entonces, por ejemplo, vamos a tener esta cuadrícula por aquí a la derecha. Se puede ver que tenemos 12345678 todo el camino hacia abajo. Y esta es la matriz. Los números en cada uno de estos se almacenan en una de estas matrices. Entonces, ¿qué hemos dado click en un botón? Entonces, por ejemplo, si hacemos clic en la tarifa de Facebook aquí, que se alina con el número 10 va a ir en la matriz y buscar el comando a las 10 . Una vez que vea que el comando a las 10 está abierto Facebook, abrirá Facebook, y haremos lo mismo con si tuviéramos 15. Se irá a volver arriba. Teníamos 19. Se irá a etcétera local, etcétera. Entonces lo que hace es cuando lo construye, crea una matriz con un montón de referencias de lo que debería abrir. Y estos rayos también tienen otra información. ¿ Al igual que qué? El icono deben ser los colores. Ya sabes, um, y otro tipo de información que funcionaría con cada uno de estos, el nombre de la APP, cosas así. Y luego cada vez que hacemos clic en él, entra y encuentra la pieza real de software para abrirse cada vez que hacemos clic en él. Y por aquí también tenemos una lista. Muchas veces estas se crean con un aumento, por lo que tendrás la matriz de cuentas, que tendrá un montón de cosas diferentes aquí. Y entonces tendrás la matriz general que tendrá un montón de propiedades diferentes aquí también. El motivo por el que funcionan los arreglos. El mejor aquí es por lo instantáneos que son. Entonces cuando hacemos clic en 18 no queremos ningún rezago entre esto. Y si hacemos clic en una, vamos a aprender sobre otra estructura de datos en la siguiente lección, que tarda más tiempo cuanto más abajo vayas. Entonces, por ejemplo, si hubiera 45 APS, no queremos que el número 45 tome más tiempo que el número uno. Nosotros los queremos a todos al instante. Lo mismo con por aquí cuando hacemos click en algo, queríamos ser exactamente el mismo tiempo. Y, como hemos estado hablando de un aumento, tener esa habilidad. Se puede llamar al array de dos o cuatro o 10 y obtener ese elemento instantáneamente, y por eso son tan importantes. Y son muy clave para usar. Si quieres ver cuáles podrían ser algunas de las convocatorias para un aumento en diferentes idiomas, realidad hay un artículo de Wikipedia realmente necesario al respecto. Pero hay esta mesa impresionante aquí y se pueden ver todos estos lenguajes, y cada uno de ellos tiene una matriz de alguna manera, forma o forma. Aquí está una especie de los grandes jugadores en programación justo aquí lo tienes sabes, tu ruby, tu python, tu javascript, Java C C plus así que realmente, los grandes jugadores en el mercado y todos se llaman con el nombre de la matriz y en el número de índice Entonces, por ejemplo, esto podría ser matriz AP, y luego esto es Index 10. Entonces esta sería una llamada de APP Array 10 y llamaría a todo dentro de esto, así que esa es solo una especie de forma interesante de mirarlo. Se puede ver que a pesar de que todos estos lenguajes son tan diferentes unos de otros, si todos usan un raise en alguna forma, o alguna forma otro uso común de un raise con bases de datos con bases de datos realmente, realmente grandes, ocasiones no se almacenan en un aumento, sus almacenados en modales ligeramente diferentes, como árboles o cosas así. Sólo porque una vez que tienes una matriz tan grande, te gustan los miles de millones, se pone un poco tedioso y se tiene que almacenar mucho ram si querías almacenar todos esos instantáneos. Entonces lo que hacen es crear cosas que son casi instantáneas pero que tardarán un poco más de tiempo. Pero eso es para una especie de explicaciones posteriores. Esto, sin embargo, es lo que en un rayo podría verse. Si tienes una más pequeña o incluso solo tablas dentro de una base de datos, estarán usando un aumento. Entonces, por ejemplo, si quisiéramos ordenar por utensilios de cocina, podríamos agarrar todos los que igualan los utensilios de cocina y luego simplemente volver a llamar. Will podría hacer tal vez una lista de todos esos números, y luego lo pasamos a una función, y luego simplemente llama a todos esos números. Entonces, por ejemplo, para estar en nuestra lista y luego 13 y 14 estarán en nuestra lista. Y cuando llamamos al 13 14 pudimos construir otra lista con solo utensilios de cocina para poder filtrar esta lista. Las matrices también se utilizan comúnmente en la Web. Este es en realidad uno de mis sitios web que tengo, y esto está usando WordPress. Pero con la parte ordenada al respecto es que he pasado por el código y cada parte de éstos realidad está usando una matriz en alguna forma o forma básicamente lo que hace que llama a todos los artículos como una matriz. Y los coloca aquí al igual que nuestro ejemplo de aplicación anterior. Y cada vez que haces clic en uno de estos, llama a las funciones, los nombres que todo lo que viene con él, y como que pasa por eso. Por lo que esta páginas Web Facebook, Twitter todos usan un aumento en alguna forma o forma para mostrar los datos. Y luego también, quería mostrar algo del código back-end aquí. Entonces esto es en realidad algún código de, um, el sitio web, y esta cosa es muy, muy compleja. Ni siquiera lo entiendo tan bien. Se tarda un poco el campo para simplemente saltar aquí y empezar a entender las cosas. Pero una de las partes aseadas es que se podía ver justo aquí. Este es un formulario de comentarios en WordPress. Se construye en array. Crea una matriz de toda la información que recoge del comentario. Y se usa aquí mismo. Se puede ver. El array se declara justo aquí. Y en realidad hay Honore aquí abajo y array aquí arriba. Hay rayos de en un aumento en una carrera. Como dije, realmente, realmente complejo. Este código es una especie de galimatías, a menos que realmente lo mires y pases horas y horas analizándolo . Pero sólo quería mostrarles que una matriz está presente en todo esto también. Entonces en cualquier lugar que mires eso tiene que ver con codificar un aumento nuestro ahí presentes y se están utilizando un aumento son casi los más. Hazlo si no la estructura de datos más utilizada por ahí. Entonces entenderlos realmente bien y luego entender algunos de sus beneficios como si fueran tiempo de ejecución rápido te demostrará por qué se usan en el mundo real tan a menudo. 17. 3-1 nodos: Entonces, antes de entrar en listas enlazadas, necesitamos entender de qué se compone la lista enlazada de qué están hechas? Y así vamos a estar hablando es de lo que están hechos. Y ahí se llaman nodos. Entonces, ¿qué es exactamente una nota? Una nota es realmente solo un objeto locacional. Se trata de un objeto que hace referencia a otros objetos, y por lo que podría ser un poco una definición confusa. Entonces vamos a seguir adelante y especie de escribir esto. Vamos a ilustrar qué es una nota. Por lo que estas cajas de aquí abajo, estas dos cajas en la parte inferior esta izquierda en esta derecha thes se contarían nuestros nodos. Y aquí arriba tenemos memoria. Por lo que podrían ser una matriz. Podría ser Ram. Podría ser realmente cualquier tipo de memoria aquí arriba, pero lo que sé que hace es que toma que tiene un montón de propiedades diferentes al respecto. Entonces, por ejemplo, podría tener, um, vamos con, como por lo general tiene una propiedad de datos. Entonces esa es la propiedad importante. Por ejemplo, podría tener una pieza de datos así, y tal vez ésta tenga una pieza de datos fuera así, pero normalmente no están dentro de la nota porque se supone que esto es como un objeto locacional. Entonces, lo que realmente hace el nodo es que tiene un spot para los datos en la parte superior, y luego tiene otro tipo de características de la parte inferior, que vamos a ir por aquí en un segundo. Y esta parte superior de los datos, en realidad contiene la dirección a un punto de memoria. Entonces, por ejemplo, digamos en nuestra memoria, aquí tenemos, um tenemos estas áreas y esto no es una matriz estas o simplemente lo hicieron, ya sabes, hay memoria adicionalmente por aquí y por aquí y estos aires apenas puntos reales en la memoria. Entonces, como este es F cero. Este es F uno. Este es F dos, y éste es F tres. Y entonces qué? En realidad está almacenando aquí, es que almacena la ubicación de los datos para que no tenga que estar en orden. Por ejemplo, este podría almacenar cero x f tres. Por lo que tiene un puntero que básicamente lo señala a esta pieza de datos. Bueno, este de aquí quizá podría almacenar cero x f uno Y así va a tener eso significa que Pointer está justo aquí. Y así ahora siempre que queramos nuestros datos cada vez que uno nuestros datos de nuestro nodo. Entonces si queremos los datos de los nodos, lo que podemos hacer es solo podríamos llamar al nodo, y luego como se llame su parte de datos y nos va a dar va a ir y hacer el trabajo por nosotros. Lo encontrará y luego lo devolverá para nosotros. Y así la parte importante sobre los nodos y la razón por la que se usan con tanta frecuencia es porque tienen otra característica especial. Y voy a usar este fondo galaxia Penda mostrar esta característica, y ese es el hecho de que tienen la capacidad de conectarse entre sí. Entonces, por ejemplo, podríamos decir eso Bueno, digamos que tenemos un estrecho entrando aquí y tenemos una flecha saliendo aquí. Podríamos tener tal vez aquí algo así como un siguiente, por lo que podríamos tener una siguiente parte de cada uno de estos nodos. Podríamos tener una parte previa a uno de estos nodos y estos realmente pueden ser cualquier cosa. Este podría ser el frente. Nos salimos de frente en uno de estos lados que siempre apuntará al frente. Podríamos tenerlo siempre apuntando a la parte de atrás. Podríamos haber apuntado siempre a ubicaciones específicas, pero una técnica común es el tenerlo anterior y frente. Y así vamos a seguir adelante y justo a la derecha que un poco claro anterior, siguiente. Y así cada uno de estos tiene anterior y siguiente. Y entonces lo que pasa es que se lo contemos. dónde debe ir el siguiente cuando podamos apuntar a otro nodo? Y en esta situación, podríamos apuntar a una nota anterior, y este nodo anterior podría apuntar en esta dirección hacia atrás como así déjame. Ese fue un mal aire. Déjame leer tu toda esa flecha para que pudiera apuntar hacia atrás así Y entonces ésta podría apuntar hacia adelante, que está justo ahí, y podría tener una flecha que en realidad apunta hacia atrás hacia ella, como así. Y así lo que esto hace es que crea una lista enlazada, y entonces eso es lo que estaremos discutiendo es que estamos usando estos tipos estos nodos aquí mismo para crear listas enlazadas, y así vamos a repasar exactamente por qué las listas enlazadas son importantes cómo nos ayudan, Um, y cómo ellos, ya sabes, se comparan con otras cosas, como la matriz de la que ya hemos hablado. Por lo que en este tipo de conferencias del tipo de unidad iban a estar discutiendo listas enlazadas. 18. Lista de 3-2: Entonces ahora que tenemos una buena idea de cómo funcionan los nodos, investiguemos un poco más y pongámonos detrás de la intuición de las listas enlazadas. Entonces, qué lista enlazada es lo que describí en la última conferencia donde tienes un montón de estas nariz pequeña. Entonces, por ejemplo, podríamos tener un montón de esos. Es decir, estas cosas podrían ser infinitas, así que podríamos tener una nota aquí. Una nota aquí, una nota aquí, una nota aquí, nota aquí, y nuevo lo hace y así sucesivamente. Y la taquigrafía para especie de dibujo estos está dentro va a ser el punto de datos. Y si apunta a algún otro lugar, solo dibujas una flecha. Entonces lo que tenemos aquí es que tenemos un montón de diferentes ubicaciones aleatorias en la memoria que están todas vinculadas entre sí por estos punteros. Entonces estamos en una matriz. Lo teníamos todo en el espacio lineal. Honore, por ejemplo, teníamos en una matriz. Lo teníamos todo en, como un espacio lineal donde era uno tras otro. Entonces eso sería como 34 10 12 y luego 11 aquí mismo, donde teníamos uno Después de la siguiente en, en uno de estos tipos de en una lista enlazada, lo que vas a tener es que van a estar por todos lados de la memoria. Entonces éste podría estar en alguna parte. Al igual que, por ejemplo, estos cuatro podrían ser, ya sabes, aquí abajo mientras este 10 se termina en alguna otra pieza de memoria y este 12 no es alguna otra pieza de memoria y así sucesivamente. Entonces lo que una lista vinculada te vive dio es que te permite conectar datos por todo el lugar juntos. Y entonces lo que esto te da la capacidad de dio es que te da la habilidad. Adelante y deshacernos de esto. Te da la capacidad de realmente agregar continuamente a la lista de longitud sin tener que hacer cosas como la expansión o duplicarla. Y si lo piensas cuando estamos hablando de la matriz, cómo se tuvo que duplicar cada vez para ser eficiente cuando se hizo más grande, muchas veces podríamos encontrarnos con un caso donde solo la mitad de la matriz está llena, lo que significa que tenemos todos sus otra habitación sobre la otra mitad. Eso no está lleno, lo cual es ineficiente. Estamos desperdiciando espacio. Solo está siendo Está a la espera de ser asignado, pero no está asignado. Por lo que la lista enlazada en realidad nos permite tener siempre y constantemente, um la memoria que se necesita para mantener nuestra lista y ni más ni menos. Entonces si necesitamos agregar un número a esto, podemos agregarlo hasta el final. Entonces, por ejemplo, si quisiéramos sumar ah, cuatro a esto, podríamos ir. Y luego simplemente vamos al final y agregamos antes a la lista justo aquí y de lo que estoy hablando aquí mismo son listas enlazadas de Singley. Y lo que eso significa es que tienes un punto de partida, ¿ verdad? Al igual Y así esto se marca como inicio la nota de inicio. Entonces cuando llamas a inicio, vas aquí. Y lo que va a dio es que vas a ir de aquí y vas a básicamente sólo la única manera que puedes atravesar es ir de aquí a aquí, de aquí a aquí, aquí a aquí y sólo siguiendo las flechas una tras la siguiente, todo el camino hasta llegar a la última y luego a ésta la forma en que sabes que estás al final es porque en lugar de éste apuntando a otro nodo, Entonces en esta situación, como por ejemplo, podría apuntar a, podría apuntar a otro nodo aquí. Digamos que este es como un cinco, pero si estamos al final de una lista, va a apuntar a algo llamado No. Y lo que no significa es que no es nada. Está apuntando a nada. No hay memoria asignada. En realidad no tiene una ubicación en la memoria. Está apuntando a nada. Y una vez que entendemos eso, estamos en nada. Entonces cuando insertamos algo, simplemente reemplazamos ese nada con nuestro nuevo nodo. Por lo que hemos creado esta pequeña nota aquí. Es como, por ejemplo, permítanme mostrarles cómo podríamos hacer esto. Hemos creado un nuevo nodo, un nuevo saber aquí abajo llamado 15 y queremos adjuntarlo a esta lista enlazada. Y así en este momento este apunta al No. Y entonces lo que queremos hacer es ganar. Adjuntar esto a ella. Entonces vamos a ir a este inicio. Íbamos a ir al inicio. Voy a bajar, son lista enlazada. Tiene algo. Tiene algo. Tiene algo. Tiene algo. Ah, es que saber. Entonces lo vamos a hacer es vamos a mover esto. No, vamos a Vamos a seleccionar esto. Saquemos esto de aquí para que sea una especie de Vamos a agarrar esto. No, vamos a sacarlo de aquí, y en realidad vamos a agarrar el nuevo nodo aquí mismo, y vamos a dejarlo caer y este nuevo nodo por defecto. Cuando creamos el nodo, es el siguiente spot estaba configurado para saber. Entonces por defecto cuando este aviso creó el siguiente pero dijo saber y verás que esto ayuda porque ahora cuando realmente seleccionamos esto y lo agarramos y lo movemos aquí arriba, notarás que el final nuevamente apunta a saber. Y este ahora se reasignó para apuntar al nuevo nodo. Y el ciclo continúa. Si queremos insertar otro, podemos seguir adelante y 13 aquí, y creamos esto. De forma automática pone a saber que no está en nuestra lista en, ya sabes, sólo todavía. Todavía se está creando. Ahora queremos agregarla a la lista. Entonces cuando vamos al inicio, bajamos, bajamos , bajamos Ahora éste no es un no. Entonces como OK, hay otro. Aquí vamos al 15. Eran como, Oh, no hay aquí. Lo que significa que ahora vamos a hacer 15 en lugar de señalar para saber que entonces vamos a mover su puntero. Entonces vamos a eliminar el no fuera aquí, y vamos a mover su puntero 2.2, nuestro nuevo nodo. Entonces técnicamente, haría esto porque el nodo en realidad no se movería aquí. Sólo le decían que señalara este nuevo pedido que creáramos este nuevo activo aquí mismo esta nueva, esta nueva pieza de datos que creamos y luego como ya creamos para tener ya un nulo del fin una vez que se vaya a escuchar, se moverá al knoll. Y ahora, si queremos contestar algo más, se va a mover derecho a este punto y podemos conseguir, ya sabes, tener un buen tipo de gráfico yendo. Ahora. Entonces, ¿qué pasa si quisiéramos, Por ejemplo, um, eliminar algo de esto en una matriz cuando eliminamos algo de ella. Todo lo que teníamos que hacer era por ejemplo, vamos a tener una matriz aquí mismo. Todo lo que tenemos que hacer es llamar a la ubicación que queremos eliminar. Entonces al 321012 podríamos simplemente llamar a X de dos iguales a ningún o entra en juego algún tipo de algoritmo de eliminación . Y yo era todo lo que hace es que sólo va, Oh, salida a Ya no iguala nada hecho. Nada de qué preocuparse Si queríamos liderar el 1er 1 Fácil hecho. Nada de qué preocuparse con lista de enlaces. No obstante te das cuenta de que hay dependencias de cotización unquote si eliminas si solo eliminamos . Si dijimos que queríamos eliminar 10 era un delete 10 justo aquí. ¿ Qué pasa? Cómo diablos se supone que vamos a llegar al resto de nuestra lista por ya no apunta a nada por solo automáticamente se quedó incumplida a señalar a saber. Por lo que apunta a saber ahora porque 10 está ahí dentro, lo que significa que este no es el fin, y perdemos el resto de nuestra lista aquí mismo. Entonces en realidad tenemos que hacer un poco de un tipo complejo de operación para eliminar déjame simplemente traer esto de vuelta. Entonces borra en cambio lo que podemos dio. Digamos que aquí tenemos un nodo. Una nota aquí mismo y una nota en medio. Tenemos el Singley apuntó los punteros sencillos punteros puntuales. Por lo que aquí es la lista de Liga Singley. Y si quisiéramos eliminar esto les dará todos estos valores para que podamos llamarlos por algo. Si quisiéramos eliminar 10 aquí mismo. Lo que tenemos que hacer es, antes de borrar esto, tenemos que decirle Hey, tres ahora va a apuntar a gustar asi que tenemos que ir a tres. Vamos a borrar el siguiente. Entonces vamos a tres y lo decimos, Hey, Hey, necesitas 2.22 Y luego una vez que se cree esta nueva asignación, ésta en realidad naturalmente simplemente caerá. Ahora es mala práctica. Simplemente deja esto aquí porque esto en realidad sigue siendo un sonido técnicamente. Entonces, por ejemplo, de esto es un inicio, esta gráfica aquí mismo sigue siendo técnicamente sólida. Se va a ir de 3 a 2 y luego por aquí apunta a saber. Y así todo esto aún funciona sigue siendo técnicamente correcto. No obstante, lo que tenemos es que aquí hemos desperdiciado espacio. En realidad no borramos el no. modo que en realidad podemos, antes de hacer eso, en realidad podemos guardar esto en algún tipo de variable como antes. Como podríamos decir, ya sabes, um, han usado Excel. Carrera irá w igual a esta nota de 10. Y luego una vez que volvamos a hacer esta cosa que podemos decir, ya sabes, podemos llamar a borrar sobre ella y en realidad lo estamos quitando de la memoria para que ya no tengamos esta cosa aquí sentada. Pero lo que quería mostrar es que todo lo que tenemos que hacer para eliminarlo es en lugar de eliminar el activo en sí, todo lo que tenemos que hacer es volver a dibujar la flecha. Y en realidad, técnicamente, éste seguiría señalando ahí. Entonces tenemos que hacer es redibujar la nota sobre así y entonces ésta está técnicamente fuera de la lista. No hay forma de volver nunca a 10. No hay forma de ir accidentalmente al 10. Es solo escalofriante ahí, y siempre puede estar ahí, y nuestra lista seguiría siendo sólida. No obstante, la forma eficiente sería entonces eliminar esto para que nuestra lista no esté almacenando datos adicionales que no necesite almacenar. Y así tenemos un caso más para cubrir cómo funciona la lista enlazada, y eso va a ser sobre cómo exactamente uno podría cómo exactamente uno podría insertarse en medio de un rayo. Entonces, por ejemplo, lo que hacemos aquí es, digamos, son el medio de una lista enlazada. Entonces si quisieras insertar en una matriz, di su tasa así en un rayo aquí, ¿qué? Y tenemos un dos aquí tenemos un siete aquí. Tenemos un cuatro aquí, y ya sabes, tenemos 0123 Y si queríamos insertar justo en esta parte de aquí, todo lo que tenemos que hacer es ex de dos igual a siete y ya sabes, va a siete Realmente fácil de hacer. Si desea insertar en cualquier otro lugar. Eso de verdad tienes que hacer es simplemente sobrescribir algo. Entonces si solo queremos que esto sea igual a cero, sólo podemos seguir adelante. Simplemente sobrescribirá esto y lo hará igual a cero. No riel, Otras cosas adicionales necesarias. No obstante, un rayo o listas enlazadas no son tan fáciles con una lista vinculada. Lo que tenemos que dio es que realmente tenemos que hacerlo. En realidad tenemos que especie de reasignar o re puntos y cosas. Entonces al igual que en la élite, teníamos una caja aquí de tres. Se traslada a 10. Y entonces digamos que éste pasa a 25 ahora tenemos una caja aquí tenemos una caja que creamos un nuevo nodo que creamos que tal vez 18 y apunta a saber. Entonces, ¿cómo hacemos que se vaya aquí mismo? ¿ Cómo lo ponemos ahí mismo? ¿ Cómo hacemos que vaya ahí mismo? Bueno, no podemos simplemente insertar. No podemos simplemente llamar al segundo spot. Diga, inserte, no hay los Punteros se van a poner todo en mal estado. Entonces lo que tenemos que hacer es llevarnos este aquí mismo. Tenemos que borrarlo. Tenemos que decirlo ahora apunta ahora apunta a la baja a 18 y después tenemos que tomar este . Tenemos que crear un nuevo puntero que apunte hasta 10 y hay un par de pequeños retos con esto. Porque si notarás algo si volvemos a donde empezó Si eliminamos si primero eliminamos esto, entonces de repente hemos perdido el resto de nuestra lista. No hay manera de llegar al resto de nuestra lista por aquí. Ya no podemos tocar. Entonces lo que tenemos que hacer normalmente es que tenemos que guardar este siguiente, éste de aquí, en una variable. Entonces, um, lo que no pudimos hacer, hay un par en realidad, formas en que podemos hacer esto. El más eficiente en realidad probablemente sería simplemente establecer primero el siguiente de éste. Entonces una vez que llegamos a una vez que tenemos este spot en la memoria, una vez que hemos atravesado son lista enlazada. Y hemos llegado a esta nota por aquí. Debilitar No dijo, Oye, queremos que 18 sean iguales a esto. No, queríamos señalar esta nota. Queríamos señalar esta nota. Entonces podemos dio es que podemos decir esto ahora apunta a esta nota también. Y entonces ahora lo que podemos hacer es que podamos volver al principio aquí. Podemos borrar esto, y ahora podemos apuntar esto hacia abajo. Ahora podemos apuntar esto a R 18 y luego ahora tenemos una buena inserción y no perdimos los datos en el back end. Por lo que las listas enlazadas ahí un poco complicado ahí un poco difícil de entender. Pero sí tienen algunos beneficios, y uno de los mayores beneficios es el hecho de que podemos seguir sumando al final. Y sólo va a crear datos. Eso es como, um que crean datos. Eso es, ya sabes, grande que necesitemos que sea, no tenemos que seguir duplicando cosas y nos permite una especie de anuncio a capricho. Podríamos simplemente agregarlo al final. No tenemos que preocuparnos por la clasificación ni la organización de la misma, y no sobrescribamos las cosas si vamos a insertar nosotros todo lo que es propio pedazo de datos que podemos agarrar y movernos en lugar de tener una matriz donde todo es una especie de encerrado en una caja que especie de limita algunas de las cosas que podríamos hacer con ella, sobre todo más adelante. Y lo que también es algo interesante de este enfoque es que una sola lista a enlazada en sí misma está, ya sabes, solo ligada de manera individual. Pero podríamos, por ejemplo, tener Ramos de nariz señalando a diferentes áreas. Y esto permite tantas cosas. Y aquí es en realidad donde nos metemos en los árboles más adelante, agregando manojo las notas. Pero esto es una especie de los fundamentos de la misma pueden estar vinculados lista por sí mismos. Tan solo de manera individual. La lista enlazada no es lo más útil, pero va a estar construyendo en cosas realmente útiles más adelante. Entonces eso son las listas de longitud Singley. La siguiente parte. Vamos a pasar a vincularlos doblemente y luego una especie de entender los tiempos de ejecución detrás de todo esto y cómo se compara con algo así como array. 19. de 3-3 tiempos de ejecución de la lista: Ahora tenemos una buena comprensión intuitiva de cómo funcionan las listas enlazadas. Vayamos por ahí. Tiempos de ejecución Probablemente dijo en informática, los tiempos de ejecución son importantes porque nos permiten analizar estas estructuras de datos y comprender sus fortalezas y debilidades. Entonces tomemos un rápido refresco sobre los tiempos de carrera de nuestro rayo aquí mismo. Entonces lo que tenemos aquí es que tenemos los tiempos de ejecución que salimos para la matriz y así que solo pondré eso aquí abajo. Esto es para la matriz. Y luego también, quiero designar Esto es para borrado aleatorio. Si estás eliminando, por ejemplo, en una matriz, um, al principio, como, por ejemplo, es una matriz circular desconocida y eliminaste el principio justo aquí. Por lo que borras este y quieres que todo se mueva hacia atrás que también se ove en igual que el en especie del frente. Por lo que este es éste podría ser dos diferentes, dependiendo de cómo quieras mirarlo. Pero borrar aleatorio siempre va a ser sobre el mientras borrar. Básicamente, frente de ladrones se le adeudará hasta el final. Entonces solo quería poner esa pequeña salvedad ahí sola, este tipo de complejidades del tiempo se pueden conseguir un poco de exactamente qué estás mirando, como específicamente Así podrían ponerse un poco confusas en ese aspecto. Pero si realmente solo piensas en ellos intuitivamente puedes entender. Entonces, por ejemplo, en la matriz, si estamos eliminando fuera de la tarifa frontal aquí, todo tiene que retroceder. Entonces tenemos que movernos en número de, um, en número de lugares en el peor. Y vamos sólo tipo de la intuición detrás de eso. Pero podemos ver algunas de estas cosas aquí. Nos dieron la inserción al azar. Nos metimos en búsqueda al frente. Eliminar búsqueda, búsqueda sin clasificar ordenada. Entonces, pasemos por estas operaciones en una lista enlazada. Por lo tanto, vamos a crear un poco de una lista enlazada de ejemplo aquí. Entonces lo que necesitamos crear es que necesitamos crear nuestros nodos. Entonces tenemos el inicio de la lista, que podemos simplemente crear como me gusta, empezar justo aquí para que pudiéramos crear, como Start, y luego apunta al inicio de nuestro primer nodo. Digamos que nuestra primera nota tiene un tres, y luego esta es una lista de enlaces únicos. Todavía no hemos hablado de doble, así que sólo vamos a ir con lista de longitud única. Yo doble sólo mejora pequeños trozos de cosas, cálculos leves, y luego vamos a ir a, como, digamos, 19 aquí o algo así, y entonces este es el final. Entonces esa es una, entonces apunta a saber por aquí. De acuerdo, así que tenemos son listas enlazadas como así, y vamos a seguir adelante y crear nuestro 1er 1 Así que aquí arriba teníamos insertar al azar. Entonces si quieres insertar algo y esto es aleatoriamente así en cualquier lugar dentro de la estructura de datos , en realidad hagamos lo mismo. La notación también es la última. Por lo que queremos insertar aleatoriamente en una matriz que nos llevó tiempo instantáneo porque estaríamos anulando las cosas si estuvieras tratando de calcular la anulación. Entonces tal vez podrías tener algunas adversidades en esto, pero si solo íbamos a sobrescribir algo perfectamente bien, podrías decir ex de cinco es igual a algún número lo que sea, y lo anulará en una lista enlazada. No obstante se convierte en un problema es que sólo se puede entrar desde aquí. No se puede simplemente saltar a cualquiera de estas posiciones. Entonces si quisiera llegar a 19 por aquí, tendría que ir desde el principio más de 123 y luego llegar a él, y tendría que hacer esto por cualquier cantidad dentro de esto. Entonces lo que eso significa es que nuestro inserto aleatorio en realidad se reduce a en O de en notación. Y eso se debe a que nuestro peor escenario de casos está insertando aleatoriamente en la parte de atrás. Lo que significa que va a insertar 1234 están en. Esta situación es de cuatro. Por lo que van a tomar cuatro para volver a aquí, y eso va con cualquier lista de cualquier longitud. Ahí hay 1000 de estos y quieres insertar cerca de la parte trasera. Podría tomar 950 a 1000. Entonces eso significa que nuestro peor escenario para insertar aleatorio en realidad se convierte en O de N. Y eso es sólo porque no hay acceso instantáneo. No hay manera de que sepamos saltar entre estos más rápido que ir desde el inicio y luego moviéndonos hacia abajo como así y así nuestro siguiente se va a insertar en el frente, así que inserte frente y delante, así que con inserto frontal y voluntad hacer insertar de nuevo también con un básico, um, una lista básica vinculada. Va a ser o hasta el final también. O en realidad, la respuesta al frente va a ser un tiempo constante. Bueno, al empezar, la espalda va a ser O hasta el final. Y esto es porque vamos con insertar primero el frente. Si queríamos insertar un nuevo nodo, digamos que aquí tenemos una nota. Una nueva nota aquí de cuatro. Si quisiéramos insertar esto en el frente, ¿cómo exactamente haríamos eso? Bueno, en realidad es bastante fácil. Sea cual sea nuestro frente, sea cual sea nuestro puntero, todo lo que tenemos que dio es que sólo tenemos que decir OK, en lugar de apuntar a este punto a este uno, y luego tuvimos que poner cuatro a nuestro viejo. Por lo que tuve que poner cuatro a nuestro viejo frente. Y entonces lo que eso hace es que en realidad solo lo agregará en 123 pasos cada vez, no importa lo que estés insertando ahí, por lo que siempre va a ser un tiempo constante y la forma en que realmente quieres hacer esto. En realidad hay una forma que debes insertar aquí porque este tipo de entra con perder memoria. Si elimino esto y luego hago este punto a esto así pierdo la habilidad pierdo esta primera nota aquí, ya no tengo habilitada para agarrarlo ya porque borramos el único punto que tenemos al mismo. Entonces si quieres insertar en el frente, lo que tenemos que hacer es tomar nuestro nodo. Tenemos el primero lo dijo a los tres. Y así esto sigue apuntando al frente. Entonces vamos a decir, Hey, cuatro, cuatro, vamos a decir, Hey, cuatro, cuatro, ahora estás apuntando tu siguiente en lugar de No, ahora está apuntando a tres. Ahora está apuntando a nuestro inicio. Vamos a decir que apunta a empezar, y eso lo va a destinar al principio. Entonces una vez que se apunte por aquí, vamos a eliminar fuera de aquí, y vamos a hacer el punto de inicio hasta aquí, y entonces eso va a crear nuestras inserciones o inserto siempre es tiempo constante. Siempre van a ser esas tres operaciones crean asignadas al inicio un signo iniciar dos nuevo no a nueva nota. Entonces siempre va a ser tiempo constante. Entonces ese es tiempo constante. Y luego tenemos inserto en la parte posterior. Entonces insertar a la parte de atrás, sin embargo, nos va a llevar un poco de trabajo porque, como dije, no hay manera de volver aquí a menos que después, voy a ir por encima como puedes crear poco punteros para ayudarte. Pero ahora mismo, con sólo una lista básica vinculada a Singley, no hay manera de que podamos llegar hasta aquí sin pasar por toda la lista. Y así esto siempre va a estar dentro. Siempre va a estar en, lo que significa, por defecto, es el peor de los casos está en también. Entonces es el peor de los casos también estará porque, como dije, no hay forma de que podamos saltar aquí. No podemos llegar desde el principio y luego simplemente pasar al final. No hay nada que nos apunte hasta el final. No sabemos qué hay aquí. No sabemos cuántos nodos aire entre esto. Todo lo que sabemos es por dónde empezar y cómo llegar al siguiente. Entonces vamos a tener que hacer es correr start. Teníamos que crearnos un nuevo nodo. Entonces si quisieron agregar uno al final, digamos que queremos sumar estos cuatro al final. El único modo en que podríamos hacer eso es que tenemos que ir. Está bien. Bueno, ¿qué hay al final? Bajar 4 a 3. Pagar un 2 a 10 este es el No, estamos al final. Genial. Ahora, una vez que estemos al final, tenemos la nota final. Podemos entonces contárselo. Oye, te vas a mover. Ya no sabes que te van a poner a cuatro. Al igual Y entonces, supuesto, por defecto. Cuando creamos esto, esto fue señalado para saber que nuestra lista funciona de nuevo. Entonces una vez que llegues aquí, la operación es sólo como uno o dos tipos de números de creación. Pero llegar hasta aquí se le debe hasta el final. Y es por eso que nuestra carrera puede tiempo será Odeon también. Y así el siguiente que queremos agarrar va a ser borrar al azar. Por lo que queremos eliminar al azar. Y así con una delicia en ella especie de depende de cómo estés borrando y dónde quieras eliminar . Entonces el problema es que si estamos borrando del frente, es realmente fácil. Si eliminamos del frente, todo lo que tenemos que hacer es decir, inicio igual al frente siguiente. Entonces déjame escribir eso porque este tipo de se mete en algunos. Al igual que si comienzas a escribir estas cosas, será como, um, inicio es igual a esta nota aquí mismo. Start dot siguiente. Y esta flecha se llamaría siguiente. Entonces lo que estamos diciendo es que el inicio ahora es igual para empezar siguiente y luego éste acaba de sacarse del ciclo y la flecha consigue re ID de asociado fuera de aquí, y luego va directo de vuelta a aquí. Entonces si eliminamos el frente, es con una sola vez. Entonces si eliminamos el frente, saldrá con una sola vez. Pero si eliminamos aleatoriamente, que está en cualquier parte de aquí, si queremos decir que queremos eliminar el cuarto elemento o el Noveno Elemento para hacer eso, va a tomar odienne porque vamos a tener que atravesar todo el asunto. Y luego si te das cuenta no podemos ir hacia atrás. Entonces si quisieras liderar éste pega. Vas a tener que agarrar el anterior, y luego vamos a tener que hacerlo. Entonces, por ejemplo, si quisiéramos eliminar tres aquí mismo, tendremos que hacer es vamos a tener que ir a dos y entonces tendremos que decirle que es el siguiente va a ser igual a su siguiente va a ser igual a punto siguiente A continuación, que tipo de se complica un poco. Entonces sería como si estuviéramos en el número dos aquí. Estamos en este nodo, ¿verdad? Aquí están todas las acciones, ¿verdad? ¿ Qué? Los números son tan correctos. Nodo cuatro. ¿ Y qué decir? Nodo cuatro punto Siguiente es igual para punto siguiente punto Siguiente. Y entonces lo que estás haciendo es agarrar el siguiente final en el siguiente. Estás diciendo que ahora es igual a esto. Entonces estás pasando por alto este de aquí mismo al pasar por alto esto, lo quitas. Pero para llegar a este punto, para llegar a este punto, hay que saber que va a hacerse cargo del final, lo que significa que el líder aleatoriamente va a estar ot adentro también. Entonces esto será o hasta el final y nosotros sólo pero hemos descubierto que borrar del frente va a ser constante es constante y ya ves un poco de mejora ahí. Entonces hemos tenido una especie de muchas cosas que podrían tardar más. Pero entre la matriz, Si ves que eliminar de frente en una matriz llevará O hasta el final mientras que eliminar del frente en una lista vinculada tomará lo que hace Eso debería ser constante. Eso debe ser constante. Si bien el engaño de esto tomará o será un tiempo constante, que significa que no se escalará, cual es genial. Y pero también se ven algunas otras diferencias aquí es que la inserción aleatoriamente fue instantánea. Si bien la inserción aquí va a ser o hasta el final, Un frente insurgente aquí dentro era odienne. Pero el frente de inserción en una lista enlazada ha terminado con uno. Entonces estamos viendo algunas compensaciones aquí. Algunas diferencias entre estos dos. Y así ahora sigamos adelante y eliminemos ese último movimiento. Ya no estamos borrando este. Va a volver a una bonita lista de enlaces justo aquí, y lo que necesitamos ahora es buscar ordenados y desordenados. Entonces, ¿qué? Tenemos esta búsqueda para ordenados y en búsqueda de desordenados. Y así ambos van a terminar siendo O hasta el final también. Y eso lo voy a explicar en tan solo un segundo. Y la razón es que no importa si esto está ordenado o no ordenado. Todavía tienes que atravesar todo el asunto para encontrar lo que buscas. Si sabíamos que esto era 12345678 entonces no importa porque todavía no hay manera de que podamos simplemente saltar a dos o saltar al número ocho o en cualquier parte de aquí. No podemos saltar. Tenemos que iniciar y luego mover desde el inicio hacia abajo la lista enlazada. que significa que pase lo que pase, si queremos entrar aquí, si, como, por ejemplo, encontrarían los dos que podría tomar para ir hasta el final, podría ser al final de la lista para encontrar esta cosa. Ya sea ordenada o no ordenada. Va a ser una reversión de lista enlazada completa, y por lo tanto va a ser tiempo lineal. Significado va a tener que pasar por cada nodo en el peor de los casos. Por lo que la búsqueda es un poco más lenta en esta situación. Si bien si vamos a una matriz, veremos que la búsqueda sin clasificar tiene lo mismo. No obstante, si ordenamos la matriz podemos levantarnos para iniciar sesión, en realidad podemos mejorarla bastante por lo que hablamos antes, donde lo cortamos a la mitad. Seguimos cortando y 1/2 hasta que terminamos encontrando el número que buscamos. Y así ahí lo tenemos. Esos son los tiempos de ejecución de una lista enlazada. Como decía antes, aquí hay un par de similitudes. Un par de pequeñas, um, adversidades entre los dos y a veces como, por ejemplo, inserción aleatoriamente e inserción en el frente aquí, verás que son diferentes. En realidad, thes el insurgente al azar es más rápido que en la matriz. Si bien la inserción al frente es más rápida en la lista enlazada, la inserción hacia atrás va a ser realmente lenta mientras que en la búsqueda en la parte posterior en una matriz va a ser realmente rápida. Delish in va a ser más lento en la lista enlazada. Pero más rápido en el ah, más rápido en la búsqueda frontal va a ser básicamente la misma si está desordenada. No obstante, si se ordenaba, la matriz sale adelante. Por lo que se puede ver que a pesar de que estos dos son muy diferentes, son completamente diferentes. Se podría pensar que tal vez, como, tal vez prefieras una sobre la otra una era más intuitiva sobre la otra, que todas estas tienen una especie de salvedad muy específica. Entonces, por ejemplo, si ponemos aquí un aumento y por aquí tenemos nuestras listas enlazadas, podría haber ciertas situaciones en las que queremos usar una sobre la otra. Si tuviéramos un programa que insertara en el frente un lote insertado hacia el frente una vez no quisiéramos usar una matriz para eso porque si usáramos una matriz para eso, tendríamos que, uh, desplazar uh, todo y seguir creando nuevo Un raise para que realmente funcione bien, en una lista enlazada, todo lo que tenemos que hacer es simplemente crear un nuevo nodo y especie del frente. Entonces si quisiéramos insertar al frente, éste tendría una ventaja. Inserta frontales programas pesados parte mi escritura aquí. Entonces inserte programas pesados frontales, todo de una matriz, si queremos ordenarlo y luego buscar Sería lo mejor. Entonces, ¿qué podemos tener una matriz ordenada? Y queremos hacerlo. Entonces es como las