Introdução à ciência da computação: domine a teoria por trás da programação

1. Introdução: Olá, todos. E bem-vindos a esta aula de Ciência da Computação. Este é um vídeo de introdução. Meu nome é Kurt Andersen. Eu vou ser o instrutor da sua aula que vai sobre o básico da ciência da computação. Uma boa visão geral de todos os tópicos que a ciência da computação atinge e algumas das áreas principais , como em notação, tempo e coisas assim. Neste curso, vamos aprender essas sete coisas, e eu vou revê-las em apenas um segundo. Mas quero dar-vos uma ideia do porquê de querermos aprender estas coisas. Ciência da computação é a forma como olhamos para a programação e algoritmos para que possamos torná-los mais eficientes. E esse termo, chamado escalável escalável, significa que nossos algoritmos funcionarão eficientemente se colocarmos 10 pedaços de dados ou se colocarmos , por exemplo, um milhão de pedaços de dados. Queremos que nossos programas sejam executados de forma eficiente ou essencialmente com o máximo de dados possível . Pense, por exemplo, se estamos construindo o próximo Facebook, imagine se eles só o projetaram para 10 pessoas. Isso seria um problema, porque quando eles chegaram a um milhão de pessoas. De repente, há um grande problema. Há tempo, problemas. As pessoas não podem carregar coisas porque nossos servidores e algoritmos são todos ineficientes. E se for muito ineficiente, podemos criar um algoritmo que faça exatamente a mesma coisa de duas maneiras diferentes. Uma das maneiras de levar 10 anos para terminar. E do outro jeito, pode levar 10 segundos. Então não queremos criar algoritmos que levam 10 anos. Queremos criar os algoritmos que levam 10 segundos. Vamos repassar coisas assim ao longo do curso, quebrando alguns problemas e conseguindo o tempo para que eu possa mostrar a diferença entre os tempos neste curso, usando esses algoritmos diferentes. E no final do curso, vamos rever um projeto. Então vamos falar sobre isso e eu vou falar sobre o projeto. A primeira coisa que fazemos é um pouco de atualização de matemática. Sei que já passou algum tempo desde que você foi a uma aula de matemática, então vamos cobrir algumas coisas básicas. Algumas das coisas que o ajudarão ao longo do curso. Isto não é um curso intensivo de matemática. Estamos aprendendo novas áreas, mas ajudará se você tiver uma base sólida. Então vamos a uma rápida atualização de matemática só para que vocês se lembrem. E se você tem um pouco de, ah, fundo instável em algo, você pode procurá-lo um pouco e aprender um pouco mais sobre isso antes de começar. Então temos em notação que é uma espécie de princípios básicos por trás da ciência da computação. É a nossa ferramenta na caixa de ferramentas que nos permite olhar para dois algoritmos e dizer qual deles é mais rápido. Então, se eu olhar para Al Gore que eu digo que está em log in versus outro algoritmo, que está no quadrado como um computador, cientistas, nós sabemos o que isso significa. Agora podemos rotular as coisas de forma diferente e comunicar as velocidades com outros cientistas da computação . Isso é o que a notação in está trabalhando sobre armazenamento de dados e um aumento. Esta é uma maneira de armazenar dados, uh, uh, disponíveis em todas as linguagens de programação modernas como Java JavaScript, coisas como desenvolvimento IOS, que geralmente é Objective C ou Swift ou Andrew Development, que é trabalho. São Escócia todos um raise listas ligadas, pilhas e filas, eles existem em todos aqueles. Então vamos passar por nós e listas vinculadas. Ambos lá quase opostos um do outro. Então eles fazem coisas diferentes, e eles permitem que você resolva problemas diferentes de maneiras diferentes. Pilhas e filas que são pensar em um que quase como quando você está esperando na fila, há coisas em fila. Então essa pessoa vai, e então essa pessoa vai, e então essa pessoa vai, e se as pessoas entrarem, elas começam a se alinhar para que possamos realmente criar isso em um algoritmo, que nos ajuda em muitos situações diferentes. Eles vão recomeçar álbuns. Esta é uma espécie de base do nosso conteúdo de ciência da computação. É sempre aqui que as pessoas começam. Há um monte de diferentes, e isso permite que você veja uma progressão. Deveríamos ir para algum tipo realmente ruim de algoritmos de holograma que levam muito tempo, e nós vamos trabalhar nosso caminho até alguns algoritmos de classificação muito, muito bons que são eficientes, mas um pouco complexos. Eles iam passar por cima das árvores e da árvore de busca binária ou da BST. Esses dois tópicos importantes dentro da ciência da computação. E finalmente, vamos fazer o projeto. Foi o fim do curso? E o projeto do produto é essencialmente que vamos pegar tudo isso e trazê-lo para baixo em um problema. Há um problema. No final do curso, temos 10 milhões de dados. Estou tentando classificar esses dados, e quero que você passe pelo problema e me diga quanto tempo levará para ser executado. Você será capaz de me dizer até o final disso e então como você pode torná-lo mais eficiente? Haverá algumasmudanças rápidas e fáceis, mudanças rápidas e fáceis, algumas estruturas de dados. Você pode mudar coisas assim que torná-lo mais eficiente, e você verá que o tempo vai muito diferente, dependendo de como você implementar essas mudanças. Então, esses são os nossos cursos, é o que vamos aprender. Vai ser uma grande viagem. Há muito a aprender, e você vai lentamente entender mais sobre o mundo dos computadores à medida que passamos por ele. Obrigado a todos, e vamos começar com este curso 2. Introdução de complexidade de um a um tempo: Então nós vamos começar este curso onde ah muitos cursos de CS começam, e isso é no tempo e complexidade. A razão pela qual começamos a complexidade do tempo é porque nos dá um padrão, algo com o qual podemos comparar nossos programas e algo sobre o qual podemos conversar com outros cientistas da computação. É uma maneira que eles podem, especialmente professores e aqueles que nos ensinam podem se comunicar conosco. Por que um determinado algoritmo de programa, nossa maneira de fazer algo é ineficiente versus outra maneira. Então, é uma maneira padrão de comparar diferentes salas fora. É a isso que tudo se resume. E o que eu quero dizer com uma maneira padrão, é o fato de que um cientista da computação, digamos, dos Países Baixos e da América e da Índia, poderia todos se comunicar exatamente da mesma maneira porque usamos certas notações como notação grande O. Então, por exemplo, seria algo parecido com isso. Esta é uma grande notação O, então qualquer cientista da computação entende o que isso significa, e mais tarde vamos discutir isso também e geralmente aprendemos. Você usa certos pequenos aspectos, como no quadrado ou outros fatores escaláveis. Então nós não estamos usando como ele você sabe que ele funciona em 25 unidades de tempo porque nós não sabemos o que 25 unidades significam. Demora 25 ciclos de relógio que levam 25 segundos da tomada? Será executado em 25 ciclos no meu computador versaria o seu computador? É muito difícil comparar quando você vai para isso. Então, o que estamos fazendo Estes estariam olhando para o padrão para isso, uma maneira que podemos comparar com algoritmos completamente independentes do computador, que ele está sendo executado na área, nesse mundo, quão rápido o A conexão com a Internet é apenas ser capaz de olhar para dois deles e ser capaz de compará-los e nos permite descobrir maneiras de melhorar a nós mesmos. Então, se pudermos olhar para uma certa, você sabe, uma certa notação, então podemos descobrir como ser melhores do que essa notação e quais coisas são piores do que essa notação, e isso nos dá muito espaço de manobra. Isso nos dá a capacidade de melhorar a nós mesmos um conjunto de metas e de pesquisar em diferentes áreas, como qualquer outro aspecto. Qualquer outra ciência, vamos rever o básico desta ciência e como podemos analisá-la e tentar descobrir como torná-la melhor. 3. 1-2 de redde de MATs: funções de Math: ciência da computação é baseada em uma base de matemática. Basicamente é apenas matemática aplicada que você joga em um processador e então ele faz tudo para você. E você sabe, você pode continuar construindo isso para fazer seus programas. Mas, em essência, é matemática, e é por isso que eu só quero rever alguns termos matemáticos que serão usados ao longo do curso. Agora, não se preocupe. Este não é um curso de teoria matemática pesada ou algo assim. Nem vai haver cálculos. No entanto. Nós vamos fazer referência a alguma terminologia matemática, alguma nomenclatura matemática, que eu queria ter certeza de que estamos todos na mesma página antes de avançarmos para esse tipo de nomenclatura. E são apenas algumas coisas que aprendemos talvez na escola. Ou aprendemos uma ou duas vezes, e simplesmente não usamos no mundo real. Mas quando você entra em ciência da computação, eles se tornam um pouco mais prevalentes. E como eu disse, você não precisa saber como fazer tudo à mão, mas apenas entendê-los. Isso é o que eu quero chegar ao ponto de você ser capaz de entender essas coisas diferentes e onde você pode vê-lo como digamos que temos um tempo de execução de um algoritmo. Podemos entender o que esse termo matemático significa em relação ao tempo de execução. E então é isso que eu estou indo para dentro. Esta palestra está passando por cima de algum material de atualização para que quando batermos nele novamente mais tarde no curso, você vai entender isso em um nível básico, e você pode tipo de expandir seu conhecimento um pouco mais fácil. A primeira coisa que quero falar é algo que é usado em ciência da computação, mas não muito em outros lugares. E essa é a idéia de log. Então aqui é referenciado, ou a nomenclatura para é assim. É baseado em log, algo assim como digamos que é baseado a de variável aqui ou um número é igual a algum outro número. Então, por exemplo, vamos colocar oito aqui, e assim esta é uma função de log. Agora, o que exatamente é uma função de log? Bem, o que é abreviado é algo conhecido como uma função log rítmica e uma função log rítmica é o inverso encontrando o oposto, o inverso de uma função exponencial. Então, um tronco é o inverso de um exponencial. Agora, o que é uma função exponencial? Digamos que o rastreamos ao longo do tempo. Rastreamos o crescimento de ambas as funções ao longo do tempo. Uma função exponencial vai um pouco como isso, onde você vai direto para o ar significa porque depois de cada iteração a mudança cresce. Então, por exemplo, talvez de 0 a 1, ele mudou por um de 1 para 2. Talvez tenha mudado por dois de 2 para 3. Talvez tenha mudado quatro, depois oito, depois 16 e 32 64. E continua indo cada vez mais alto e mais alto até quando você faz um mudar seus bilhões ou trilhões de números para o próximo. Então essa é uma função exponencial. São muito ruins na ciência da computação. Se você está falando sobre tempos de execução porque isso significa que quanto mais coisas você colocar nele, ele só vai para o infinito de quanto tempo vai levar Agora Uma função de log é o inverso disso. É o oposto disso, e qual seria o oposto disso? Bem, isso é simples. Isso é se você pegar isso e você sabe exatamente o oposto, então vamos assim em vez disso. Então, o que é isso, é que vai ter uma grande mudança no início. Mas com o tempo, a mudança entre números vai ficar cada vez menos e menos com o tempo. Então, onde este vai quase para uma linha vertical reta, este vai quase para uma linha horizontal reta. Isso é bom porque isso significa que quanto mais coisas colocamos em nosso programa, é quase como se o tempo de execução não estivesse mudando. Está ficando cada vez menos e menos até começarmos a gostar dessa linha horizontal. E é por isso que as funções de log são importantes porque são o inverso do exponencial. E há alguns algoritmos que são executados neste tipo de tempo, então esse é o lado teórico disso. Vamos dar uma olhada em alguns exemplos, então vejamos primeiro. A equação para este log de X é igual ao nosso log baseado X de por que é igual a Let's Go b e que, por sua vez, entra na função exponencial. Então este é um registro com a minha função. Esta é a função exponencial e a função exponencial é x de B igual. Por quê? Certo, então vamos analisar alguns números aqui para sairmos desse tipo de variáveis abstratas e estranhas e entendermos isso um pouco melhor. Então, se levarmos dois para o B e for igual a oito, então o que isso significa? Bem, isso significa que se levarmos dois para algo e se, por exemplo, o que estamos dizendo aqui é, por exemplo, para um igual a 22 a dois é igual a quatro. E isso é porque é apenas muito vezes para você tomar 22 vezes dois para o três é igual a oito. E isso são apenas duas vezes. Duas vezes dois você está tomando para multiplicado por si mesmo três vezes igual a oito, e assim por diante e assim por diante. Então nós estamos dizendo é que há um número ser que existe tal que ele é igual a oito. Bem, aqui nós só descobrimos isso. É de dois a três igual a oito. Então, se nós conectamos três para B, nós temos que o três é igual a oito. Este lado é igual a oito. Este ciclo a. Essa é uma expressão legal. Então aqui em cima, B é três. Bem, como isso nos ajuda? O que isso nos diz? Bem, se nós transformamos isso em uma função de log, nós podemos realmente obter um pouco de informação fora dele. Então, se obtivermos log de, vamos conectar nosso valor X, nosso X aqui. Então é uma base longa para. E então agora vamos ligar nossos, uh, nossos uh, escritores B ou R Y real por muito tempo, baseado em dois de oito. O que é isso igual? Bem, sabemos que é igual a três. Então o que podemos fazer com a função rítmica log é que podemos realmente encontrar este número mais fácil. Confinamos que seria mais fácil. E isso é importante porque com uma função rítmica log, nós podemos conectar números aqui e podemos obter números no lado direito onde com uma função exponencial, nós conectamos números e esquerda, e obtemos números Por aqui. Então isso nos ajuda porque agora o que podemos fazer é olhar para a relação de por que uma função log é importante. Digamos que temos isso ou vamos primeiro falar sobre a base. Então, tipo, por quê? O que é base longa para com base longa 10. A base é exatamente o que estamos pegando o número dois. Então, por exemplo, se nós tendemos a um tendem para o para e tendem para o três ou nós teríamos é 10 em seguida 100 em seguida 1000 e isso é por causa disso aqui tendem para o judeu é 10 vezes 10. Assim é 110 dos três é apenas 10 vezes 10 vezes 10. É 10 vezes três de si mesmo, então é apenas 1000. Então, nesta situação, seria registrado com base 10 porque o número aqui é um 10 e isso é não há nenhum significado que você possa fazer. Log baseado 27 Log Place 98 Log baseado 1000 Realmente não importa. Ciência da computação. Ficamos com Log baseado, também, e vamos explicar isso um pouco mais tarde. Mas tudo se resume a como os computadores têm realmente apenas um zero e um um para trabalhar. Então eles estão citando dois estados separados aqui, e é por isso que deixamos usar a base de registro para que passou por cima de sua cabeça. Isso é perfeitamente bom. Só entenda que usamos o também. Então, digamos que tínhamos muito baseado Digamos que temos um algoritmo que é executado em tempo de log. Digamos que temos muito baseado, também, também, e esta é a quantidade de informação que entra. Então, digamos que é baseado em muito tempo. Dois de nós temos 64. Então talvez tenhamos uma conta no Facebook e estamos executando algum algoritmo no Facebook que passa por nossos amigos. Então temos quantos amigos nesta situação? Temos 64 amigos e quanto tempo vai demorar? Bem, nossa equação corre em log, então nós completamos que 60 estrangeiros, e vai ter algum valor aqui. E nesta situação, podemos ir. O que vai? O que é até o final que é igual a 64 que sai para ser aproximadamente dois para o sexto, que é que você pode ver bem aqui em baixo. Vai para o 816 Então, se formos para o quarto, vai ser 16 para o 5º 32 para o 6º 64 certo? Assim. Então, o que é 2 a 6? Então agora temos o seis. E agora temos aqui seis. Então, neste lado direito, o que temos é o tempo de execução. Então vamos dizer que isso é segundos. Então agora temos um algoritmo aqui. Temos base de registros. Dois dos 64 dados equivale a um tempo de execução de seis segundos. Bem, vamos meio que fazer isso ir. Um pouco mais para o lado extremo. Por que longo é um algoritmo tão bom? Por que é tão importante na ciência da computação? Bem, se conseguirmos um algoritmo que seja assim, podemos começar a ver algumas coisas muito, muito legais. Então vamos em frente e limpar um pouco de espaço aqui e vamos olhar para isso um pouco mais. E se tivéssemos muito tempo de dois de agora? Eu não sei. Um. Vamos dobrar isso. Então, 1 28 Bem, isso vai ser igual a sete segundos. Então duplicamos a quantidade de informação que está chegando, e só subimos um segundo. Só mudamos um pouco. Vamos ainda mais alto. Digamos que queremos em vez de duplicar isso ou sim, vamos continuar dobrando. Vamos para 56 aqui e agora temos oito segundos para que você possa ver que a mudança entre estes está ficando cada vez maior, mas os segundos estão subindo linearmente. Eles estão indo para Lee subindo por um segundo cada vez. Vamos extrapolar isso. Digamos que levamos dois para o eu não sei, digamos 32. E por que isso é importante? Bem, para a 32ª. O que é para o 32º igual? Era um número muito, muito grande, e esse número passa a ser 8.000.589.000 ou 589 milhões, 934.000 592. O que há de significativo nisso? Este é o primeiro número nesta sequência que é maior que a população do planeta . E se estamos lidando com o Facebook aqui, isso significa que nosso algoritmo no Max vai correr 33 segundos. Não vai longe em que você não pode ter mais amigos do que há pessoas no planeta. Então nós meio que tivemos isso. Temos um algoritmo incrível aqui onde não importa quantos dados são. Vai sempre correr 33 segundos ou menos, quer estes milissegundos de ar ou estes microssegundos de ar ou outros tipos de unidades de tempo. Esta é uma taxa de crescimento realmente grande. Isso significa que a próxima versão seria se duplicássemos isto novamente, modo que seriam 16 mil milhões. Então, temos uma mudança de um segundo indo de oito bilhões para 16 bilhões e depois mais um segundo para subir para 32 bilhões. Então é por isso que os registros são importantes é por causa desse relacionamento que falamos aqui , como eles não crescem muito com o tempo. E se você continuar indo para o infinito, eles quase se tornam uma linha horizontal onde você pode colocar em tantos dados quanto você quiser jogar dentro e seu algoritmo ainda vai executar basicamente a mesma velocidade. Então essa é a função rítmica de log. É muito, muito tipo de função simples uma vez que você entenda. Mas ainda é muito estranho no buraco, toda a discussão sobre matemática e é algo que realmente não vemos com muita frequência. Então essa é a primeira coisa que eu queria cobrir antes de entrarmos nela. A próxima coisa que eu quero cobrir é outro que muitas pessoas já viram, mas eles realmente não entendem em um nível básico, e isso é algo conhecido como fatorial 4. 1-3 de redde de materiais: funções factorial: Então, o que é exatamente um fatorial? Bem, um pouco parecia algo básico como este. Faux três e depois um ponto de explicação ou talvez 27 um ponto de explicação. Hum, o que é exatamente? Um fatorial significa o que é um fatorial? É apenas se você quebrá-lo, é qualquer que seja o número no ponto esquerdo multiplicado por todos os números prosseguidos. Então, neste caso, o fato de três fatoriais vai ser igual a seis. Vai ser igual a seis, que é uma vez 22 vezes três. Então, um vezes dois é igual a 22 vezes três é igual a seis. Então, três fatoriais é igual a seis. Você vai notar que algo muito importante sobre isso é que esta taxa de crescimento é insana. Então, se formos um fatorial, isso só vai comer um dois fatorial legal uma vez 22 Então é, você sabe, bem parecido com o resto das taxas de crescimento. Três. Fábrica muito igual a seis quatro fatoriais. Então pegamos esse seis e multiplicamos por um quatro, que vai ser 24. Então, em vez de apenas uma vez duas vezes três, temos uma vez duas vezes três vezes quatro, então você pode ver que são 24 agora, cinco fatoriais. Vamos pegar esse número, que é esse número aqui multiplicado por cinco. Então podemos fazer uma matemática rápida. Por que você pode ver que nós já estamos chegando ao ponto em que nós vamos ter que fazer como , hum, basicamente matemática manual para fazer essas coisas funcionarem. E só estamos no número cinco, como nos registros. Poderíamos continuar subindo, subindo e subindo, não era muito difícil. Seis. Bem, vamos passar por isso por seis. De vez em quando temos 120 por isso vão ser 600. Isso é me dar 720 bem ali, certo? Sim. 720 e você pode ver ou 820. Ato Nº. 7 20 Você pode ver que este número está crescendo em uma quantidade substancial. Cada mudança está ficando cada vez mais onde tivemos uma mudança de uma bem aqui. Agora temos uma mudança de quatro. E então uma mudança de, hum, aqui em baixo nós tivemos uma mudança de Vamos dizer, vamos ver 18 aqui. Tivemos uma mudança de 96 aqui. Tivemos uma mudança de 600 você pode ver que isso está ficando fora de controle. Então fatorial há algo que nós nunca queremos encontrar lá sempre representado por qualquer um dos gostos e em, o que significa apenas qualquer número. Você pode ligar lá que, tipo, tipo, se quisermos ser genéricos, podemos colocar uma variável no ponto de explicação, ou podemos colocar um número para obter uma resposta real. No entanto, isso é o que um fatorial é. É apenas uma multiplicação de cada número que o procede então, como eu disse, um fatorial de um sete é apenas ou um são sete. Fatorial é apenas uma vez duas vezes três vezes quatro vezes cinco vezes seis vezes sete. Nada muito complicado nisso. Mas como eu disse, muitas pessoas não vêem isso, especialmente elas podem ser vistas uma ou duas vezes na aula de matemática, mas não novamente. Às vezes vamos falar sobre fatorial é que eles são algoritmos muito ruins. Se o seu programa acabar no Factorial, eles podem pegar como eu disse, você poderia colocar em um programa que é talvez quatro fatorial e vai correr muito rápido. E então se você colocar em um programa que é, você sabe, 20 fábricas. Apenas, você sabe, mais 16 pedaços de dados que talvez nunca completem. Você sabe, o tempo que pode levar para completar o sol pode queimar mais rápido do que isso. Então essa é a importância de um fatorial. 5. Redefinição de MAT, 1-4 a de Math: expressões de Math: E finalmente, eu só queria rever algumas álgebra básica ou algumas coisas que você pode ver no curso. Então, por exemplo, podemos ver algo assim, que é N log-in. Então, o que isso significa? Bem, isto é apenas uma espécie de função genérica. É só mostrar o que uma taxa de crescimento ou o que uma função estava usando nesta situação. Então, digamos que A é igual à quantidade de dados, a quantidade de dados. Então, se tivéssemos uma função que é assim, tudo o que estamos dizendo é que digamos que nossa entrada sai para 700. Não sabemos se vai ser porque os programas são dinâmicos. Eles correm em espaços diferentes. Às vezes, uma pessoa pode ter 20 amigos no Facebook. Às vezes eles podem ter 1000. Não sabemos quantos amigos do Facebook vão acabar por ter. Então é por isso que escrevemos algo assim. É quase como um espaço reservado. Diz-nos o que vamos usar sempre que conseguirmos este número. Mas antes não sabemos o que é. Este é um princípio básico da álgebra, e então o que podemos fazer quando temos uma fórmula como esta quando entendemos o algoritmo, o álbum de computador ou o uso é que uma vez que obtemos um exemplo concreto, isso é como o resumo. Isto é algo que ainda não sabemos. Podemos ligar esse exemplo concreto aqui, e podemos realmente obter um número. Então, nesta situação, seria 700 vezes log de 700. E digamos que esta base aérea para vamos com algo que podemos realmente calcular em nossas cabeças. Digamos que é igual a, hum, Vamos com 16 vai um 16. Então isso significa que vai ser 16 vezes longo, baseado em dois de 16. E nós aprendemos no último que isso é apenas o registro de quê? Ou para a base bem aqui para o que é igual a 16. Bem, duas vezes quatro vai ser igual a 16. É duas vezes duas vezes duas vezes duas vezes 22 vezes, duas vezes duas é igual a oito. Então este é 48 16. Então agora sabemos que quatro é a resposta para isso, então temos 16 vezes para o qual vai sair. Teoh quatro vezes. Então vai ser 40 vai ser 64, certo? Como assim. E então é isso que vamos ter um par destes. Quero dizer, eles podem ficar, você sabe, eles ficam mais complicados do que eles poderiam ser no quadrado de log para o terceiro ou em cima para fazer logoff em mais de três ou qualquer coisa do tipo. Mas entenda que sempre que você tem uma função como esta, tudo o que significa é que estamos tomando estes dois vão ser o mesmo número que ambos são a extremidade variável. Então ambos serão exatamente o mesmo número e sempre que tivermos um número concreto , vamos ligar esse número. Acho que isso é bom. 6. Notação de 1-5: Então temos uma boa compreensão de onde estamos indo nesta unidade. Vamos começar a construir esse processo. Comece a entender isso um pouco mais e passar por cima de algo chamado em notação em notação é apenas uma maneira de olhar para como nosso programa é executado representado como uma função de in. Então isso é importante aqui. É representado como uma função de em uma função de fim. E o que isso significa é que teremos um número arbitrário chamado. Então, por exemplo, nós temos aqui e o que exatamente está dentro? Normalmente, é julgado pelo número de dados que estão sendo processados por um programa. Então basicamente o que um programa é que você tem um monte de entradas aqui, então vamos chamar essas entradas. Você é um monte de pontos. Eles vêm ao nosso programa como uma caixa preta, se preferir. E então eles têm um monte de saídas bem aqui. E é basicamente assim que os programas funcionam. Você tem um monte de entradas, eles são processados de alguma forma, e então eles são armazenados ou fora. Coloque-o de outra forma. Então o que em é quantas entradas estamos recebendo quantas vezes temos que executá-lo e em cada processo. Então é basicamente como, por exemplo, nesta situação, é como as entradas Maney podem ser em quantos tipos de cálculos precisamos poderia estar. E, em seguida, quantas saídas sair também poderia estar dentro. Então é algo que é arbitrário o suficiente para que possa ser usado em qualquer processo de execução do programa, mas ainda assim nos permite entender como os programas foram reagindo. Então vamos dar um passo para trás e vamos olhar para isto de uma forma mais explícita . Digamos que nesta situação em igual a 100 então agora nós realmente temos um número aqui. E então, se nós conectamos o mental, você sabe todas essas diferentes versões aqui, digamos que isso não está em algoritmo e compará-lo a um algoritmo in quadrado. Você pode ver que não importa qual seja esse número, esse número sempre será muito, muito maior, e nessa situação é muito maior, e na verdade é 1000 versus 100. E a razão pela qual normalmente não conectamos números explicitamente é porque a quantidade de dados que estão sendo processados geralmente nunca é garantida como um determinado número. Por exemplo, vamos olhar para digamos que o nosso programa introduz a quantidade de amigos do Facebook que você tem. Então o nosso programa introduz a quantidade de amigos do Facebook que temos. É colocar esses dados na nossa caixa. Mas quantos amigos do Facebook você tem? Porque eu posso te dizer que eu sou meu número vai ser diferente do seu número. teu número vai ser diferente do que provavelmente muitas pessoas a frequentar esta aula. Então, se estamos construindo um algoritmo para 250amigos especificamente, não vai funcionar para a maioria dos casos. Então o que fazemos é construir algoritmos que podem absorver uma quantidade arbitrária de dados. E nessa situação, é exatamente o que chamamos de verdade. E assim pode ser tomado em quantidade de dados. E, em seguida, uma vez que ele processa e produz, ele vai produzir em quantidade de dados. E assim com estes, este tipo de classificação foi capaz de comparar al Berlin sem nunca entender quantos números vão colocar em. E isso é só porque estamos olhando para ordens de grandeza aqui. Nós não estamos olhando para a diferença entre 10 e você sabe, nove unidades de tempo ou o que quer que seja. No entanto, ele sai que estamos olhando em verso no quadrado. Então, por exemplo, nesta situação, digamos que se colocarmos em uma quantidade de amigos do Facebook que vai levar em um quadrado de tempo. E agora nós entendemos que talvez se eu tivesse 10 amigos, isso funcionaria bem e seria apenas, você sabe, isso sai para, tipo, o que, 100? Mas o que acontece se eu tivesse um milhão de amigos, então qual seria esse número? Seria um número absolutamente enorme, e a diferença de cálculo seria enorme em comparação com se fosse apenas uma saída. E então vamos dar uma olhada nisso um pouco mais em profundidade, e você pode ver que há um monte de maneiras diferentes que podemos representar aqui , e este é um gráfico de sua escala ao longo do tempo. E então o que estamos tentando descobrir é como é que, em escala, chega ao infinito? Então, a razão pela qual estamos em questão importante é porque, medida que ele escala ao infinito, é a possibilidade do que nosso programa poderia dar entrada. Então não estamos olhando para Como é que escala para 100 ou 1000 que estamos olhando? Se colocarmos um 1.000.000 de dados ou um 1.000.000.000 de dados nisto, como é que ele vai reagir? E esses gráficos contam a história. Então aqui em baixo nós temos algo chamado tempo constante, que é este colchete ou esta coluna Ah, bem aqui. E o tempo constante significa que se colocarmos o 1110 1 não importa o que aconteça, será sempre executado ao mesmo tempo, não há fim envolvido. Porque não importa o que, ele vai sair exatamente ao mesmo tempo, então o acima que é realmente base de log a de dentro. Lembra quando falamos sobre o sistema binário? Nós não usamos log baseado 10 como a maioria da matemática porque nós não estamos lidando com o sistema de números dezenas . O que estamos lidando aqui é com o sistema de números de dois. Então nós usamos base longa para e, em seguida, aqui temos a raiz quadrada de in in in in in log evento quadrado dois D e em fatorial e você pode ver que há uma grande, grande diferença entre estes dois aqui e estes dois aqui. E você pode ver que o ângulo fica maior e maior e maior à medida que isso vai direto para o infinito. E se você realmente trouxe isso para fora, ambos para o infinito, isso pareceria que estava quase no ar. Bem, esta casa pareceria que estava, você sabe, ainda no ângulo de 45 graus. E é nisso que estamos tentando nos concentrar. Aqui está, quando os comparamos, quão diferentes eles vão ficar com o tempo? Por exemplo, isso pode parecer uma mudança muito pequena, mas se colocarmos esses números no infinito, você começará a ver que a diferença começa a surgir. Então vamos dar uma olhada em alguns exemplos. Aqui temos o número é zero, hum, hum, 10 101.000 em igual a 10 1 Então, nesta situação, o que temos aqui é que temos o número da esquerda e, em seguida, um algoritmo que executa o tempo final e eu vou jogá-los que executa em tempo quadrado em um algoritmo que é executado em log in time e, em seguida, aqui é o tempo constante. Então, se colocarmos em um pedaço de dados, você notará que o que temos é basicamente que eles são todos exatamente iguais e zero nem sempre não faz sentido. Então, o registro é um pouco complicado. Nesse sentido, ele vai colocar para fora um zero ou indefinido às vezes. Mas isso só significa que funciona de uma vez, então todos eles são exatamente iguais. Agora começamos a escalar mais do que um. Você pode ver, todos eles começam exatamente no mesmo lugar. Começamos a escalar além de um para nossos 10. Então, você vê, eles estão todos começando aqui e agora estamos nos movendo para 10, que é bem aqui. Você vai começar a ver que as diferenças saem em, vai para apenas 10 no quadrado, chega ao topo deste gráfico em 100. Então já há uma grande diferença aqui. E, em seguida, fim Log de fim fica até cerca de 33. Vocês podem ver que está bem ali. Agora, se avançarmos mais uma unidade Decca para a direita, digamos que o nosso número é 100. Ele vai até 100 no quadrado vai até 10.000 que é, se você colocar 100 destes e empilhá-los em cima do outro. É assim que o número fica grande. É onde está lá em cima. Então este é um deles e você tem que colocar mais 100 desses. Então isso iria pelo meu teto e então para o céu, como provavelmente dois ou três andares apenas comparado com os 100 aqui, que é, você sabe, bem aqui. Você poderia até mesmo grande em que 1000. E o que temos é em vez dos 1000 aqui, o que nos dá, então, se nós apenas escalarmos isso ao longo do tempo, provavelmente estaria em algum lugar colocando todos os grandes aqui em cima. Este é um milhão, que é se você pegar 1000 desses e empilhá-los em cima um do outro e continuar subindo para o céu. Então isso é como um prédio de 25 andares. Então, comparado a talvez aqui, comparado a uma taxa de 25 andares acima, como aqui, talvez um pouco mais longe nessa direção, comparado a um prédio de 25 andares. Essa é a diferença. E este número vai para cima e para cima e para cima, especialmente se você conseguir um número realmente grande, como um 1.000.000 porque então este vai ser um 1.000.000 então este vai estar em algum lugar , como um par de um trilhões ou talvez 100 trilhões em algum lugar ao redor dessa área. E então o que você tem aqui é que você tem uma espécie de número diferente, e você percebe que esses dois parecem ser muito, muito parecidos. Mas quando você começa a se levantar em números realmente grandes, a diferença começa lá realmente sair. Então você verá aqui que 10.000 contra 664 e, em seguida, um milhão contra 9909 165. Há uma diferença muito grande. E isso é tudo o que estamos tentando fazer com N é, o que estamos fazendo é olhar para equações que estavam tentando saber como e vai para o infinito . Qual equação é melhor? E se tivermos uma equação que está em verso quadrado, uma equação que está em, entendemos que esta vai ser substancialmente melhor, mais eficiente do que esta, e então eu meio que queria rever se você não entendia que log era muito rápido. O que é log E isso é, por exemplo, temos um gráfico exponencial. Isto é como no quadrado bem aqui. Então começa com zero. E então, com o tempo, sua taxa de mudança sobe mawr e mawr e mais até que seja quase uma linha reta. Então isso aqui está no quadrado. O que é um gráfico de lei é exatamente o oposto disso. Então ele vem muito rápido, e então ele passa e quase se torna uma linha reta ao longo do tempo. E, você sabe, nós temos nossos machados bem aqui. O mesmo por aqui. Nós temos alguns eixos, mas basicamente a razão para isso é porque log é o inverso de um exponencial. Então, ao longo do tempo, onde esta a taxa de mudança. Então essa inclinação de um k quanto ele vai de aqui para aqui versus aqui para ouvir isso vai ficar maior e maior e maior até que ele está quase indo direto para o ar enquanto este aqui está ficando cada vez menor e menor tempo. Então isso significa que se colocarmos este para, você sabe, um milhão de milhões de cada vez que sobe um, esse número pode crescer em 1.000.000.000 ou um trilhão. Bem, neste caso, uma vez que chegamos a um número muito, muito grande, podemos estar indo de 8.1 para 8.0 05 Você sabe, algo como algo assim, onde a mudança vai ser extremamente minúsculo, e é assim que o log funciona. Basta pensar nisso como o inverso de uma função exponencial e você vai notar que há realmente um pequeno tipo de coisa legal que sai. Esse entendimento é se voltarmos ao gráfico aqui, você pode notar que temos log de fim e em tempo constante e porque este ao longo do tempo quase se torna uma linha reta onde estamos apenas nos movendo, você sabe, talvez 10.1 decimal. Todo mundo sobre log in e cronômetro constante na verdade geralmente tratado um no mesmo porque, como eu disse lá, sua taxa de mudança diminui onde esses ângulos realmente não mudam tudo muito. Onde no oposto acontece com no quadrado à medida que chegamos cada vez mais longe e mais longe, o ângulo começa a mudar para um ponto onde é quase uma mudança de 90 graus porque ele simplesmente vai direto no ar. Então eu só queria explicar que se você não entendeu o que um tronco significa, é o inverso de um exponencial. E então, quando vamos para o infinito, temos que pensar em outro uma idéia diferente. E esse é o fato de que se você notar e que nós não estávamos falando, qual é a diferença entre dois em verso em? E isso é porque a constante o número na frente não importa. Por que não importa? Vamos dar uma olhada aqui em cima. Então o que temos é que temos no quadrado e temos que no quadrado. E à medida que se torna cada vez maior e maior, a diferença entre estes dois começa a diminuir, onde o número em que a mudança não é tão significativo como costumava ser. E isso tudo vem para baixo frações Teoh e, você sabe, tipo de números como este. Mas o que estamos tentando olhar aqui é que comparamos com coisas que não estavam tentando comparar é um final quadrado adverso e em quadrado. Melhor porque sabemos que ambos são inerentemente muito ruins. O que estamos tentando comparar é isto em quadrado melhor contra um fim. Então, nesta situação, vocês notarão que não importa o número que coloquemos na frente daqui, ainda será substancialmente maior do que este número aqui. E então não importa a constante que temos na frente quando ela vai para o infinito, a constante não importa, e nós só olhamos para a variável em si, mesmo que eu saiba que isso é um pouco confuso. Mesmo que tenhamos um 1.000.000 em verso no quadrado, ainda será o pior cenário. E como eu disse, isso é um pouco confuso no começo só para realmente enrolar sua cabeça. Mas tudo se resume ao infinito, e o infinito é um número que você nunca pode alcançar por causa de quão grande ele é uma vez que chegamos em ir para o infinito. Uma vez que chegamos perto do infinito, a constante não significará nada, porque este número ainda superará um 1.000.000 vezes nele ainda superará um 1.000.000.000 um trilhão de vezes em algum momento. Então você tem que realmente pensar teórico aqui, mas tudo se resume a esta regra simples. Se você sabe, se você não consegue entender a teoria, basta pensar nessa regra civil. Se houver um número na frente, desconsidere-o. Não importa em nossas comparações. Então, agora vamos fazer um exemplo aqui. Vamos nos divertir um pouco. E vamos criar um exemplo onde podemos realmente ver isso em um aspecto do mundo real . Então, se cada ciclo de um programa leva 0,1 segundos Então, nesta situação, o que estamos olhando é cada ciclo de um programa que estamos dentro é que você sabe, quando fizemos essa caixa estão nesta situação são os ciclos e lado ou algum tipo de coisa Dentro desta caixa, essa é a nossa entrada. Assim, cada ciclo de um programa leva 0,1 segundos. Quanto mais rápido o programa em execução de log-in do que um programa em execução ao quadrado? Se 1000 pedaços de dados passarem e assim é realmente aqui que ele chega onde você pode realmente ver a diferença. Então vamos passar por isso. Temos 1000 peças de dados chegando. Este é N log in, que equivale a substituir nossas extremidades com o que estão em foi dada taxa aqui. Então são 1000 pedaços de dados, que é o que vai levar 1000 ciclos de meia. Então, nesta situação, nosso in é igual a 1000. Agora podemos fazer as contas por trás disso. Dizemos que vai levar 1000 vezes log de 1000 e que vai nos dar 3000 vezes 30000.1 que por sua vez nos dá 30 segundos. Agora, vamos comparar isso com em Quadrado, que vai ser 1000 para o segundo, é igual a um milhão de vezes 0,1 segundos, porque cada ciclo de relógio leva 0,1 2º Então é por isso que estamos multiplicando no final. E o que temos são duas horas e 46 minutos. Então, porque esses programas executá-lo no quadrado em vez de em, faça login. E vamos voltar ao nosso gráfico aqui e dar uma olhada. Lembrem-se, estes dois pareciam muito próximos um do outro, mas não estão. Então vamos voltar ao nosso gráfico nosso exemplo aqui porque ele correu ao quadrado. Vai demorar duas horas e 46 minutos, ou duas horas, 45 minutos a mais do que esta aqui. E vamos trazer isso para um número ainda maior. Digamos que ele tem no log de em assim de 25.000 EUA lá em equivale a 25.000 aqui. Então, em igual a 25.000. Agora você vai realmente começar a ver a diferença. Então, nesta situação em Logan é igual a 25.000 vezes log de 25.000 que vai águia em algum lugar em torno de 109.948 vezes 0.1 Então ele vai igualar em torno de 18 minutos e 32 segundos. Mas vamos dar uma olhada no final do quadrado. Então essa lista, você sabe, parece longa e desviada por mais de 30 segundos. Também notamos que é muito menos do que até 24.000 menos dados 300,7 ao quadrado. Se formos ao quadrado, 25.000 quadrados, que Eagles 625 milhões de vezes 0,1 que águias seis milhões, 250.000 segundos, que é 72 dias. Então você pode ver que este número começa a realmente decolar por aqui. E estamos apenas com 25.000 pedaços de dados. Há quantas pessoas no Facebook agora, e seus dados existem algoritmos provavelmente tem que rodar com quantas pessoas estão no Facebook. Então imagine que se você tentasse dizer que eu acho que talvez um bilhão de pessoas lá agora através deste programa levaria isso iria subir para os bilhões de anos que nunca iria terminar. E então é aqui que você pode tipo de ver a diferença das extremidades. Então, basicamente, tudo isso está tentando se resumir a alguns fatos chave. Fim é apenas quatro comparações. Então esse é o nosso primeiro fato é que está em é apenas comparar dois programas. É para verificar o tempo de execução de dois programas. Não é para uso prático, que significa que não vamos estar rodando em algoritmo em um, você sabe, um você sabe, programa e vendo se ele pode retornar coisas dentro de, você sabe, você sabe, 20 segundos ou qualquer coisa do tipo Isso. Não podemos fazer isso dentro de nós. E a razão para isso está dentro é apenas um padrão é uma maneira que podemos olhar para um programa independente fora se o computador é rápido ou lento, onde a conexão com a Internet é mais rápida, lenta Podemos compará-lo com outro programa, como no quadrado ou no Log in, e poderíamos começar a entender quais algoritmos são os melhores e quais não escalariam corretamente. Também precisamos entender que não é ruim ter números maiores. Às vezes é inevitável. Então não pense apenas que você sabe, a idéia de uma ciência da computação é nunca encontrar no quadrado novamente. Não é suposto usar para fins práticos que estamos a tentar fazer. Estamos a tentar teoricamente, resolver problemas diferentes. E assim, por exemplo, todas as espadas de comparação não podem fazer melhor do que no login. Então voltamos a este gráfico aqui. Você verá que todos os tipos de comparação caem nesta linha, então eles estão lá em algum lugar deste lado. Eles não estão no resto deste mais fácil, gráficos mais rápidos e os tipos de comparação são como você gostaria, gostaria, classificar um monte de números, então, mesmo como o uso diário, tipo de algoritmos ainda caem no login. Além disso, múltiplos caem ao comparar assim entender de volta para esta lição que múltiplos não importam e, em seguida, exponencial é pode ser muito, muito perigoso ao longo do tempo. E nossos cérebros realmente não têm a capacidade de entender as diferenças. E isso só mostra você neste aqui onde nós não pensaríamos que isso seria 72 dias versículo 18 minutos. Só porque mudamos deste gráfico para este gráfico, mas as horas extras exponenciais são muito, muito, muito fortes. 7. Notação de 1-6 a 6 a 6 de maior o o: Então agora temos uma boa compreensão de dentro e como exatamente ele funciona, e ele se liga à nossa análise de algoritmos. Podemos começar a acrescentar isso. Então nós sabemos que em é uma maneira de classificar o quão rápido no exterior eles corre, dado um certo número em Quanto tempo vai levar com respeito esse número? Então, vai levar a tempo? Então, se foi, 1000 vai ser igual a 1000 ou vai levar algo como em tempos quadrados onde quando é 1000 ele vai ser igual? UM, um milhão, e este é um tipo muito importante de classificações. No entanto, programas não são tão fáceis. Eles não correm a uma hora exata o tempo todo. Muitas vezes eles têm abundam. Então, por exemplo, talvez você não carregasse. Ele vai ser executado e em quadrado, mas ele executa um fim, e nele, e nele, você sabe que ele exporta em log in e então nós temos que ser capazes de olhar para isso, e nós temos que olhar para o programa e dar uma classificação sobre o programa como um todo. Então, por exemplo, este programa, nós sempre olhamos para o pior caso está sempre indo para o pé do pé. Pior caso tomar ao quadrado, no entanto, em certos passos vai correr mais rápido. E por causa disso, nós realmente temos esse tipo de sistema bem aqui, que vai classificar os, hum, os limites em nossa notação. Então vamos descer isso e dar uma olhada nisso. Estes aqui são chamados omicron. Você desbotou no meio e, em seguida, omega, e este é minúsculo de mega aqui em baixo e assim você pode ver que eles são alfabeto grego. Mas nós apenas muitas vezes em grego de Matthew porque o alfabeto fica confuso. Então usamos o dedo grego, simbolicamente representam as coisas, e neste caso, cada um desses símbolos gregos simbolicamente representa abundam. Então o que você tem aqui é vamos desenhar, por exemplo, um amarrado bem no meio aqui e aqui em cima é mais rápido, então vamos dizer aqui em cima vai ser mais rápido e abaixo aqui vai ser mais lento. Então nossa primeira notação é pequena. Oh, e você pode ver que nós simplesmente não gostamos de dizer omicron como grande notação omicron que apenas leva muito. Então dizemos pequeno Oh, grande oh, e tão pouco Oh, bem aqui. Significa que vai ser mais rápido, que significa que o programa será sempre mais rápido do que este limite. Então, por exemplo, se nosso Barão estivesse no quadrado bem aqui, se tivéssemos pouco, oh, de no quadrado bem aqui, veríamos que isso significa que nunca vai se tocar e ao quadrado. Na verdade, vai ser sempre mais rápido do que no quadrado, por isso vai estar sempre acima desta linha, mas mais rápido do que no quadrado. E então o que podemos fazer é que podemos realmente usar isso para descobrir o salto. Então o próximo que temos é que temos grande Oh, e Big O significa que ele vai ser mais rápido, seu igual a. Então isso significa que vai tocar esta linha ou ser mais rápido, então vai ser na pior das hipóteses, e isso é algo que é muito importante aqui. Isto significa, na pior das hipóteses, que vai ser ao quadrado. O próximo que temos são dados, o que significa que não vai tocar em nenhum desses dois. Não vai diminuir. Não vai ficar alto. O que vai acontecer está bem nesta linha. Então, não importa o que vai ser no quadrado, vai ser ao longo desta linha em algum lugar. E então o próximo abaixo que temos é mais lento ou igual a que temos. Este é Omega, e este é mais lento igual a então ele toca esta linha e é sempre mais lento. Então, você sabe, nós ficamos tipo em terceiro para o quarto aqui em baixo, aqui em cima nós podemos ter como dentro Então é sempre mais lento do que isso, ou igual a n ao quadrado. Então, na melhor das hipóteses, este é, na melhor das hipóteses, ele vai ser executado neste se você colocar isso. Então, por exemplo, se nós direito de n quadrado, como assim cortar um pouco ali, mas de em Quadrado como então entendemos que este programa será sempre executado, ou na melhor das hipóteses ele vai ser executado está em quadrado, o que significa que pode correr pior do que isso, e, em seguida, abaixo que temos mais lento do que o que significa que ele sempre vai correr pior do que em quadrados. Pouco nunca toque e quadrado, mas vai correr pior do que no quadrado E então por que isso é importante? Por que queremos nos concentrar neste de todos esses? E isso é porque Big O dita o pior cenário e estamos preocupados com o pior cenário porque dada a probabilidade e as estatísticas são, programa pode tocar o pior cenário caso em um ponto e queremos saber, Sem dúvida, qual é o pior cenário? Então é por isso que usamos o grande Oh, é ver no pior. O que vai ser? E você pode ver que eu vou trazer o gráfico novamente aqui. Quando temos essa ideia, quando temos a capacidade de dizer, Qual será o nosso programa? Podemos começar a preencher este fim. Então, se nós temos, por exemplo, um, talvez grande o de dentro. Nós entendemos que, na pior das hipóteses, ele vai estar dentro para que possa estar dentro. Mas também pode ser qualquer coisa maior do que dentro. Então podemos preparar todos os nossos diagramas de tempo e esboços e qualquer coisa assim, partindo da suposição de que nunca vai para este lado da linha. Ele sempre vai para este lado, e isso é realmente poderoso porque agora podemos começar a comparar programas, piores casos, piores casos, e podemos começar a ver que pode ser quando um programa escala o, por exemplo, Se tivéssemos um programa de login versus um programa in, podemos ver que quando este escalar, vai ser pior do que este. Então vamos meio que tomar, uh, vamos quebrar isso um pouco e podemos meio que ver por que alguns desses são insignificantes . Então temos um programa que executa aquele pequeno oh no quadrado, que significa que é mais rápido do que no quadrado. Então isso significa que pode ser em qualquer lugar do quadrado todo o caminho até basicamente como nós apenas mais rápido do que ele. Então não vai ser no quadrado, mas pode ser qualquer coisa mais rápido do que no quadrado. E esta é uma espécie de grande Oh, mas a coisa é, nós não pensamos a coisa que nos é dada, então é um pouco de oh de dentro. Não podemos tocar nisso, então só deixa um pouco confuso. Nos dá um limite, mas não facilita. para vermos. Não podemos imediatamente olhar para isto e dizer, Oh, isto vai correr a tempo. Podemos olhar. Temos que olhar para isto e dizer: “Oh, “Oh, vai correr mais rápido do que acabar. Mas nós realmente não sabemos onde, e isso realmente não nos dá muito espaço de manobra. E então nós temos nossa grande notação O e isso é o que nós acabamos de passar é que podemos olhar para isso e nós vamos ser como, Oh, Oh, na pior das hipóteses, ele vai correr em muito tempo em Fada seria ótimo se nós sempre pudéssemos usar dados. O que é o? Isso é igual ou às vezes é usado como a média, mas na maioria das vezes significa igual ao fim, Então isso seria ótimo. Mas o problema é que os programas nem sempre funcionam exatamente ao longo da linha. Às vezes eles podem correr, você sabe, talvez em uma parte ele tem um fim. Mas em um ponto ele é executado, faça login e ele vai para qualquer lugar no meio. Estes dados são muito específicos para nós, ainda gosto muito. E então estes são praticamente insignificantes porque eles não nos dão muita informação . Pense nisso, este aqui, que é Omega So Omega em quadrado. Isso significa que vai ser mais lento ou igual ao quadrado ômega, que é como você está dizendo que nosso programa vai estar rodando no quadrado ou vai ser mais lento. Como vamos planejar com isso em mente? Porque mais devagar poderia ir para o infinito. Poderia ser o mais lento possível, e nunca seríamos capazes de nos preparar para isso porque nunca teríamos abundante. Seria como, Ok, então ele vai apenas correr em quão rápido ele poderia levar no quadrado. Pode levar em fatorial. Pode acabar com o infinito. Não nos ajuda a analisar o programa porque há um lado infinito nele. E exatamente a mesma idéia com o pequeno Omega aqui também é que ele vai para o infinito no lado ruim, o que não nos ajuda. pequeno Omega aqui também é que ele vai para o infinito no lado ruim, o Então isso nos ajuda porque o lado ruim é deixar eu apagar um pouco disso aqui e dar um pouco mais de espaço. Então isso nos ajuda porque o lado ruim. Então, digamos que aqui é para o infinito. Isso nos dá um limite, então qualquer coisa será na pior das hipóteses aqui. Mas poderia ser melhor e não nos importamos se ele voltar e correr essa constante, tudo bem. Isso é perfeitamente bom. Isso significa que nossos programas têm uma ótima camisa, mas podemos planejar isso. Significa que nossos programas são executados mais rápido do que esperávamos. Então o que poderíamos fazer então é planejar para o pior cenário. No entanto, se você for para o outro lado desta linha, você não pode planejar para o infinito. Então é por isso que Big Oh é tão importante é que é o mais útil de todas essas notações . Isso nos dá um cenário pior, e por isso é meio que tomar um exemplo de como podemos aplicar isso a um problema específico. Então, geralmente o que você sempre faz é usar o pior cenário, ou seja, em que ponto do programa não será o mais ineficiente. Então aqui, por exemplo, digamos que tivemos grande o de no quadrado. Tivemos um grande, uh em log em grande O de dentro, e então grande O de Constant Time, e então estes aqui em baixo são ótimos. Mas o problema é que não importa o que aconteça, sempre seremos gargalos por esse cara aqui. E isso é porque a nossa taxa de tempo de carregamento aqui está no quadrado, que significa que este programa vai executá-lo no quadrado mais no login mais o 2, o primeiro, que faz mantê-lo tipo de constante. Aqui vamos nós mais um. E você pode estar pensando, por que estou fazendo isso? E isso é porque você pode realmente adicionar cada parte dos passos juntos. Então, porque você faz essa parte, então você faz essa parte. Então você faz essa parte, então você faz essa parte para que você possa realmente adicioná-los todos juntos. Lembre-se do que estamos fazendo de antemão quando estamos falando sobre como estes como nós tentamos olhar para um programa como ele vai para o infinito. Então, se olharmos para este número, qual destes vai ultrapassar os outros quando formos para o infinito? Bem, por exemplo, vamos colocar em 1.000.000. Quão significativo é um milhão, que é certo um vai ser verso um milhão vai ser verso. Talvez em algum lugar em torno de três milhões vai ser versículo um quadrilhão ou talvez um trilhão 60 sentados foi um e 12 zeros. Este vai ser substancialmente maior. Estes vão ser uma porção menor e menor do número como ele vai para o infinito até o ponto onde estes irão chegar perto de zero como significância. Então você vai começar a ter, você sabe, um número do Google, que é 100 zeros mais talvez, como oito milhões aqui, algo assim. E isso significa que esta parte aqui é completamente insignificante neste momento. Então o que fazemos é eliminar os mais baixos, e o tempo de execução deste programa está no quadrado. E então vamos apenas tipo de cimento que com outro exemplo aqui, digamos que tivemos Big O. Então tivemos um grande O de quadrado grande O de In Squared Big O de Petroleos aqui Vigo de In Squared novamente. E vamos ver agora temos o grande O do final do terceiro. E agora o que temos aqui é que temos n ao quadrado mais no quadrado mais no quadrado mais no no terceiro, e assim podemos realmente combinar estes até três e ao quadrado mais no terceiro. E agora lembre-se do que falamos na última palestra sobre a notação em. Estes não importam. A constante aqui não importa. Porque à medida que entramos no infinito, isso se torna cada vez menos significativo. Até que uma vez chegamos a um número suficientemente alto, ele se torna basicamente zero para que possamos riscar esse para fora. E então agora temos no quadrado mais no terceiro. E então, claro, é claro, este vai decolar muito mais alto do que o outro programa dolorido acaba ficando em terceiro lugar. E agora, já que essas são todas grandes oh, notações que conhecemos no pior dos casos, nosso programa irá executá-lo em terceiro lugar, o que estamos agora. Nós temos este limite de em terceiro e infinito de tempo de execução vai por aqui, e agora podemos planejar que, no pior dos casos, teremos até o terceiro. E podemos planejar tudo de volta ao tempo constante, porque agora tudo o que temos é apenas amarrado aqui. Entendemos que, você sabe, se colocarmos em um pedaço de 1.000.000 de dados, pode não funcionar. Talvez possamos trazer isso, mas nos dá um lugar para começar. Nos dá um lugar para compará-lo com outros. Então essa é uma grande notação “O”. Muito importante. E com o tempo você vai começar. Basicamente, isso se tornará a segunda natureza. Apenas ser capaz de olhar para isto. Você nunca verá esses outros. Muitas vezes. Vais ver este. Às vezes. Se ele diz que um certo ponto de um programa é igual a este tempo de execução, então você verá este. Mas além dessa tese, você provavelmente nunca verá e provavelmente nunca verá o pequeno Omar Khan. Então essas notações aqui apenas as memorizaram, entendam o que elas significam, e você deve estar pronto para ir. Você vai começar a entender muito mais do tipo de documentos de ciência da computação. 8. Exemplo do mundo de grandes o: Não é. Aprendemos muita teoria. Vamos dar um revés e passar por uma análise de código do mundo real. Agora, eu não vou usar código complexo ou qualquer tipo de que você precisa saber aqui. É tudo pseudo código, e vou explicá-lo. Cada passo do caminho é se você nunca tocou no código antes porque é assim que eu quero explicar. Esse tipo todo, claro, é que estamos olhando para a teoria por trás de tudo. Não é o código, no entanto, aplicá-lo a algo que o mundo riel pode ajudar, você sabe, tipo de descobrir alguns dos conceitos, e é por isso que estamos fazendo isso. Então vamos dar uma olhada no nosso primeiro pedaço de código. Vou seguir em frente e passar por isso aqui. Então o que temos é que ele diz que eu escrevi em pseudo. Esse tipo de apenas lê na língua, algo que você pode olhar e entender o que está acontecendo. Então ele diz para cada dados na lista de dados, então vamos criar uma lista de dados aqui em uma segunda impressão. Dados para tela OK é suficiente. Digamos que introduzimos isto um pedaço de dados uma lista aqui que talvez seja de três a 10 e, em seguida, iria apenas búfalo. Então este é três inteiros e uma string. É assim que seria tecnicamente confidencial. Mas nem vamos olhar para isso. Estes são quatro dados. E então o que estamos dizendo é que para cada dado, então para cada dado em nossa lista, vamos imprimir esses dados na tela. Então, na nossa situação aqui, o que está em? Bem, nesta situação aqui mesmo em iguais, os 1234 porque temos quatro pedaços de dados. Então, nesta situação em igual a quatro Então agora vamos ver qual seria o tempo de execução disso. Então nós temos para cada pedaço de dados e, em seguida, nós imprimir para a tela. Então, ok, vamos descer a lista. Aqui. Vamos lá. Primeiro pedaço de dados. Então nosso primeiro pedaço de dados é três. Pegamos três da nossa taxa de documentos aqui, então este é o número zero. Uma matriz, ou, se você quiser pensar sobre isso, é 1234 Computadores geralmente ir com 0123 apenas do jeito que eles funcionam. Então vamos pegar nosso primeiro pedaço de dados aqui e então vamos imprimir na tela. Então pegamos nossos três que imprimimos para a tela. Então isso é um tempo de execução. Então, o tempo de execução agora é um. E agora vamos pegar o para porque vamos descer a lista. Então, para cada pedaço de dados, nós tocamos neste. Então agora vamos para este. Então agora pegamos dois e imprimimos para a tela. Então agora nossa tela se parece com isso. E então isso é tempo de execução adicional bem ali. Isso é um tempo de execução. E agora imprimimos nosso próximo pedaço de dados, que é 10. Então agora temos 32 10. Isso é tempo de execução adicional bem ali. E agora imprimimos búfalos, que seriam de 3 a 10 búfalos. E isso é um tempo de execução adicional porque tudo o que estamos fazendo é pegar o pedaço de dados e imprimi-lo. Não há nenhum processo de pensamento especial acontecendo aqui foram apenas agarrar, imprimir, pegar, imprimir, agarrar, imprimir. E agora, se somarmos tudo isso, veremos que ele sai para um mais um mais um mais um mais um, que é igual a quatro e então o tempo de execução nesta situação é quatro e você verá que nosso tempo de execução é igual à quantidade de fim aqui. E se pudéssemos pensar sobre isso teoricamente por um segundo, se tivéssemos um milhão de pedaços de dados aqui, não haveria, em nenhum momento, o programa onde teríamos que tocar mais de 1.000.000 pedaços de dados . Então, não importa o que façamos aqui é tempo de execução vai ser qualquer que seja o nosso fim, o que significa que o que temos aqui é um tempo de execução nesta situação particular, nós poderíamos realmente usar Fada como em, na verdade, é igual ao fim. Não há espaço de manobra aqui, mas vamos dizer que está pior, porque essa é anotação que gostamos de usar. manobra aqui, mas vamos dizer que está pior, porque essa é a Então este é um exemplo de um em que isso é chamado de loop for. Portanto, quatro loops são tipicamente, por exemplo, forno termina em uma situação. Vamos para um problema um pouco mais complexo aqui. Então deixe-me quebrar este também O que temos aqui é que ele diz para cada dado em uma lista de dados. Então isso significa que em vez de chamá-lo de pai e lá fora, cada pedaço de dados em uma lista vai estar em xeque se os dados estão na lista. Então, vamos, em seguida, ir para cada dados W nas listas de dados. Se n é igual a w imprimir. Verdadeiro. Então vamos em frente e meio que quebrar este um pouco também. Vamos com o mesmo exemplo de antes, que era três vírgula, duas vírgula , 10 búfalos vírgula assim. E nesta situação, nosso in ainda é igual a quatro. E agora o que vamos fazer é olhar para o primeiro problema aqui, então vamos dar uma olhada agora. Digamos que vamos pegar cada um desses pedaços de dados, então vamos pegar os três e agora está dentro. E agora, para cada pedaço de dados nesta lista de dados e você pode ver que esses nomes são exatamente os mesmos. Então isso significa que esta é a lista de dados. Estamos verificando os dois, então temos nossas três maneiras de pegar nossos três. E agora estamos tentando verificar se esses três aqui são equivalentes a algo aqui em cima, e a única maneira de fazer isso é citar força bruta. Então vamos levar estes três. Vamos verificar com a 1ª 1. Vamos verificar com a 2ª 1. Vamos verificar com a 3ª 1. Vamos verificar com a 4ª 1. Isso vai ser 1234 operações . Então, primeiro, vamos quebrar isso, tipo, muito longe aqui em baixo. Temos os nossos três. Pegamos nossos três, e agora estamos checando. Será igual? Deixe-me fazer isso um pouco menor vai ser um pouco maior de um gráfico. Então estamos dizendo, três é igual ao primeiro pedaço de nossos dados, que vai ser os três novamente? Porque não dissemos para começar com um número que não é ou qualquer coisa extravagante como essa . Só estamos checando essa lista uma segunda vez. Então temos nossos três e estamos checando. Não é igual ao 1º 1 Então é igual a três. Sim, faz. Então isso vai imprimir uma mensagem verdadeira, e isso levou uma operação. Agora faz. São três iguais a não. Então não publicamos nada. Essa é uma operação. Nossos três são iguais a 10? Não faz. Então essa é uma operação. Nossos três são iguais a búfalos? Não faz. Então essa é uma operação, e agora terminamos com os três. Então, seguimos em frente. Nós cuidamos dos três, então vamos criar um 2º 1 aqui em baixo. Vamos ver isto. O que? Vai ser aquele que vamos checar com o deles exatamente o mesmo. Mas eu só quero tornar isso um pouco mais visual para todos vocês. Então terminamos com três. Então vamos passar para os dois agora. Então faz muito igual. Três. Não faz. Essa é uma operação que faz igual a ela faz. Essa é uma operação que faz igual a 10. Não faz. Isso é o que a operação faz para igualar búfalos. Não faz. Essa é uma operação, e então vamos descer a lista. Mais um faz 10 igual a três Não é uma Operação faz 10 igual a não é isso que operação faz. 10. Igual 10. Ele faz. É quando a operação faz 10 igual a Buffalo. Não faz. Essa é uma operação que faz Buffalo. Vou abreviá-lo como sendo aqui, então quero continuar escrevendo. Búfalo. Buffalo é igual a três? Não faz. Então essa é uma operação que faz. Búfalo igual a ele não. Então essa é uma operação. Buffalo é igual? 10? Não faz. Então essa é uma operação. Búfalo é igual a Buffalo? Ele faz. Então essa é uma operação. E agora se adicionarmos tudo isso aqui, o que vamos ver é que vai ser 123456789 10 11 12 13 14 15 16. Então, nesta situação, nossa entrada era quatro, mas o tempo de execução era aproximadamente 16. E o que é que isso vem a ser? Bem, isso sai para ser no quadrado. Então, digamos que se pegássemos quatro e o quadrássemos, seria igual a 16. E podemos, teoricamente, pensar sobre isso também. Se expandirmos isto para cinco, cada um teria não só mais cinco aqui, mas temos de multiplicá-lo porque agora temos de verificar um adicional também. Então, cada instância única, terá cinco e terá um inteiro outros cinco, que o quadra assim, nesta situação, o tempo de execução está no quadrado. E a razão para isso é, mesmo que tenhamos 24 loops, há o que é conhecido como aninhamento. Nós aninhamos 14 loop dentro de outro quatro loop. Então esta parte aqui fora, vamos desenhar isto e ler esta parte aqui fora está dentro enquanto esta parte dentro está dentro também. Então o que fazemos é pegar o fim do lado de fora, multiplicá-lo pelo final, dentro, e entrar ao quadrado. E então esse será o nosso tempo final para esta situação. Então, como eu disse, este curso não é fortemente designado para escrever código ou para fora, e ainda é definida a teoria. Mas pensei que isto poderia ajudar a mostrar-lhe o que estivemos a falar este tempo todo. Como o código pode ser realmente analisado para que possamos entender essas diferentes partes. E você pode ver que não importa o que aconteça, nós acabamos de aprender algo muito importante. Quatro loops estão sempre indo para estar em, mas aninhado para loops são sempre vai ser como muitos aninhamento há. Então, se este aqui bem aninhado 1/3 1 isso seria uma fórmula em quadrado, e você começa a se levantar em números realmente grandes para começar a verificar todas essas coisas. Então, espero que este exemplo prático tenha ajudado você a entender esse conceito um pouco melhor. 9. 2-1 Como os dados armazenados: Então vamos começar a saltar para um dos próximos tópicos principais da ciência da computação, e essa é a capacidade de entender e manipular estruturas de dados. Estruturas de dados são a maneira de basicamente tirar dados, organizá-los e ser capaz de agarrar o acesso, salvá-los de certas maneiras que se encaixam com o nosso objetivo. Assim, alguns são mais rápidos do que outros em certos aspectos. Então, por exemplo, alguns deles vamos ocupar mais espaço enquanto sendo realmente, muito rápido acesso. Alguns deles não ocupam muito espaço, mas podem demorar um pouco para acessar. Alguns deles têm inserções mais rápidas. Alguns deles têm mais rápido remover ALS. Tudo se resume ao que exatamente você quer realizar em seu programa ou teoria ou em qualquer tipo de seção de ciência da computação em que você está indo. Então, a primeira coisa que pensamos antes de entrarmos nessas estruturas de dados, é que precisamos entender como, exatamente, os dados são armazenados, porque isso nos ajudará a começar a entender essas estruturas de dados e por que alguém pode tomar mais longo do que o outro e por que um poderia ocupar mais espaço do que o outro. Então a primeira coisa que precisamos fazer é primeiro. Como eu disse, entenda os dados. Então o que os dados são é É como, por exemplo, é algo algum tipo de zeros e uns que significam algo. Então, por exemplo, um três pode ser um pedaço de dados ou um texto inteiro, ou talvez um documento inteiro possa ser um pedaço de dados. E o que acontece em um computador é que esses tipos de dados são armazenados em, por exemplo, como um disco rígido, que está em seção em pequenas partes diferentes e essas partes de seção em mais partes E então dentro de um desses, você tem como clusters, que tipo de sair para se parecer com isso aqui. Então, por exemplo, talvez isso represente essa coisa toda aqui e o que cada uma delas representa é um pedaço de dados. E então cada um deles terá um endereço na memória, como um endereço para onde sua casa é. Se você quiser enviar um pacote, o computador usa exatamente a mesma coisa. Por exemplo, talvez este. Ele geralmente usa hexi decimal de modo que então eu vou usar Talvez este é 00 e então este seria então 01 E este símbolo zero com pouco X ao lado dele geralmente significa Hexi Decimal. Então é isso que estou usando para isso. Então continuaria continuamente aqui em baixo. Isso seria 020304 etc. E então por que isso é importante é porque uma vez que temos o endereço, podemos realmente pegar a coisa que está nesse endereço. Então, por exemplo, se pegássemos um pedaço de dados, digamos que tínhamos uma string ou um pedaço de dados que era três e quatro, assim E vamos dizer que três foram armazenados. Zero x 00 e quatro foram armazenados em zero x 01 Então agora, se quisermos pegar esses pedaços de dados, o que podemos fazer é criar uma tabela com esses tipos de dados e suas associações. Então, por exemplo, nossa mesa pode dizer três. Está guardado aqui. Isso é armazenado aqui, exceto que normalmente seria o inverso. Nós diríamos o que está em 00 e seria algum tipo de dados. O que é isso? 01? E seria algum tipo de dados. E agora, quando queremos realmente recuperar esses dados, podemos procurar o endereço ou vice-versa. Se quisermos ver o que há, podemos ir até lá e descobrir. Então, digamos que queríamos recuperar. Três. Queremos recuperar os três em nosso conjunto de dados. Então três está localizado bem aqui e quatro está localizado bem aqui. E assim queremos recuperar três. Basicamente, o que o nosso programa faz nos bastidores. Muitas vezes, menos que o seu programa em um nível muito baixo, que significa muito perto do dedo do pé como máquina, manipulando a máquina completamente e totalmente dentro de si mesmo, geralmente linguagens de montagem e coisas assim. Então tudo o que temos que fazer é dizer, você sabe, apenas var X é igual a três e com a máquina está fazendo isso dizendo, Ok, agora estamos associando X com o endereço zero x 00 Então, qualquer vez que o usuário usa ou chama X , nós vamos pegar o que está sempre em zero x 00 Agora o usuário vem aqui e ele, você sabe, cria uma nova variável. Por que é igual a quatro, E agora por que é associado ID com zero x zero vinho. Isso é o que o programa faz é dizer que tivemos o programa ir. O que é X plus? Por quê? O que é isso igual? Bem, o que ele faz é correr bem, então X está às 00 Vamos pegar o que nunca? Às 00 e nós vamos, ele escaneia para o disco rígido. Ele vai todo o caminho e encontra 00 e diz, Ei, tem um três aqui. Então os três, em seguida, é chamado, trouxe todo o caminho de volta para cima no processador, e então ele é armazenado em Ram, que é uma memória mais próxima do computador real. Mas isso é meio que está ficando muito, muito exigente e como os computadores funcionam. Mas tudo o que ele faz é agarrar isso e dizer, Este é um três. E então então agora dizemos que queríamos mais sobre o porquê e então ele faz exatamente a mesma coisa . Ele vai para baixo na sua lista. Ele encontra o setor, o cluster, o que quer que desça e diz, Oh, é um endereço ou um que ele retorna. Oh, o que é endereço ou o que um quatro vai todo o caminho de volta para cima e volta antes E claro, ele faz isso em quase tempo instantâneo, e então então ele pode fazer os cálculos que chamou. São duas partes de dados bem aqui. E agora faz o cálculo de sete. E isso é uma base de como os dados são armazenados em um computador. É apenas um tipo de endereços da Siri, e há diferentes maneiras de armazenar esse tipo de dados. Então, por exemplo, esta é mais uma maneira direta de armazená-lo onde podemos chamar o endereço especificamente. Que maneira disse que queremos alocar, vamos deletar algumas coisas aqui. Na verdade, o que podemos fazer é duplicar este slide aqui e vamos descer. Então vocês terão este topo, será duplicado e, em seguida, tipo de deletar fora dele e fazer um segundo exemplo aqui. Então essa foi uma maneira muito direta de dizer o que eu era. Se nós dissemos que temos esses dados, esta estrutura que vai ser entre aqui e aqui e seu endereço como um todo vai ser zero X 00 agora Se nós chamamos zero x 00 vamos dizer, Bem, vamos colocar alguns dados aqui. Se chamássemos zero x 00 não haveria dados específicos aqui. Estamos ligando para toda essa entidade, então isso não nos ajuda. Então o que podemos fazer é aqui que começamos a entrar. A próxima parte é que podemos realmente meio que em pequenos mini-nomes para cada um desses pequenos segmentos. Então isso é apenas 12345 E nós podemos usar esse tipo realmente básico de classificações porque nós temos nosso endereço principal bem aqui. E agora, já que temos o nosso endereço principal, o que vamos fazer é ir para o endereço principal, e então vamos usar um dos seus mini nomes para encontrar qualquer pedaço de dados estamos procurando. E isso é o que é chamado de array. E a próxima palestra. Nós realmente vamos começar a levar isso para o próximo nível, mas isso é chamado de array. Então o que podemos fazer é criar, salvar nossos X iguais e, em seguida, criar algo assim. E então agora ele armazena todo aquele pedaço de dados neste pedaço de memória e que agora se nós dissemos Return X de qualquer que seja o pequeno mini nome é. Então, digamos X de um. Agora ele vai chegar. Ele vai para o zero x 00 e então ele vai para o mini nome de um, que é um dois. Então ele vai voltar para e assim que é uma maneira diferente de olhar. Em vez de ter acesso direto, você poderia tê-lo segmentado em pedaços como este. E o que acontece é que isso geralmente é o mais comum. Porque se tivéssemos um endereço direto para cada peça na memória, estaríamos desperdiçando muito espaço e sendo algumasmesas realmente, realmente grandes, mesas realmente, realmente grandes, porque você tem que pensar que a memória não pode Ah, computador não pode criar memória na mosca como você não pode simplesmente armazená-lo em terra imaginária. Se ele quer armazenar cada um desses relacionamentos, ele tem que ter uma outra seção inteira de memória especificamente designada para armazenar memória. Então, se você tentar armazenar cada pedaço de dados como este, seu espaço começa a ficar realmente grande, e estes são todos conceitos. Vamos começar a quebrar à medida que formos mais longe. Mas eu só queria mostrar isso em um nível de cima para baixo para que você possa começar a entender como a memória funciona. E então quando entramos nessas estruturas de dados como um aumento, como árvores como listas vinculadas, você pode começar a entender como ele pode funcionar sob o tipo de capô em. Nós podemos entrar em um pouco mais de, você sabe, apenas esse entendimento, e uma vez que você entenda, você pode usá-lo melhor. Você pode manipular melhor. 10. Introdução de matriz de 2-2: Então vamos passar por cima da nossa primeira grande estrutura de dados, e isso vai ser o array e nesta situação, o array fixo. Então, o que é um array? Bem, em um ataque, por definição é uma Siris ordenada de acordo. E então tudo o que isso significa é que é um agrupamento de tipo de elementos semelhantes juntos. E nesta situação, os elementos semelhantes apenas significa que há um pedaço de dados assim em um raio no mundo da ciência da computação é apenas uma coleção como de dados ou uma realmente apenas uma coleção de dados que está tudo ao lado outro. E o que quero dizer com isso é que vamos passar por diferentes estruturas de dados mais tarde onde você pode ter um pedaço de informação aqui em um disco rígido e, em seguida outro pedaço aqui e ali, apenas ligado juntamente com algo chamado Ponteiros. Então é como, digamos, se quiséssemos representar a coisa abaixo aqui em baixo, teríamos algo assim. Mas poderia haver, você sabe, um monte de peças diferentes no meio, e um monte de peças diferentes no meio também. E isso não é o que em uma corrida é algo chamado uma lista vinculada. Então em um raio é quando eles estão todos juntos e você tem certos benefícios disso, você tem certas desvantagens disso. Mas uma matriz se parece com isso sempre que você representa. Visualmente, você tem esse segmento de memória, e quando você cria uma matriz, você normalmente sempre atribuiu quanto tempo você deseja. Estás a perguntar ao computador. Eu quero uma seção de seis pedaços de dados e o computador vai procurar pelo disco rígido, e então ele vai encontrar um lugar de seis, e vai te dar esse slot. Então, por exemplo, no nosso disco rígido, se pedirmos um lugar de três, ele iria olhar através, olhar lá e tipo, Oh, bem aqui nós temos uma seção de três. Então, ele lhe daria esses três pedaços de dados, e isso seria em código. É tipicamente representado por uma declaração de parênteses assim. Então você diria que algo como X é igual a esses colchetes, e isso significa uma matriz vazia. E então, se você quiser colocar informações nele, pode ser algo como X igual a 123 E isso vai apenas criar uma matriz que se parece um pouco com isso, onde você tem o primeiro lote de um, o segundo slot de para e o terceiro slot de três assim. Então é assim que seria representado em código. Agora, como é que uma matriz conta? O que é isso? Você sabe o que? É para que é usado? Uma das partes mais importantes é que a matriz começa em zero. Chama-se indexação zero. Isso significa que sempre que queremos agarrar o primeiro elemento sempre que queremos agarrar este elemento ou nesta situação, este elemento jamais iria querer agarrar um desses desenvolvimentos. Temos que começar no zero. Tem que ser este zero aqui. Isso é porque ah, muitas fórmulas de computador funcionam com zero. Na verdade, há discussões online inteiras sobre por que ainda usamos base zero. Costumava haver um monte de diferentes tipos de razões para isso e a razão que começou a cair. Mas o que quer que seja agora, ainda usamos base zero. Então, na matriz é sempre começando por zero. E isso significa que o fim é algo chamado em menos um o que está em menos uma média terminará nesta situação é apenas o comprimento da matriz. Então isso significa que o último vai ser em menos um. Serão só seis. Então isso, como você pode ver, contém sete peças de informação. 1234567 No entanto, se quisermos pegar a última informação, não pegamos sete. Pegamos seis, um pouco confuso no início. E muitas vezes, até mesmo cientistas veteranos da computação, eles se enganam o tempo todo. Eles vão colocar, eles vão colocar, você sabe, se eles estão tentando pegar o último elemento, eles vão colocar X de sete. E isso vai retornar algo chamado falha de sequência, que é apenas o computador dizendo, você , está acessando memória fora dos limites. Você está acessando a memória. Eu não lhe dei controle e linguagem mais fraca ou línguas que não têm salvaguardas nele. Bem, na verdade, apenas devolva o lixo que está lá, então isso é realmente chamado Ah, ataque de estouro de buffer é se você atacar esse lado direito, você pode hackear as coisas por isso. Mas isso é como as línguas realmente básicas como C, seja em um monte de salvaguardas. Mas sempre que tentamos fazer isso em algo como, Java vai nos dizer que a segunda falha foi acessar a memória que não foi concedida no disco rígido, algo mais está lá que nós não deveríamos estar tocando. E isso, como eu disse, é cancelado por um ar. Coloque a parte importante que você precisa para sair desta palestra. Esta introdução para corrigir um aumento é que um na matriz é apenas uma coleção de dados no mesmo lugar no disco rígido vai passar sobre a vantagem que na próxima eleição falamos sobre os tempos de execução. Mas isso é o que é. É uma coleção desses dados juntos. A próxima coisa que sabemos é o que é a parte fixa deste ia falar sobre diferentes arrays. A parte fixa disso significa apenas que nunca vai mudar. Então, nesta situação, se criarmos uma matriz de tamanho quatro, ela sempre vai ficar tamanho, pois não há código para fazer um ir maior e fazer ir menor. Uma vez que o enchemos , está cheio. Ou temos que sobrescrever algo ou excluir algo ou mover algo em outro lugar para colocar mais informações apreciadas. Mas, de qualquer maneira, essa é a introdução aos arrays fixos, realmente, realmente precisa de estruturas de dados, e vamos pular em um pouco mais da gritty nitty de como você realmente usa essas coisas e o que seus vantagens são. 11. Horários de execução de matriz de 2-: Vamos dar uma olhada mais profunda nas matrizes fixas e vamos olhar para seu tempo de execução, realmente usando as coisas que aprendemos na última unidade, você sabe, a análise de tempo jumbo jumbo que vamos tomar que estamos realmente vai ser implementá-lo e olhar para as velocidades de diferentes tipos de funções dentro do array. E então seremos capazes de tomar esse tipo de velocidade e será capaz de olhar para diferentes estruturas de dados será capaz de compará-los juntos. Então é isso que vamos fazer. Vamos ver algumas das vantagens. Nós vamos estar vendo algumas das desvantagens, e nós estamos apenas indo para mergulhar profundamente em que matriz fixa é e por que você pode usá-lo. A primeira coisa que vamos rever é inserção aleatória. Então, há algo que temos que nos unir. O que vamos estar falando sempre que falamos sobre uma inserção, uma exclusão ou até mesmo pesquisar o que queremos dizer com uma inserção é se temos um conjunto de dados que queremos manter no mesmo tipo de ordem Então, por exemplo, todos os dados são importantes em todos os nossos exemplos. Então, se tivermos um um, dois ou três, não temos. Quando dizemos “inserir”, não queremos dizer “toe” sobrescreve algo chamado “replace”. Então não estamos falando de, você sabe, mudar isso para um dois. Então é 2 para 3 ou mudar este 1 para 2 ou, você sabe, você sabe, fazer o que for. Não é sobre que uma inserção está inserindo entre aqui ou inserindo em um lugar ao redor dele. Então, por exemplo, na inserção seria Este é um espaço em branco e queremos inserir um três aqui. Ou inserção pode ser que depois de um, queremos inserir um três. Então, como vamos fazer isso? O produto final? O que queremos é que queremos algo que apareça como 132 e então isso é o em busca, e isso é o que queremos dizer com uma inserção aleatória. Então, qual é a hora dessa inserção aleatória? O que será preciso se quisermos inserir algo aleatoriamente aqui? E vamos em frente e deletar ah, alguns dos elementos traseiros. Então temos algo para trabalhar aqui e aí vamos nós. Então qual é o tempo que vai levar para inserir algo em uma matriz fixa? Bem, o tempo acaba sendo O até o fim ao fim. Então, exatamente por que é até o fim? Bem, vamos dar uma olhada nisso. Este exemplo aqui meio que mostra isso. Sempre que estamos inserindo aleatoriamente, temos que assumir que não sabemos onde ele vai ser inserindo. Pode estar inserindo aqui. Pode estar inserindo aqui. Pode estar inserindo no final ou no início. Mas o que sabemos é que, a menos que seja final, teremos que mover alguns dados. Então vamos ter que pegar esses dados, e queremos desviá-los todos para caber esse outro pedaço de dados. Então, por exemplo, digamos que neste exemplo, aqui em cima temos um vamos estender isso para fora, e digamos que queremos inserir outro número que queremos aqui. Queremos inserir um quatro. O que vamos ter que fazer, que quantidade de trabalho ou vamos ter que fazer para colocar aqueles quatro lá dentro para fazer isso, nós vamos ter que pegar os três. Ou, na verdade, vamos começar o fim aqui. Então, vamos levar os dois. Vamos movê-lo, vamos pegar os três, vamos movê-lo, e então vamos pegar os quatro, e vamos inseri-lo. Então isso vai levar quantas operações vai no máximo, ele vai levar todo o array. Vamos ter que mover cada elemento sobre e, em seguida, mais a adição do novo elemento. Quantos elementos disso? Bem, essa é a nossa confiança em termos de um. Lembre-se que em é o comprimento do nosso tamanho de todas as partes de dados que estamos tentando inserir. Então, quantas operações iam fazer? Bem, todos os dados atuais vão exigir uma Operação um movimento para mover três, mover por movimento. Então isso vai ser dentro. Na melhor das hipóteses. Vai ser apenas uma constante de inserção regular, por isso vai ser apenas uma. Mas é aqui que fica complicado. Temos que olhar para a média. Qual é o tempo médio que vai levar para continuar inserindo em um gráfico ou em uma matriz aqui, e é aí que temos o nosso final escrito bem aqui. É esse o tempo médio que vai levar? É algo como, Oh, em mais de dois e você pode pensar sobre isso. Se mediarmos uma distribuição normal , colocamos em pontos aleatórios diferentes. Estatisticamente e probabilidade sábia, ele vai inseri-los no, uh, pelo menos a mesma quantidade para cada uma das células. Então digamos que o inserimos. Eu não sei, 12 vezes a probabilidade sábia, nós deveríamos chegar aqui, aqui, para baixo a lista fora de um lugar diferente para inserir. E isso significa que aqui em cima, vai demorar vezes cada vez. E então aqui vai levar menos um em menos dois em menos três e menos quatro e menos cinco em menos seis. Então vai levar tempo constante, e assim que as médias para todos eles combinados sobre o que vai, em seguida, dar-nos o nosso em mais de dois. E lembre-se, estamos falando de tempos de execução. Temos que riscar o que conseguirmos. Isto é apenas um 1/2 na frente. Então nós só riscamos. E então isso significa que nosso tempo médio acaba sendo exatamente isso dentro. Então uma inserção aleatória está no tempo. Então, o que é inserção na frente? Mas estamos falando disso, e essa é a parte lenta de nossas inserções. inserção na frente vai ser o para o N também. Deixa-me livrar-me disto aqui. Então, em certa parte da frente vai ser O até o fim. Lembra quando estávamos falando sobre o exemplo antes? Dissemos que se entrarmos na frente, seria o pior cenário. Vamos pegar tudo e movê-lo por um. Então isso vai ser o O até o fim. Agora, o que acontece se inserirmos na parte de trás? Então, vamos inserir neste lugar aqui? Bem, esta é uma inserção muito fácil. Podemos colocar um três aqui. Se quiséssemos você e o inserimos. É um tempo constante. Tudo o que é preciso é uma única operação que é tomar o número. Coloque-o dentro. Não importa quantas peças temos. Isso pode ser, você sabe, isso pode ser zero e, em seguida, 10 2030 40 50. E nesse monte de números entre eles, não importa. Nós só vamos dizer, você sabe X de 50 é igual a três e agora é igual a três. É sempre tempo constante. Então é por isso que, com uma inserção de matriz na parte de trás é tempo constante também. Agora, então, deleite em uma exclusão significa que vamos excluir o elemento. Mas temos que nos lembrar, manter a integridade. Vamos levantar todos os zeros aqui para voltar. Isso significa que temos que manter a integridade. E então o que isso significa? Isso significa que se tirarmos um sete, se removermos os sete desde o início, o que precisamos fazer é ter certeza de que o resto deles caia para trás em direção a isso. Então vamos em frente e fazer um pequeno exemplo aqui em cima. Digamos que temos um monte de números, como então temos uma matriz 1234 que é tamanho para, mas a indexação lembrar é começa em zero. Então, digamos que queríamos remover um do nosso conjunto de dados. Bem, o que quer que removamos o do conjunto de dados, não podemos deixar um espaço vazio aqui que não mantém a continuidade dos nossos dados . Se tentarmos agarrar o primeiro elemento, assumimos que, sabe, talvez tenhamos um algoritmo e sempre tentamos agarrar o primeiro elemento assim. Vai sair do ar. Não há nada lá. Então o que precisamos fazer sempre que apagamos da frente é que temos que fazer exatamente a mesma coisa. Temos que voltar, voltar trás, voltar para trás. E como você pode ver o que conversamos antes, qualquer coisa que vai exigir que nós voltemos um monte de vezes vai ser O para o fim. Delish em aleatório é também ir para o fim também. Então, se pegarmos qualquer tipo de exclusão aleatoriamente aqui, seria devido. O fim agora na matriz também tem esse bom benefício de ser capaz de excluir da parte de trás em tempo constante porque não temos que mudar nada. Então, se quisermos apagar os quatro da parte de trás, tudo o que temos que fazer é apagar. Então, em código, você sabe, pode ser algo como X de três igual a não são aspas vazias ou o que quer que seja para torná-lo vazio. De qualquer forma, é assim que é simples. É operação Zingale. Nada mais tem que entrar, então também é dever à mulher tempo constante. Então este ar este ar, o curto prazo, que eu vou usar às vezes é tempo linear. Então estes são todos tempos lineares. Este é o tempo constante, linear, constante. E eu só quero te ensinar esse voto agora porque, como eu disse, eu poderia trocá-los no futuro e dizer, Oh, para o 10 para o N Cada vez fica um pouco cansativo. Então, muitas pessoas só vão dizer Constante, eles vão dizer, linear aqueles tão exponenciais. De qualquer forma, vamos ver o nosso último. Quanto tempo leva para procurar algo? A lista de pesquisa e não classificada. Isto aqui é desordenado. Temos sete. Temos 89 10 e depois um. Então não há nenhum tipo de ordem aqui. Nós realmente não sabemos a ordem. Então, quanto tempo vai demorar? Digamos que queremos ver é um presente de nove. Bem, não há riel. Maneira rápida de fazer isso. O que temos que fazer é fazer o método da quarta força bruta. Isso significa que temos que começar aqui. Este mal é negado? Não. Passar para o próximo. Esta é a sequela hoje à noite? Não. Passar para o próximo. O single é o nove? Sim, é. Mas se estivermos, por exemplo, à procura de 90, estaríamos tipo, “ Não”. Não, não. E vamos até a lista até acabarmos. Até chegarmos a um espaço aqui que não tenha nenhuma informação. E então voltaríamos. Não, não é igual a 90. Então essa operação acaba sendo como as outras. Oh, o fim. Porque na pior das hipóteses, nós vamos ter que descer cada um destes e chegar até o fim para descobrir se ele realmente existe dentro da matriz, podemos ter sorte. É claro que às vezes pode ser no início. Às vezes pode ser dois ou três elementos dentro, mas em uma base média, o pior caso é que vai ser devido até o fim. Então isso também vai ser tempo linear. E depois a última, a última vez. Na verdade, vamos dizer para a próxima palestra porque isso vai funcionar antes, um pouco de aprofundamento na razão pela qual uma matriz de busca classificada sai para fazer login. E então você pode estar olhando para isso agora dizendo: “ O que isso significa? É por isso que vamos aprofundar exatamente por que essa busca classificou o mesmo log de fim. Mas eu só queria rever mais uma ou duas coisas nesta palestra, e então vamos em frente e saltar para aquela palestra. A última coisa que quero é saber o que isso tudo nos diz? O que isso nos diz sobre as vantagens e as desvantagens de uma matriz que podemos ver imediatamente que para armazenar dados que todos têm uma espécie de integridade para eles, talvez em uma taxa não seja o melhor para como se tivéssemos Ah, programa que precisa inserir e elite constantemente porque cada vez que inserir excluir, ele será devido até o fim, especialmente se estamos inserindo para a frente ou aleatoriamente dentro dele. E nós realmente temos outras estruturas de dados que podem fazer todos esses tempos constantes. Então talvez algo assim não seja muito importante. E algo que não está por aqui, mas temos tomado como certo é a capacidade de apenas verificar o que está em cada um desses elementos. Só posso dizer, sabe, que posso ligar, exceto três. Eu posso chamar esse elemento, e ele vai me dizer instantaneamente que 10 está lá. Isso é outra coisa que é uma grande vantagem para uma corrida. É tempo de acesso constante? Isso é outra coisa que talvez não comparemos muito com os outros. Mas chama-se tempo de acesso. Quanto tempo leva para chegar a um elemento dentro da matriz e nesta situação, todos esses tempo constante de ar? Isso é o que um tipo de array lhe dá é a capacidade de começar em algum lugar e, em seguida, ir para qualquer um desses elementos e chegar a ele imediatamente. Então o tempo de acesso é constante, e isso é muito importante. Se, por exemplo, digamos que não temos um programa que tira e insere muita informação com o programa que de vez em quando faz isso. Mas na maioria das vezes é só checar lugares diferentes. Estamos apenas armazenando informações diferentes aqui, e então nós somos como, então, os programas tipo, ok, eu preciso do número três, o que é o número três? E o número quatro? O que está no número quatro e, em seguida, está constantemente a enviar essa informação para trás e para a frente. Mas na maioria das vezes. Isso permanece entre aspas estáticas, o que significa que não muda. É aí que uma matriz pode ser útil. Temos aquele tempo de acesso muito rápido, e vai fazer tudo ir muito mais rápido. No entanto, como eu disse, se estamos inserindo na liderança o tempo todo, talvez queira olhar para uma estrutura de dados diferente de qualquer maneira, vamos saltar para que realmente precisa exemplo da pesquisa classificada, e vamos ver por que isso sai para fazer login 12. Algoritmo de pesquisa binária (pesquisa de matriz: Então vamos rever o que conversamos na última palestra. E isso vai ser a busca de matriz fixa ordenada. Então, por que isso é diferente? Por que isso nos ajuda a chegar a esse tempo de execução interessante do log em que é substancialmente mais rápido do que o O até o fim. A versão não classificada. Isso vai ser muito mais rápido do que por que quando resolvermos isso, temos essa vantagem? E isso é porque fazemos algo chamado tipo binário. Então vai ser um algoritmo de ordenação binária ou um algoritmo de busca binária. Foi mal meu. Um algoritmo de busca binária. A razão pela qual isso nos permite fazer um algoritmo de pesquisa binária é por causa da maneira que ele configurou. Então imagine a velha maneira de fazer isso. E esse é o método da força bruta. Digamos que estamos tentando descobrir se 19 existe? Então, estamos tentando descobrir que 19 existem como Então, para fazer isso com um método de força bruta, vamos desde o início. Está aqui? Não. Não, não, não. E continuamos a descer a lista. E, claro, pode não estar na lista e, portanto, temos que passar por toda a lista para descobrir isso. Ou pode estar a meio caminho da lista ou perto do fim, ou talvez logo no início. De qualquer forma, na pior das hipóteses, vai levar que toda a lista vai levar O até o fim dos tempos. No entanto, com uma pesquisa binária, podemos garantir que está em Lee indo para tomar log de tempo final e log de no tempo é como eu disse, é muito mais rápido. Lembre-se quando você está falando sobre login e os tutoriais anteriores, ele vai assim, o que significa que no início, o número fora do número de elementos que temos. Então vamos dizer que isso indo para a direita aqui, este acesso vai ser o número de elementos em que temos. E este é o tempo que leva. A pesquisa ou o tempo de execução são tempo de execução. E então o que isso vai nos dizer é que com o Mawr em que nós temos essa execução, tempo diminui de modo que em algum momento nós saímos como 32.000 e será basicamente o mesmo tempo de execução em 64.000 que é basicamente o mesmo tempo de execução que 128.000. Vai subir mais devagar e mais devagar a cada vez. E assim isso acontece por causa da maneira como a pesquisa binária funciona. Então vamos em frente e passar por esse exemplo. Como iríamos passar? Como procuraríamos uma matriz fixa? Bem, o que fazemos é ir em frente e fazer esta pequena fórmula. Chama-se esquerda mais direita para. Então tomamos a esquerda mais a direita, e então vamos em frente e dividimos isso por dois. Então essa é a nossa fórmula. Então vamos em frente. Vamos pegar isso e vamos realmente mover isso para cima porque nós vamos estar referindo muito isso enquanto fazemos isso. Então esquerda, mais, direita para. Então o que resta vai continuar e ser a parte esquerda. Vai ser o número que temos à esquerda, se isso faz sentido. Então, nesta situação, é uma matriz completa. São à esquerda, é zero e são à direita é a direita completa à direita aqui, que é o 10. Vamos pegar esses dois números, vamos juntá-los, e então vamos dividir por dois. E esse é o índice que vamos procurar no início. Então isso significa o nosso primeiro passo aqui. Vamos pela esquerda. Vamos manter os números iguais aqui. Vamos pegar a esquerda, que vai ser zero, e então vamos em frente e adicionar a direita, que é o 10. E eles iam dividir isso por dois. O que, é claro, só sai para 10 dividido por dois, que é cinco. Então, nosso primeiro passo, pegamos o índice cinco aqui. Então vamos em frente e pegamos o índice cinco. Vamos em frente, pegamos, trazemos de volta e damos uma olhada. O que é isso? Então, o que é ex de cinco? Bem, ele retorna 12. Então agora nossa próxima decisão é 12. Menos ou é maior do que o número que procuramos? Bem, 12 é menos do que o número procurava. E lembre-se, este é um array ordenado. Então, se 12 é menor que o número que procuramos, por que procuraríamos deste lado? Nós já sabemos que isso está resolvido, então quero dizer, tudo antes disso vai ser menor que 12 e sabemos que nosso número é na verdade maior que 12. Sabemos que 19 é maior que 12. Então 19 tem que estar deste lado. Portanto, tomamos este lado todo aqui e saímos. Nem sequer olhamos para ele. Não vamos tocá-lo. Nós não vamos verificar o que está lá porque nós confiamos que este array ordenado. Portanto, vamos em frente e vamos para a direita. Vamos dar uma olhada no lado certo, e então vamos fazer nossa pequena fórmula mais uma vez. Então vamos em frente e pegue a esquerda e a esquerda é agora um cinco. Normalmente, porém, já procuramos isso. Não precisamos de fazer. Olha para isto. Então nós estamos realmente indo, uma vez que é maior do que nós adicionamos um a ele. Se fosse menos do que tiraríamos um. Mas vamos em frente e começar com seis agora, então vamos em frente e ir com seis, e então vamos adicionar um, uh, uh, mais o lado direito, que ainda é 10. Divida isso por dois. E esta situação, nós realmente vamos ter um 16 dividido por dois, que vai ser igual a oito. E para que nós vamos olhar para a seção oito ou índice oito aqui, nós vamos dizer, o que é isso? Índice oito. Vamos dar uma olhada. E, claro, X de oito. Bem, isso devolve um 20. Bem, é 20 maior do que ou é menor do que o nosso 1920 é maior que 19. Então nossa segunda busca foi bem aqui. 20. Vamos dar uma olhada. Percebemos que é uma lição. Então vamos para a esquerda. E isso significa que Ei, nós não precisamos desta seção inteira aqui. Então agora vamos em frente e pegar o oito menos por um, e então vamos pegar o que sobrou. Então, a parte esquerda deste é seis. A parte certa é sete. Então vamos continuar a descer a fórmula. Então vamos em frente e pegamos os seis e depois adicionamos aos sete nesta situação, somados a sete. Então dividimos isso por dois, e temos 13 divididos por dois. Agora, isto é importante. Temos 13 divididos por dois. Com isso, normalmente fazemos algo chamado truncamento onde isso não é igual a 7,5 nesta situação . Ou, na verdade, nada disto seria 6,5. Isso não é igual a 6,5 e nós não arredondamos para cima. Não contornamos tudo. Fazemos o que chamamos de truncamento, que é apenas truncar o back-end. Seja o que for, apagamos e pegamos o número inteiro. Tomamos qualquer que seja o número no início é o número inteiro. Então, por exemplo, se tivéssemos um 7,9, ainda seria sete. Tínhamos 7.3. Ainda seriam sete. Se tivéssemos 7,98 ainda seriam sete. Isso é o que é truncamento. Então é isso que fazemos. O que quer que façamos esta fórmula. Então nós truncamos e verificamos seis. Vamos em frente e damos uma olhada no seis. Damos uma olhada no seis e conseguimos o número 17. Fazemos nosso pequeno processo de novo. Bem, nós sabemos que está certo e nós podemos realmente fazer a fórmula mais uma vez aqui e geralmente temos como um cheque. Se é o último elemento, basta olhar para o elemento dele. Está aí? Não é seguir em frente? No entanto, podemos fazer tudo de novo. Nós podemos fazer. O sete é à esquerda. Mais sete é o direito dividido por dois. Então isso é 14 dividido por dois, o que é igual a sete. Então fazemos a fórmula que verificamos é sete. Aqui é 19 igual a 19. É. Isso significa que aqui vamos em frente e vamos checar. É assim que esta fórmula faz. Leva e toda vez que o divide ao meio. E essa é a parte importante aqui. Compreender é que cada vez que dividimos o problema e 1/2 então isso significa, por exemplo, se começamos com oh, eu não sei, como 128 itens diferentes após a primeira geração estavam apenas verificando 64 itens. Depois disso, estamos verificando 32 itens e depois disso estamos verificando, você sabe, 16 e em oito e depois quatro e depois dois e depois um. E a coisa é que, porque isso dobra cada vez, o número de passos só aumenta. Aumenta mais devagar e mais lento. Então, por exemplo, cada um deles é um passo. Então nós temos 123456 e fomos para rever isso várias vezes ao longo deste curso porque é tão importante em tantas áreas diferentes. Mas o que temos aqui é que 128 equivale a 6 passos de Onley. Agora, se dobrarmos isso, se formos mais um passo adiante Então, em vez de 128 itens, temos 256 itens Will 256 só é igual a sete. Só damos mais um passo para chegar lá. E então, é claro, poderíamos descer outro, que vai ser 512. E isso é apenas qualquer igual a oito e assim por diante e assim por diante e assim por diante. Então percebemos que aquele gráfico de que estamos falando não não é tão feio. Tem um gráfico. Nós temos esse gráfico de que estamos falando, onde ele vai para cima e sobre onde o número de em que obtemos a mudança, o tempo de execução, este é o tempo de execução da esquerda fica cada vez menos e menos e menos e menos e menos ao longo do tempo. E que este padrão aqui, isto é chamado de Login. E se nós realmente aplicamos, se nós realmente colocar no log de 512 ele realmente nos pega. Ele produz oito. Esse é o padrão. Esta é apenas a maneira que os matemáticos representam. Este padrão é através de uma coisa chamada log. E é por isso que o tempo de execução sai para registrar. Porque este pequeno padrão complexo aqui, não é realmente muito complexo. Uma vez que você se conecta a um computador, é como seis linhas de código. Mas este padrão aqui realmente faz a coisa toda. Ele faz isso e corta ao meio cada vez para que tenhamos o registro no tempo. E, portanto, uma vez que podemos fazer isso lá, podemos usar essa busca binária para fazê-lo. Nosso pior caso, tempo de execução, pode ser reduzido para apenas log de n 13. 2 a 5 matrizes circulares: na última lição, discutimos um aumento e como podemos adicionar subtrair. E então também discutimos o tempo desses raios, como o quê? Todo tipo de operação, quanto custa. Então, se você quisesse responder aleatoriamente, poderíamos fazê-lo basicamente instantaneamente. Mas se quiséssemos inseri-lo na frente com respeito a, como o resto da corrida, temos que empurrar o resto do raio para trás teria que ir tudo dentro. E todos esses tipos de, você sabe, eles assumem que nós não estamos superando. As coisas que eles assumem que estamos gerenciando nossos dados de forma eficaz porque não estamos excluindo substituindo ou indo muito longe de nossos limites de array. Então, estes são basicamente os limites de matriz que criamos, mas podemos realmente melhorar em um deles, e este vai ser este aqui, o inserto na frente criando algo que é conhecido como uma matriz circular. Então, em teoria, o que estamos fazendo é a matriz e a memória sempre vai ficar assim. Sempre vai ser um bloco que vai desde, você sabe, você sabe, o início, todo o caminho até o fim assim vai ser alocado e então vai ser preenchido, e isso é sobre isso. Você realmente não pode fazer isso como qualquer outra coisa. Mas estamos teoricamente fazendo é que vamos descobrir uma maneira que podemos pegar isso chegar e nós poderíamos torná-lo em um raio circular, que é assim. Então, por exemplo, evidente agora e agora nós vamos realmente pegar este array, e nós vamos fazê-lo neste círculo bem aqui. Sobre o benefício disso é agora que se queremos inserir algo, digamos que temos 123 se quisermos inserir algo na frente. Digamos que esta é a frente. Tudo o que temos que fazer é olhar para trás e inseri-lo ali mesmo. E quão rápido com isso. Isso foi tempo constante, o que significa que podemos realmente melhorar a inserção na frente como tempo constante criando esta matriz circular. E então o que vamos fazer é que isso é um pouco difícil implementar em código, mas a teoria por trás disso não é tão difícil. Então vamos ter o que é conhecido como Ponteiros. Vamos ter um que aponte para o topo bem aqui. E eles iam ter um que aponta para o fundo bem aqui. E ambos vão apontar exatamente no mesmo lugar agora porque este de cima, este de cima, vai ser a frente da nossa direita. Vamos ter algo que nos diga que isto é a frente, e vamos ter algo que nos diga que aqui é a parte de trás. E então agora, sempre que inserimos na matriz e estamos dizendo que não estamos fazendo inserções aleatórias estavam apenas fazendo inserção na parte de trás ou inserção da frente da matriz. Então estamos inserindo na parte de trás agora, ou na frente. Ambas apontam exatamente para o mesmo lugar. Vamos em frente uma inserção, um número bem aqui. E agora que inserimos um número em nossa matriz, podemos então pegar o verso e dependendo de como você implementá-lo. Assim, por exemplo, podemos sempre inserir um mais qualquer que seja a parte traseira apontada, ou podemos apontar a parte de trás para o próximo espaço disponível. Eu vou apontar para o próximo espaço disponível então nós enchemos este agora e na parte de trás é realmente movido para cá. Então agora ele está apontando para aqui assim E então agora nós temos isso estão de volta, é apontado para aqui, e então vamos em frente e inserir outro número. Então nosso programa, nós podemos simplesmente, na verdade, se escrevermos isso em um programa, nós poderíamos realmente fazer algo assim. Poderíamos voltar X, e ele vai nos apontar para o lugar exato que queremos preencher. Então vamos X de volta igual a seis. E agora podemos colocar um seis aqui. Vamos fazer exatamente o que fizemos antes. Vamos selecionar isto aqui. Deixe-me pegar uma seleção aqui para que eu possa selecionar. Vamos pegar esse elemento, e então vamos movê-lo para a próxima parte aqui, e de alguma forma parte da minha flecha não sobreviveu com isso. Então vamos bem, parte disso eu ia ficar lá. Então o que temos agora é que a parte de trás é movida por cima de um. Então agora estão de volta é apontado aqui, e assim tudo vai bem. Mas o que podemos fazer agora é porque temos essas dicas nos dizendo para onde exatamente tudo está indo. Podemos realmente inserir a frente sem fazer um sem ter que empurrar tudo para a frente. E isso é porque em vez de empurrar tudo para a frente, vamos apenas mover o ponteiro para trás. Então vamos inserir a frente agora vamos em frente e inserir a frente. Então, por exemplo, poderíamos ir, hum, nós vamos x de frente é igual a algum número, mas você vai notar que nesta situação a frente está realmente apontada para a frente. Então o que podemos fazer é ir x de frente menos um, e isso vai nos levar para o local bem ao lado dele. O menos um ponto. E poderíamos ter feito o que fizemos com a parte de trás onde removeu e disse fazendo isso. Mas eu queria fazer os dois lados aqui, então estamos fazendo X de frente menos um é igual a sete. E então isso vai nos levar ex de negativo igual a sete. Mas isso não funciona. Não podemos acrescentar um inju negativo. Nosso raio terá uma segunda queda. Vamos sair dos nossos limites. Números negativos não aparecem em um aumento. Então o que podemos fazer e disse é que ele realmente vai fazer este algoritmo aqui onde nós vamos tomar o qualquer número é. Então nós inserimos em um negativo e nós vamos adicionar quantos, hum, hum, pontos existem aqui e então você pode ver que há 123456789 10 11 12 Porque lembre-se, isso está em menos um. Aqui, isto é em menos um. Então isso significa que o nosso em é igual a 12. Então vamos fazer é pegar o limite ilegal e vamos adicionar a ele. E neste caso, Então é negativo um mais e então estamos adicionando como 12. E isso vai nos dar a posição de 11. Então, agora, quando vamos para este negativo, nós vamos então re associá-lo, e nós vamos realmente inserir isso na parte de trás, certo? Assim, insira este sete aqui na parte de trás do raio. E agora o que vamos para Dio é pegar esse elemento e vamos arrastá-lo até aqui assim E agora a frente do nosso raio é Deixe-me ir em frente e correr até lá para não chegarmos a nenhuma flecha aqui. Então agora a parte de trás ou a frente da nossa taxa está na verdade na parte de trás da nossa direita, e então isso fica um pouco confuso. Você está tipo, o que é a frente? O que é a parte de trás? Então nós temos que não pensar nisso assim, nesta linha reta mais. Temos que pensar nisso como se estivéssemos enrolando isso em círculos. Então nós estamos fazendo é fazê-lo para emular essa onda é que nós estamos realmente tomando a frente e a parte de trás nós estamos mantendo o controle deles, e isso nos permitirá inserir em ambas as posições, apenas chamando um certo número e inserindo Lá. E isto vai continuar por aqui enquanto este vai continuar por aqui. E, claro, você pode chegar a um ponto em que eles começam a se sobrepor um ao outro. E mais uma vez, isso não é algo que estamos tentando lidar com você. Isso é um erro. Se alguma vez tiveres a tua frente e as tuas costas tipo de tentar atacar exactamente a mesma área. Isso é um erro da sua parte na implementação do seu programa e terá que ser abordado em algum lugar. Mas isso não é sobre o código. Isto é sobre a teoria. Então, com isso, o que criamos aqui com este raio circular adicionando os ponteiros dianteiros e traseiros e, você sabe, eles poderiam ser apenas variáveis que literalmente nossos números. Então podemos dizer agora frente é igual a 11. Enquanto nós poderíamos dizer volta é igual a dois e então se nós alguma vez quiséssemos inserir, nós poderíamos apenas ir x de volta como nós fizemos lá em cima é igual a algo. Ou podemos ir x de frente menos um. E eu fiz ambos o menos um e o exato nisso porque, como eu disse, eu só queria mostrar os dois caminhos, mas você pode querer mantê-los meio parecidos. Hum, então deve ser para trás menos um e frente menos um ou para trás e para frente. Será confuso se um deles for diferente do outro. Mas o que estou tentando dizer aqui é que temos essas variáveis e são muito fáceis de acompanhar. Depois de criarmos algo, dizemos “frente” mais um “traseiro” mais um “ou o que for”. Nossa frente menos um atrás mais um e então podemos continuar ligando. Começando na parte de trás, na frente deste raio, nós o tornamos circular. E através de tudo isso que criamos, podemos riscar o o de dentro e com um raio circular são tempo de inserção realmente se torna o de um. 14. 2 a 6 matrizes dinâmicas: até este ponto, nós meio que ignoramos um caso importante. E esse é o fato de que um aumento pode encher e o que fazemos, ganhar um aumento, encher. Nós temos discutido antes deste ponto basicamente o que são conhecidos como arrays fixos, que são levantados para que uma vez que eles chegam ao fim, uma vez que eles estão cheios de capacidade, nada mais acontece. Você vai ter que sobrescrever alguma dúvida, um subsídio para apagar alguns dados. De alguma forma, um compromisso terá que ser feito. No entanto, há uma espécie de matriz que pode crescer com o seu programa, e isso é chamado de matriz dinâmica. E então o que vamos discutir nesta palestra é o aumento dinâmico de como eles funcionam e alguns dos tempos de execução que podem estar associados a tal aumento. Então a primeira coisa que precisamos entender é que um lado e Ray fica cheio. Então vamos dizer que temos em um raio bem aqui e uma vez que ele fica cheio de números ou pedaço de dados. Então nós temos, tipo, um três aqui um dois, talvez um 1 1007 você sabe, não importa uma vez que está cheio. Assim que o nosso Ray estiver cheio, o que fazemos para acrescentar a isso. Tudo bem, então se nós, você sabe, rotular aqui em baixo certas áreas aqui. Então nós temos a coluna 01 234 A única outra maneira que nós podemos adicionar a isso é que nós temos que sobrescrever algo. E se quisermos adicionar ao fim, então chegamos a um grande problema porque não podemos adicionar ao e não há fim. Ele vai dizer, hum, por exemplo, se você tem um programa que apenas incrementa ID por um cada vez, nós queríamos adicionar ao final. Quando chegarmos a este ponto e tentarmos adicionar ao fim mais uma vez, vai ter uma segunda queda. Nós vamos ter algo como, você sabe, hum, hum, nós temos que somar a ex de cinco agora é igual a sete. Isso não vai funcionar. Isso vai acabar em uma falha, porque não há cinco aqui. Não há cinco à direita aqui, então ele vai tentar tocar dados que ele não tem a capacidade ou o conhecimento de tocar,o tocar, que vai colocar falha no programa. Vai sair do ar e nunca vai executar. Então, o que fazemos nesta situação? O que podemos fazer é aumentar dinamicamente o tamanho da matriz. Agora o problema é que, uma vez que um array é criado, o tamanho é criado. Se você se lembra, volta a ter uma memória foi criada, por exemplo, nós tínhamos um monte de segmentos e digamos que em cada um desses segmentos ele criou este array bem aqui. Mas o problema é que este é segmento já foi atribuído e depois disso foram dados adicionais . Então você não pode simplesmente aumentar o tamanho da matriz. Isso não funciona porque você estaria substituindo alguns outros talvez dados críticos do sistema aqui . E isso é um problema. Não queremos fazer isso. Então, o que você pode dio é em vez de apenas adicionar ao final, você pode fazer um novo array e copiar todas as informações lá em um novo, maior array. E então essa é a técnica comum que normalmente é usada. E assim lá. Você sabe que há um par de maneiras diferentes de fazer isso. Digamos que em vez de um cinco, array queria adicionar um ao final. Então agora o que temos que difundir é vamos nos criar em um raro bem aqui. Digamos que é em vez de cinco intolerantes, seis grandes. Então está aqui. Aqui, aqui, aqui, aqui estava o 123456 Ok, e então então nós copiamos sobre um dado. Então nós temos três e isso segurar o problema aqui é que o que nós temos para criar um novo array? Porque o que acabamos de falar, não podemos aguentar mais tempo. Então temos que criar um novo array, mas não há aumento vazio. Agora nós vamos realmente ter que entrar e pegar cada pedaço de dados e copiá-lo . E quando fizermos isso, o que vai acabar sendo é que vamos ter que fazer uma transação. Então um custo aqui é três, então um custo para obter o custo 21 para obter o custo 11 para obter o custo 10 1 para obter o sete e, em seguida, a inserção aqui. Então, por exemplo, vamos criar uma inserção. Agora ele cria ex de cinco. Dissemos que era igual a sete. E assim nós temos que sete inseridos. Mas você vai notar que em vez da inserção normal até o fim com que estamos lidando, lembre-se, de volta em tudo isso, dentro para trás deve ser tempo constante. Então o Ray dinâmico o problema é que quando tentamos inserir na parte de trás de um array que já estava preenchido, adicionamos um adicional, mas levou tempo. Por que demorou a tempo? Porque aqui em números há 12345 Então nesta situação estão no nosso em igual a cinco . Mas tivemos que tomar. Adicionamos um aos nossos fins com um R N que se tornou seis, e foram necessárias seis operações para copiar tudo. E então imagine se isto fosse uma matriz de, digamos, 100 destes aqui. Levaria 100 operações para copiar tudo. Então isso significa diretamente proporcional ao número de números que temos aqui. O quão maney temos aqui. Isso é exatamente quantos, hum, operação vai demorar. Então, em vez de nosso odor rápido primeiro, ou são tempo constante não é mais que esta inserção realmente se torna o de tempo final, e isso é um problema porque inserir em uma corrida deve ser rápido. Essa é uma de suas vantagens. No entanto, se chegarmos ao fim do tempo do que algumas de nossas outras opções começam a se tornar muito mais apetitosas, porque não temos mais inserções instantâneas. Então, o que vamos fazer? Na verdade, há uma maneira de contornar isto. Há uma maneira de você não ter que fazer essa implementação para que você não precise alterá-la até o fim. Você pode manter relativamente isso aqui, e tudo se resume a algumas médias. Então, digamos que em vez de fazê-lo da maneira ingênua, que seria inserir uma nova caixa toda vez. Então, se precisarmos de seis, levaríamos nós inseriríamos uma caixa aqui no final, que fizemos aqui mesmo. E se precisássemos de um, criamos um novo array aqui embaixo, e então ele tem você sabe, B B 7 grande, e poderíamos continuar fazendo isso. Mas tudo o que o tempo que fazemos que se torna devido ao fim, então podemos fazer em vez enfraquecer fazer em vez disso é o dobro do tamanho da matriz agora. Então, se você tem um array que foi criado, vamos passar pelo tipo duplo de gráfico aqui. Então você tem uma matriz. Agora está preenchido com um. Agora você insere até o fim. Agora, agora nós dobramos. É muito que quatro de oito em 16 de 32 em 64 1 28 e assim por diante. Vai para cima que estamos fazendo para Exponential está aqui para fazer o X bem aqui em cima. Isso é o que estamos fazendo aqui é cada vez que os foguetes se encheram, vamos dobrar o tamanho da matriz e a maneira que a razão que isso ajuda é porque se você vai notar que há uma quantidade decrescente de tempo que temos que usar sobre o fim. Então, por exemplo, você verá que em cada um desses pontos, tem que ser O até o fim. Nós temos que você. Temos que copiar todos os dados a partir do acima. Temos que copiar os dados anteriores para o novo. Mas você também percebe algo aqui é que há uma quantidade crescente de distância entre cada um desses números. Cada vez mais, está ficando mais longo, que significa que se não precisarmos redimensioná-lo, não teremos que redimensionar aqui ou aqui. que significa que entre, por exemplo, 65 65 a 27 não temos que redimensioná-lo, que significa que todas essas operações são uma estrada para uma, porque estamos apenas fazendo inserções regulares naquele ponto. Então esse é o tipo de o que isso aqui representa o inferior bem aqui é o que eu estou representando aqui é que estamos pegando esse tamanho e em vez de ter cinco, estamos dobrando para 10. Então agora copiamos os dados aqui e vamos para três, 21 10 107 e no sete. E agora, em vez de ter que fazer sobre o final para as próximas quatro operações, esses anúncios serão todos oh, para o único porque nós não temos que redimensioná-lo enfraquecer. Basta inseri-lo como uma matriz normal. E assim este foi o “O” até o fim. E então se o trouxermos de volta, se olharmos para aqui, podemos pensar sobre isso para que este tenha sido o até o fim para inserir, e então teve que dobrar. Então este teria saído até o fim. Mas então temos um lugar de 02 com um oh para o um e então teríamos um duplo. Este foi cinco. Deve ser quatro. Se estamos fazendo isso dessa maneira, vamos ver que ele começa a ficar cada vez mais quantidade de O para os uns. E por que isso é tão importante? Porque isso significa que em vez de toda a nossa operação ser O até o fim, podemos realmente criar uma espécie de média. Então vamos dar uma olhada nessa média. Então nós entramos aqui e vamos passar por alguma criação simulada aqui. Então nós temos uma inserção 23456 Eu só vou descer a lista aqui. Vamos criar uma pequena mesa aqui. De todas as inserções possíveis que poderíamos fazer até certo ponto e você começará a ver o padrão aqui, você começará a entender por que isso é realmente bom para fazê-lo para dobrar a matriz dinâmica , e Vamos subir para 25 aqui mesmo. Nós estamos realmente vamos subir para 32 porque esse é um dos nossos bits são um dos nossos pontos duplos . Certo, então quando inserirmos 12 aqui, será uma operação constante. Temos uma matriz. Vamos criar a nossa direita e vai ser tamanho F. Então isso vai ser constante vai ser um aqui mesmo. Agora, uma vez que você chegar a este ponto, vai correr para o espaço, então nós tivemos que dobrá-lo. Então agora é muito grande. Então esta era uma ode à operação, que, na verdade, era um não a uma operação porque só tínhamos uma parte de dados que tínhamos que transferir . Mas tecnicamente é uma ode até o fim, por isso vamos sentar-nos sem ti lá dentro. Agora temos um espaço aberto aqui, então se você pensar sobre isso, eu vou desenhar o quadro aqui um pouco no início para ilustrar o que estamos fazendo aqui. Então, tínhamos um lugar. O problema era que queríamos inserir um 2º 1. Não há mais vagas. Então o que fizemos foi duplicar copiar os dados. Então agora há pontos suficientes. Agora queremos ir para o três. O problema é que, quando chegarmos a três, temos de o duplicar de novo, porque não há vagas disponíveis. Agora vamos dobrar de novo, e vamos encher essa insulina vai ser outro O até o fim. Mas agora o número quatro para preencher o quarto lugar, está aberto, então podemos ir para o que não temos que fazer dobrando este lugar aqui. A taxa spot aqui está aberta, e então continuamos, e notamos que cinco precisarão ser dobrados porque corremos nas vagas para podermos ir em frente e duplicar de novo. Copie todos os nossos dados para o novo array. E então agora vamos em frente e remover a ambiguidade ali mesmo. E agora temos todos os nossos dados. Os nossos dados neste momento estão a preencher este e este e este este este um e cinco, e agora, uma vez que vamos lutar. Então as cinco operações que um nos levou foram até o fim, e agora, quando chegarmos ao seis aqui, podemos preenchê-lo imediatamente. Então ir para o 17 é exatamente o mesmo caminho sobre o um e são lugar tem oito lugares. Então é o até o fim bem aqui ou o meu mal, o meu mal. Ainda é mais um com um porque temos um espaço aberto aqui com outro O para um. Então agora temos a totalidade do array preenchido mais uma vez, este é 12 12345678 Ele está preenchido, e agora temos que dobrar mais uma vez, então nós dobrá-lo novamente. E agora o que temos que fazer é criar um não para a operação em operação, e eu vou continuar desenhando agora porque agora você pode ver um padrão. Aqui está, então nós dobramos. E agora é bom até 16 vagas, então poderíamos sair com um. Oh, aquele com um. Podemos continuar até chegarmos à próxima parte dupla. E agora estamos em 16. Então agora é ir para o fim, e então vamos continuar tempo constante, tempo constante, tempo constante, tempo constante, tempo constante, tempo constante, tempo constante. Não vou mais escrever o Theo. Eu só vou corrigir os tempos constantes constantes, constantes, constantes, constantes, constantes. E, em seguida, até se fizemos 32 constante 33 dentro e assim por diante. E por que isso é importante? Bem, você vai notar no início, que tivemos um monte de operações de O para o N. Mas depois disso estava ficando cada vez menos assim até o fim. E cada vez mais cabine de log ou cada vez mais, mawr tempo constante. Nós, por exemplo, aqui temos três constantes de um tempo linear. É assim que se chama. Vamos começar a chamá-lo linear um tempo linear, em seguida, um monte de tempos constantes, um tempo mais mabrio do que uma quantidade extraordinária de tempos constantes do que uma vez. E o que acontece é que, ao longo do tempo, esses tempos constantes ou não constantes, esses tempos lineares vão ficar em desvantagem numérica. Eles vão ser superados. E isso é porque o fato de que estamos dobrando cada vez, então quando dobramos, estamos criando um log de ocorrências rítmicas de O até o fim. Então estamos criando uma ocorrência como esta que você pode ver essa leitura. No início, temos um monte de gente livre do começo. Temos um monte de diferentes. Ele vai de, tipo, tipo, zero dedo do pé. 1234 chamadas de logado. Mas depois disso, cinco chamadas estão aqui. Seis chamadas para vir para cá. Sete chamadas está completamente fora do ecrã. E assim fica cada vez menos ao longo do tempo. E tudo isso se resume a um tipo importante de, um, uma realização importante. E isso é deixar-me ir em frente e fazer alguma coisa aqui. E esse é o fato de que se dobrarmos cada vez que dobrarmos, o que estamos realmente fazendo é criar log de no tempo, um log de uma média de quatro nossas extremidades, que significa que esse tipo de entra em algum pouco de um truque O Matthew. Então, eu só vou dizer isso para você e apenas meio que entender. Talvez anexemos um documento que entenda um pouco mais. Mas o que acontece aqui é aquele log de fim, porque em está associado a isso, porque nossas chamadas, porque nossas chamadas para porque nossas chamadas para terminar começam a entrar em um log de in. Podemos reduzir isso a tempos constantes. A média torna-se tempo constante, que significa que o pior cenário geral torna-se, para todos os fins intensos, tempo constante. Agora é um toque acima dotempo verdadeiro e constante, tempo verdadeiro e constante, mas para fins relacionais compará-lo a outras coisas que podemos entender e enfraquecer. E acredita-se muito amplamente que esta inserção se torna tempo constante. E assim, através de tudo isso, você só pode pensar nisso. Há algumas maneiras diferentes de implementar um array dinâmico, mas há uma maneira muito eficiente de fazê-lo. E vocês notarão que muita ciência da computação tem coisas assim onde há uma maneira muito eficiente de implementar esses projetos e esses padrões. E há uma maneira muito ineficiente. E assim, nesta situação, dobrar em cada vez é muito suficiente no fato de que ele sai para o tempo constante todo o caminho no final por causa dessa mudança rítmica log. E é por isso que é compreensivo. A matemática é uma espécie de importante, porque através disso, Matthew poderia entender que quando você cria essa média longa de cadeias ao longo do tempo que sua operação realmente meio que média para o tempo constante, e que seria a maneira mais eficiente de fazer isso. Então isso é arrays dinâmicos e um pouco da teoria por trás deles. Um pouco de matemática por trás deles e apenas uma boa introdução ao trabalho dinâmico e como você poderia criar uma taxa dinâmica, que é apenas criar uma nova e, em seguida, duplicar o tamanho e, em seguida, preencher todos os informações em cada vez que dobra. Então esses são dinâmicos elevam sua realmente, muito legal porque eles removem parte dessa limitação do tamanho do espaço ter que ser constante , e eles permitem que você tenha um monte de flexibilidade ah em sua programação. 15. Revisão de dois a 7: Então nós cobrimos muito sobre um aumento em apenas estas últimas palestras. E então eu meio que queria apenas dar um passo para trás e apenas rever tudo de novo muito rapidamente e meio que amarrar tudo isso juntos em 11 vídeo. Então, nós vamos estar indo para cima rapidamente. O que aprendemos nas lições anteriores tipo de re, você sabe, re ilustrando o que aprendemos e, em seguida, apenas amarrando todos esses aspectos juntos para que possamos realmente ter uma boa compreensão de um aumento, como eles funcionam o que seus tempos de execução, etcetera. Então a primeira coisa que precisamos fazer é lembrar como a corrida funciona. Então raise são apenas um ponto de dados dentro de nosso disco rígido ou nossa RAM ou algum outro ponto do nosso computador. E esses dados são trazidos para um segmento em sempre que criamos um array estavam apontando para o pedaço de dados como um todo, e estamos dando um nome a ele. Então, por exemplo, ele tem um endereço físico, um endereço de computador, mas podemos estar apenas declarando-o como uma variável como, digamos, X é igual a uma matriz do que é um comprimento de classificação cinco. E assim, nesta situação, podemos estar declarando nossa matriz de do nome de X enquanto na conversa de computador. É encontrar um endereço de lugar específico e memória, e então uma vez que chamarmos esse endereço, ele vai nos trazer para o próprio array. E a matriz tem esses muitos nomes, que eu gosto de chamá-los, que são apenas o tipo de parte da matriz que queremos contatar. E então nós podemos entrar em contato com todos esses e eles geralmente são como eles podem até mesmo ser colocados no final bem aqui. Então isso pode ser zero, etc. No entanto, o computador faz esse tipo de fora do escopo deste curso, Mas o computador fará sua coisa para que possamos acessar cada um desses pontos instantaneamente apenas dando-lhe seu nome completo. E depois são muitos nomes. Então, nesta situação, se quiséssemos, se preenchêssemos a taxa de dados e sem pecado aqui, então, por exemplo, nós temos, você sabe, apenas alguns números aqui, e queríamos pegar um ponto específico ou um lugar específico aqui. Tudo o que temos que fazer é apenas dar-lhe o nome e, em seguida, o mini-nome nesta situação, também. E depois recuperaremos os resultados. Então, por exemplo, isso seria configurá-lo para 10 e, em seguida, para obtê-lo de volta, nós diríamos que nós apenas chamá-lo e ele iria chamá-lo de volta e ele iria nos dar 10 porque iria. Este é o seu nome principal. Está pegando seu nome crina. Ele é usado em seus muitos nomes, e então ele recebe nosso pedaço de dados assim e assim um aumento também pode ter propriedades adicionais , o array nesta situação. O que estamos fazendo é, na verdade, estamos indo de um para o outro, e estamos chamando arbitrariamente dizendo que deve ser 10 3 deve ser 44. No entanto, se você quiser adicionar um pouco mais de um estilo uma estrutura para isso, podemos começar a adicionar para trás ou adicionar para a frente e apenas por si só. Nessa situação, começamos a entrar no problema em que, se quisermos adicionar à frente, teremos que pegar todos os nossos dados e desligá-los por um, porque não há nenhuma maneira associarmos. Mas esta é a frente. Este é o fim. Não podemos ir para um negativo. Negativo é uma falha da SEC que não existe no nosso programa. Então teríamos que mudar tudo para baixo. E isso traz um problema para que possamos consertar isso. O problema é que podemos começar a criar uma espécie de aspecto mais honore. Então, se quisermos torná-lo circular, lembre-se, isso foi ensinado a Se você quiser torná-lo circular, nós apenas adicionamos um ponteiro frontal e um ponteiro traseiro nele e isso irá emular uma matriz circular . Ele irá emular este tipo de coisa onde o array é realmente circular em que ele vai se você quiser adicionar à frente tudo que você tem a fazer é mover um para a esquerda, indo para a parte de trás. Tudo o que você tem que fazer é mover um, ou nesta situação, sentido anti-horário ou no sentido horário. Se você quiser adicionar para a parte de trás e assim podemos, em seguida, mover esses ponteiros o que está em tudo podemos, em seguida, mover esses ponteiros de uma área para a próxima. Se assim escolhermos assim, uma vez que adicionamos um elemento aqui. Podemos associar a parte de trás aqui. Podemos associar a parte de trás para aqui. E então podemos adicionar para trás em tempo instantâneo e adicionar para a frente e tempo instantâneo também . Mas então nos deparamos com o caso em que, por exemplo, são matriz pode ficar sem espaço. Então, por exemplo, podemos ter esse direito, e pode ficar muito grande. E então, se nosso raio acabar ficando muito grande, o que podemos realmente dilatar é que podemos ir em frente quando podemos dobrar seu tamanho. Então isso o torna um array dinâmico, enfraquecer realmente, qualquer maneira de torná-lo maior? Poderíamos fazê-lo ir, por exemplo , adicionar um ao fim. Mas aprendemos que isso não o torna eficiente. Isso faz com que seja realmente ineficiente. Então, se tivéssemos uma matriz de para, assim poderíamos dobrar o tamanho uma vez que alcançamos um ponto inválido e poderíamos torná-lo um array de quatro como este e continuaremos dobrando para cima e para cima, e veremos que ele vai ficar maior lentamente e maior e maior para caber nossos dados ao longo tempo, e isso nos permitirá criar uma tabela ou um array, que ao longo do tempo adiciona uma inserção do final de O de um por média. Então nós vamos ter um par de instâncias essas instâncias bem aqui onde ele vai ser em que vai ser um tempo linear em cada uma dessas instâncias, e isso apenas chega ao fato de que nós temos que copiar todo o nosso conteúdo de cada vez re dimensioná-lo. Temos que copiar nosso conteúdo do A mais antigo para o novo raio e depois adicionar nosso número adicional . E então toda vez que temos que expandir isso, nós vamos acabar tendo que copiar tudo, que vai ser em, hum, procedimento. Então vai ser um procedimento em cada vez que temos que fazer isso. Mas se dobrarmos cada vez que este procedimento se torna cada vez menos comum até que ele sobe em um ponto infinito no qual basicamente se torna, nós vamos ter que redimensioná-lo. Nós vamos ter que usar quase zero vezes então pensando se nós formos para o infinito em algum momento, haverá um momento em que nós estamos usando, você sabe, você sabe, um 1.000.000.000 de operações constantes e, em seguida, uma em operação. E se você pegar um e dividi-lo por um 1.000.000.000 você obtém um número tão pequeno que poderia muito bem ser zero. E por causa disso, calcula que as extremidades à medida que vão para o infinito, as extremidades aqui à medida que vão para o infinito, na verdade acabam se tornando zero, e elas se tornam basicamente inúteis. Não olhamos mais para eles. Então nós apenas olhamos para aquele tipo de um fora, e esse é o uso constante do tempo constante. Então, se dobrarmos nosso aumento A cada vez que eles ficam sem dados, podemos obter uma inserção de tempo constante na parte de trás, e isso torna nosso programa muito mais eficiente. Então isso é apenas uma espécie de resumo do que temos vindo a cobrir nestas últimas palestras sobre um aumento, como você pode torná-los circulares, como você pode torná-los dinâmicos, e em algumas das vezes associar-se a cada desses raios. Então isso será testando esse tipo de dados no próximo tipo de lição, onde nós estamos realmente fazendo um pequeno teste aqui apenas tipo de certificar-se de que tudo isso é cimentado em suas mentes e você entende pelo menos o básico. Você não tem que entender tudo isso 100%. Muitos cientistas da computação não entendem tudo isso 100%. Só queremos ter uma boa compreensão disso para que se esquecermos alguma coisa, possamos ir procurá-la. E temos uma base boa o suficiente para entender o que não entendemos. Se isso faz sentido, entendemos a parte que estamos tendo problemas para olhar para cima. E se entendermos um pouquinho, se tivermos uma base que possamos continuar nosso aprendizado. Estou animado que chegamos tão longe que nós começamos a aprender sua primeira estrutura de dados em um aumento, e eu mal posso esperar para vê-lo na próxima unidade onde vamos discutir listas vinculadas listas vinculadas 16. Exemplos do mundo do real 2-8: Agora que temos uma boa compreensão de um raise e como eles teoricamente funcionam, vamos olhar para alguns exemplos do mundo real de onde podemos ter interagido com uma matriz sem sequer sabê-lo. O exemplo mais comum, ou algo que é usado muito comumente é em nossos smartphones. Ah, muitas vezes as listas aqui e o tipo de layout APP são todos baseados em matriz. Então o que eles fazem é uma tempestade em um aumento. E sempre que você clicar sobre isso, ele chama o comando qualquer array que você tem. Então, por exemplo, vamos ter esta grade aqui à direita. Você pode ver que temos 12345678 todo o caminho para baixo. E esta é a matriz. Os números em cada um deles são armazenados em um desses arrays. Então, o que temos de clicar num botão? Então, por exemplo, se clicarmos na taxa do Facebook aqui, que alinha com o número 10, ele vai para a matriz e procurar o comando em 10 . Uma vez que ele vê que o comando em 10 está aberto no Facebook, ele vai abrir o Facebook, e nós vamos fazer o mesmo com se tivéssemos 15. Vai voltar para cima. Tínhamos 19. Vai para o local, etc., etc. Então o que ele faz é quando ele constrói, ele cria um array com um monte de referências do que ele deve abrir. E esses raios também têm outras informações. Como o quê? O ícone deve ser as cores. Você sabe, um, e outro tipo de informação que funcionaria com cada um desses, o nome do APP, coisas assim. E então sempre que clicamos nele, ele entra e encontra a peça real do software para abrir sempre que clicamos nele. E aqui também temos uma lista. Muitas vezes estes são criados com um aumento, então você terá a matriz de contas, que terá um monte de coisas diferentes aqui. E então você terá a matriz geral que terá um monte de propriedades diferentes aqui também. A razão de matrizes funcionar. O melhor aqui é por causa de como eles são instantâneos. Então, quando clicarmos em 18, não queremos nenhum atraso entre isso. E se clicarmos em um, aprenderemos sobre outra estrutura de dados na próxima lição, que leva mais tempo quanto mais você for. Então, por exemplo, se houvesse 45 APS, não queremos que o número 45 demore mais que o número um. Queremos todos no instante. O mesmo com aqui quando clicamos em algo, queríamos ser exatamente ao mesmo tempo. E, como estivemos falando sobre um aumento, temos essa habilidade. Você pode chamar a matriz de dois ou quatro ou 10 e obter esse elemento instantaneamente, e é por isso que eles são tão importantes. E eles são muito importantes para usar. Se você quiser ver o que algumas das chamadas para um aumento podem ser em diferentes idiomas, há realmente um artigo realmente necessário na Wikipédia sobre ele. Mas há uma tabela incrível aqui e você pode ver todas essas línguas, e cada uma delas tem uma matriz de alguma forma, forma ou forma. Aqui está uma espécie de os grandes jogadores na programação bem aqui você tem você sabe, seu rubi, seu python, seu javascript, Java C C plus então realmente, os grandes jogadores no mercado e eles são todos chamados com o nome da matriz e no número de índice Então, por exemplo, isso pode ser matriz AP, e então este é o índice 10. Então isso seria uma chamada de APP Array 10 e chamaria tudo dentro disso, então isso é apenas uma maneira interessante de olhar para ele. Você pode ver que mesmo que todas essas línguas sejam tão diferentes umas das outras, se todos eles usam um aumento de alguma forma, ou alguma forma outro uso comum de um levanta com bancos de dados com bancos de dados realmente, realmente grandes, Às vezes, eles não são armazenados em um aumento, eles são armazenados em maneiras ligeiramente diferentes, como árvores ou coisas assim. Só porque uma vez que você tem uma matriz tão grande, você gosta de bilhões, ele fica um pouco tedioso e um monte de ram tem que ser armazenado se você quiser armazenar todos aqueles instantâneos. Então o que eles fazem é criar coisas que são quase instantâneas, mas que vão levar um pouco mais de tempo. Mas isso é para explicações posteriores. Isto, porém, é o que em um raio pode parecer. Se você tem um menor ou mesmo apenas tabelas dentro de um banco de dados, eles estarão usando um aumento. Então, por exemplo, se quiséssemos classificar por utensílios de cozinha, poderíamos pegar todos aqueles que igualam utensílios de cozinha e depois ligar de volta. Will poderia fazer talvez uma lista de todos esses números, e então passamos para uma função, e então ele só chama todos esses números. Então, por exemplo, para estaria em nossa lista e, em seguida, 13 e 14 estarão em nossa lista. E quando ligamos para 13 14 nós poderíamos construir outra lista com apenas utensílios de cozinha para que pudéssemos filtrar esta lista. Arrays também são comumente usados na Web. Este é realmente um dos meus sites que eu tenho, e isso está usando WordPress. Mas com a parte legal sobre isso é que eu passei pelo código e cada parte deles está realmente usando uma matriz de alguma forma ou forma basicamente o que ele faz que chama todos os artigos como uma matriz. E isso os coloca aqui, assim como nosso exemplo de aplicativo anteriormente. E sempre que você clica em um desses, ele chama as funções, os nomes que tudo o que vem com ele, e meio que passa por isso. Então estas páginas web Facebook, Twitter eles todos usam um aumento de alguma forma ou forma para mostrar os dados. E então também, eu queria mostrar alguns dos códigos de back-end aqui. Então isso é na verdade algum código do site, e esse material é muito, muito complexo. site, e esse material é muito, Eu nem entendo isso tão bem. Leva um pouco de tempo para entrar aqui e começar a entender as coisas. Mas uma das partes legais é que você pode ver bem aqui. Este é um formulário de comentário sobre WordPress. Ele constrói na matriz. Ele cria uma matriz de todas as informações que ele coleta a partir do comentário. E é usado bem aqui. Você pode vê-lo. A matriz é declarada aqui. E, na verdade, há Honore aqui em baixo e matriz aqui em cima. Há raios de em um aumento em uma corrida. Como eu disse, muito, muito complexo. Este código é uma espécie de bobagem, a menos que você realmente olhe através dele e tipo de passar horas, horas e horas e horas analisando-o . Mas eu só queria mostrar a vocês que uma matriz está presente em tudo isso também. Então, em qualquer lugar que você olhar que tem a ver com a codificação de um aumento nosso lá presente e eles estão sendo usados um aumento são quase o mais. Faça isso se não for a estrutura de dados mais usada lá fora. Então, compreendê-los muito bem e, em seguida, entender alguns de seus benefícios como eles são rápido tempo de execução, tipo de mostrar a você por que eles são usados no mundo real com tanta frequência. 17. 3-1 nos nós: Então, antes de entrarmos em listas vinculadas, precisamos entender o que são vinculados lista composta do que eles são feitos? E então nós vamos estar falando é sobre o que eles foram tirados. E há chamados de nós. Então, o que é exatamente um bilhete? Uma nota é realmente apenas um objeto de localização. É um objeto que faz referência a outros objetos, e isso pode ser um pouco de uma definição confusa. Então vamos em frente e tipo de escrever isso. Vamos ilustrar o que é uma nota. Então, estas caixas aqui em baixo, estas duas caixas no fundo, esta à esquerda, uma à direita, seriam contadas os nossos nós. E aqui em cima temos memória. Então eles podem ser uma matriz. Pode ser o Ram. Pode ser qualquer tipo de memória aqui em cima, mas o que eu sei é que tem um monte de propriedades diferentes sobre isso. Então, por exemplo, poderia ter, hum, vamos com, como normalmente tem uma propriedade de dados. Então essa é a propriedade importante. Por exemplo, ele poderia ter um pedaço de dados como este, e talvez este tenha um pedaço de dados como este, mas eles geralmente não estão dentro da nota porque isso é apenas suposto ser como um objeto de localização. Então o que o nó realmente faz é que ele tem um ponto para os dados no topo, e então ele tem outro tipo de características da parte inferior, que nós vamos passar por aqui em um segundo. E esta parte superior dos dados, na verdade contém o endereço para um ponto de memória. Então, por exemplo, digamos em nossa memória, aqui temos, hum nós temos essas áreas e isso não é um array estes ou eles apenas, você sabe, há memória adicionalmente aqui e aqui e estes ar apenas pontos reais na memória. Então, como este é F zero. Este é o Fum. Este é F dois, e este é F três. E então o quê? Ele está realmente armazenando aqui, é armazenar a localização dos dados para que ele não precisa estar em ordem. Por exemplo, este poderia armazenar zero x f três. Então ele tem um ponteiro que basicamente aponta para este pedaço de dados. Bem, este aqui poderia talvez armazenar zero x f um e então ele vai ter isso significa que Pointer está bem aqui. E assim agora sempre que queremos nossos dados sempre que um dos nossos dados do nosso nó. Então, se quisermos os dados dos nós, o que podemos fazer é chamar o nó, e então qualquer que seja sua parte de dados é chamada e ele vai nos dar ele vai e fazer o trabalho para nós. Ele vai encontrá-lo e depois devolvê-lo para nós. E então a parte importante sobre nós e a razão pela qual eles são usados com tanta frequência é porque eles têm outra característica especial. E eu vou usar este fundo galáxia Penda mostrar esta característica, e esse é o fato de que eles têm a habilidade de se conectar um ao outro. Então, por exemplo, poderíamos dizer que... Bem, digamos que temos um estreito vindo aqui e temos uma flecha saindo aqui. Poderíamos ter aqui algo como um próximo, então poderíamos ter uma próxima parte de cada um desses nós. Poderíamos ter uma parte anterior para um desses nós e estes podem realmente ser qualquer coisa. Isto pode ser a frente. Nós saímos da frente em um desses lados que sempre apontará para a frente. Podemos sempre apontar para a parte de trás. Poderíamos ter sempre apontar para locais específicos, mas uma técnica comum é o tê-lo anterior e frontal. E então vamos em frente e apenas para a direita que um pouco claro anterior, próximo. E assim cada um destes tem anterior e seguinte. E então o que acontece é que nós contamos. Onde o próximo deve ir quando podemos apontar para outro nó? E nessa situação, poderíamos apontar para uma nota anterior, e esse nó anterior pode apontar nessa direção para trás como então deixe-me. Foi um ar ruim. Deixe-me ler toda essa flecha para que ela possa apontar para trás assim e então esta pode apontar para frente, que está bem ali, e pode ter uma flecha que aponta para trás em direção a ela, assim assim. E então o que isso faz é criar uma lista vinculada, e isso é o que vamos discutir é que estamos usando esses caras esses nós aqui para criar listas vinculadas, e então vamos repassar exatamente por que listas vinculadas são importantes como eles nos ajudam , e como eles se comparam a outras coisas, como a matriz que já falamos. Então, neste tipo de palestra do tipo de unidade iria estar discutindo listas vinculadas. 18. Lista de links 3-2: Então, agora que temos uma boa idéia de como os nós funcionam, vamos investigar um pouco mais e ficar atrás da intuição de listas vinculadas. Então, que lista ligada é o que eu descrevi na última palestra onde você tem um monte desses narizinhos. Então, por exemplo, poderíamos ter um monte desses. Quero dizer, essas coisas podem ser infinitas, então poderíamos ter uma nota aqui. Uma nota aqui, uma nota aqui, uma nota aqui, nota aqui, e novo faz isso por diante e assim por diante. E a abreviação para tipo de desenho isto está dentro vai ser o ponto de dados. E se apontar para outro lugar, é só desenhar uma flecha. Então o que temos aqui é que temos um monte de diferentes locais aleatórios na memória que estão todos ligados entre si por estes ponteiros. Então estamos em uma matriz. Tínhamos tudo no espaço linear. Honore, por exemplo, tínhamos em um array. Tínhamos tudo dentro, como um espaço linear onde era um após o outro. Então isso seria como 34 10 12 e 11 bem aqui, onde tivemos um depois do próximo em, em um desses tipos de em uma lista vinculada, o que você vai ter é que isso vai estar em toda a memória. Então este pode estar em algum lugar. Como, por exemplo, este quatro pode ser, você sabe, aqui em baixo enquanto este 10 está em algum outro pedaço de memória e este 12 não é algum outro pedaço de memória e assim por diante e assim por diante. Então, o que uma lista vinculada vive você dio é que permite que você conecte dados em todo o lugar juntos. E então o que isso lhe dá a capacidade de dialogar é que ele lhe dá a habilidade. Vamos nos livrar disso. Ele lhe dá a capacidade de realmente adicionar continuamente na lista de comprimento sem ter que fazer coisas como expansão ou dobrá-la. E se você pensar sobre isso quando estamos falando sobre o array, como ele tinha que dobrar cada vez para ser eficiente quando ele ficou maior, muitas vezes nós poderíamos encontrar um caso onde apenas metade do array é preenchido, o que significa que nós temos todos os seus outro quarto na outra metade. Isso não está preenchido, o que é ineficiente. Estamos desperdiçando espaço. Há apenas ser Ele está esperando para ser alocado, mas não é alocado. Então lista ligada realmente nos permite sempre e constantemente ter, um a memória que é necessária para manter nossa lista e não mais e não menos. Então, se precisarmos adicionar um número a isso, podemos adicioná-lo ao fim. Então, por exemplo, se quiséssemos adicionar ah, quatro a isso, poderíamos ir. E então nós apenas vamos para o final e nós adicionamos antes para a lista bem aqui e o que eu estou falando aqui são listas ligadas Singley. E o que isso significa é que você tem um ponto de partida, certo? Assim E assim isso é marcado como iniciar a nota inicial. Então, quando você ligar para começar, você vai para cá. E o que vai dizer é que você vai partir daqui e você vai basicamente apenas a única maneira que você pode atravessar é ir daqui para aqui, aqui para aqui, aqui para aqui, aqui para aqui e apenas seguindo as setas uma após a outra, todo o caminho até você chegar ao último e, em seguida, a maneira que você sabe que você está no final é porque em vez de este apontar para outro nó, então nesta situação, como por exemplo, pode apontar para, pode apontar para outro nó aqui. Digamos que este é como um cinco, mas se estamos no final de uma lista, vai apontar para algo chamado Não. E o que não significa é que não é nada. Está apontando para nada. Não há memória alocada. Na verdade, não tem um local na memória. Está apontando para nada. E uma vez que entendemos isso, estamos em nada. Então, quando inserimos algo, nós apenas substituímos esse nada pelo nosso novo nó. Então criamos esta pequena nota aqui. É como, por exemplo, deixe-me mostrar como podemos fazer isso. Criamos um novo nó, um novo conhecido aqui chamado 15 e queremos anexá-lo a esta lista vinculada. E então, neste momento, este está apontando para Não. E então o que queremos fazer é vencer. Anexe isto a ele. Então vamos para este começo. Vamos para o começo. Eu estou indo para baixo, estão ligados lista. Tem alguma coisa. Tem alguma coisa. Tem alguma coisa. Tem alguma coisa. Oh, é que sabe. Então vamos fazer, vamos mudar isso. Não, vamos selecionar isto. Vamos tirar isso daqui para fazer com que seja uma espécie de Nós vamos pegar isso. Não, nós vamos movê-lo para fora daqui, e nós realmente vamos pegar o novo nó aqui, e nós vamos soltá-lo e este novo nó por padrão. Quando criamos o nó, o próximo local foi definido para saber. Então, por padrão, quando este aviso criou o próximo, mas disse para saber e você vai ver que isso ajuda porque agora, quando nós realmente selecionar isso e agarrá-lo e movê-lo aqui, você vai notar que o fim novamente aponta para saber. E este foi agora re alocado para apontar para o novo nó. E o ciclo continua. Se quisermos inserir outro, podemos ir em frente e 13 aqui, e criamos isso. Ele automaticamente coloca para saber que não está em nossa lista em, você sabe, ainda. Ainda está sendo criado. Agora queremos adicioná-lo à lista. Então, quando vamos para o início, descemos, descemos, descemos Agora este não é um não. Então, como OK, há outro. Aqui vamos nós para 15. Tipo, “Oh, não há aqui. O que significa que agora vamos fazer 15 em vez de apontar para saber que vamos mover o ponteiro. Então vamos excluir o não aqui, e vamos mover seu ponteiro 2.2, nosso novo nó. Então, tecnicamente, faria isso porque o nó não se moveria aqui. Estávamos apenas dizendo para apontar para este novo pedido que nós criamos este novo ativo aqui , este novo pedaço de dados que nós criamos e, em seguida, desde que nós já criamos para já ter um nulo do fim uma vez que ele vai para ouvir, ele vai se mover para o knoll. E agora, se quisermos responder a outra coisa, ele vai passar direto para este ponto e nós podemos começar, você sabe, ter um bom tipo de gráfico indo. Agora. Então o que acontece se quisermos, Por exemplo, um, excluir algo deste em uma matriz quando excluímos algo dele. Tudo o que tínhamos que fazer era, por exemplo, ter uma matriz bem aqui. Tudo o que temos que fazer é chamar o local que queremos apagar. Então, no 321012, poderíamos apenas chamar X de dois igual a não ou algum tipo de algoritmo de exclusão entra em jogo. E eu era tudo o que faz é dizer, Oh, Oh, sair para não é igual a nada mais feito. Nada para se preocupar se quiséssemos liderar o 1º 11 Fácil feito. Nada para se preocupar com a lista de links. No entanto, você percebe que existem dependências entre aspas se você excluir se apenas excluirmos . Se dissemos que queríamos apagar 10 era um delete 10 aqui. O que acontece? Como é suposto chegarmos ao resto da nossa lista para já não apontar para nada para apenas automaticamente foi predefinido para apontar para saber. Então ele aponta para saber agora porque 10 está lá, que significa que este não é o fim, e nós perdemos o resto da nossa lista aqui. Então nós realmente temos que fazer um pouco de um tipo complexo de operação para excluir deixe-me apenas trazer isso de volta. Então excluir em vez disso o que podemos dio. Digamos que temos um nó aqui. Uma nota aqui e uma nota no meio. Temos o Singley apontou ponteiros simples de ponteiros. Então é a lista da liga Singley aqui. E se quisermos excluir isso dará todos esses valores para que possamos chamá-los por alguma coisa. Se quiséssemos apagar 10 aqui. O que precisamos fazer é, antes de deletar isso, precisamos dizer Ei, três agora vai apontar para gostar, então precisamos ir para três. Vamos apagar o próximo. Então vamos para três e dizemos: “ Ei, Ei, você precisa de 2,22 e então, uma vez que essa nova alocação é criada, essa realmente vai cair naturalmente.” Agora é um mau treino. Deixe isso aqui porque isso ainda é tecnicamente um som. Então, por exemplo, disto é um começo, este gráfico aqui ainda é tecnicamente sólido. Ele vai ir 3 para 2 e depois aqui aponta para saber. E então tudo isso ainda funciona ainda é tecnicamente correto. No entanto, o que temos é que desperdiçamos espaço aqui. Na verdade, não deletamos o não. Então nós podemos realmente, antes de fazer isso, nós podemos realmente salvar isso para algum tipo de variável como antes. Como poderíamos dizer, você sabe, um, ter usado o Excel. A corrida vai w igual a esta nota de 10. E então uma vez que nós estamos fazendo essa coisa que podemos dizer, você sabe, nós podemos chamar deletar sobre ele e nós estamos realmente removê-lo da memória para que nós não temos esta coisa sentado aqui mais. Mas o que eu queria mostrar é que tudo o que temos que fazer para excluí-lo é em vez de excluir o próprio ativo, tudo o que temos que fazer é redesenhar a seta. E, na verdade , tecnicamente, este ainda estaria apontando para lá. Então temos que fazer é redesenhar a nota assim e então este está tecnicamente fora da lista. Não há como voltar aos 10. Não há maneira de ir acidentalmente para 10. É apenas arrepiante lá, e sempre pode estar lá, e a nossa lista ainda seria boa. No entanto, a maneira eficiente seria excluir isso para que nossa lista não esteja armazenando dados extras que não precisa armazenar. E então nós temos mais um caso para cobrir de como a lista ligada funciona, e isso vai ser sobre como exatamente um pode exatamente como se pode inserir exatamente no meio de um raio. Então, por exemplo, o que fazemos aqui é, digamos, estamos no meio de uma lista vinculada. Então, se você quiser inserir em um array, dizer sua taxa assim em um raio aqui, o quê? E nós temos um dois aqui temos um sete aqui. Nós temos um quatro aqui, e você sabe, nós temos 0123 e se nós quisermos inserir direito nesta parte aqui, tudo o que nós temos que fazer é ex de dois igual a sete e você sabe, ele vai para sete realmente fácil de fazer. Se você quiser inserir em qualquer outro lugar. que você realmente tem que fazer é apenas sobrescrever algo. Então, se quisermos fazer isso igual a zero, podemos ir em frente. Ele só vai sobrescrever isso e torná-lo igual a zero. Sem riel, Outras coisas adicionais necessárias. No entanto, um ray ou listas vinculadas não são tão fáceis com uma lista vinculada. O que temos de difundir é que temos de o fazer. Nós realmente temos que tipo de realocar ou re pontos e coisas. Assim como na elite, tínhamos uma caixa de três. Ele se move para 10. E então vamos dizer que este se move para 25 agora temos uma caixa aqui nós temos uma caixa que nós criamos um novo nó que nós criamos que talvez 18 e que aponta para saber. Então, como fazemos isso aqui? Como colocamos isso aí? Como vamos fazer isso ir bem ali? Bem, não podemos simplesmente inserir. Não podemos chamar o segundo lugar. Diga, insira, não há nenhum Poninters vai ficar todo confuso. Então o que temos que fazer é levar este aqui. Temos que apagá-lo. Temos que dizer que agora aponta agora para baixo para 18 e, em seguida, temos que assumir este . Temos de criar um novo ponteiro que aponte até 10 e há alguns pequenos desafios com isso. Porque se você notar algo se voltarmos para onde começou se excluirmos isso primeiro, então de repente perdemos o resto da nossa lista. Não há como chegar ao resto da nossa lista aqui. Não podemos mais tocar. Então o que temos que fazer normalmente é que temos que salvar este próximo, este aqui, em uma variável. Então, Então, o que não podíamos fazer, há algumas maneiras de fazer isso. O mais eficiente seria, na verdade, definir o próximo primeiro. Então, uma vez que chegamos a uma vez que temos este ponto na memória, uma vez que atravessamos são lista ligada. E chegamos a esta nota aqui. Weaken não disse: “ Ei, Ei, queremos que 18 seja igual a isso. Não, queríamos apontar para este bilhete. Queríamos apontar para esta nota. Então nós podemos dizer que isso agora aponta para esta nota também. E agora o que podemos fazer é voltar ao início aqui. Podemos apagar isto, e agora podemos apontar isto para baixo. Agora podemos apontar isso para R 18 e agora temos uma boa inserção e não perdemos os dados no back-end. Então, listas vinculadas lá um pouco complicado lá um pouco difícil de entender. Mas eles têm alguns benefícios, e um dos maiores benefícios é o fato de que podemos continuar aumentando até o fim. E só vai criar dados. Isso é como, hum que criar dados. Isso é, você sabe, muito grande que precisamos que seja, não temos que continuar dobrando as coisas e isso nos permite uma espécie de anúncio por capricho. Poderíamos adicioná-lo ao final. Nós não temos que nos preocupar com a classificação ou a organização dele, e nós não sobrescrevemos coisas se vamos inserir nós tudo o que é próprio pedaço de dados que podemos pegar e mover em vez de ter uma matriz onde tudo é uma espécie de trancado em uma caixa que limita algumas das coisas que poderíamos fazer com ela, especialmente mais tarde. E o que também é interessante sobre essa abordagem é que uma única lista vinculada em si é, você sabe, apenas uniformemente ligada. Mas poderíamos, por exemplo, ter cachos de nariz apontando para diferentes áreas. E isso permite tantas coisas. E é aqui que entramos em árvores mais tarde, adicionando um monte de notas. Mas isso é uma espécie de o básico de que pode ser ligado lista por si mesmos. Apenas sozinho. Lista vinculada não são a coisa mais útil, mas vai ser construindo em coisas realmente úteis mais tarde. Então essa é a lista de comprimento de Singley. A próxima parte. Vamos passar a ligá-los duplamente e, em seguida, entender os tempos de execução por trás de tudo isso e como ele se compara a algo como ele array. 19. 3-3 lista de vinculados: Agora temos uma boa e intuitiva compreensão de como as listas vinculadas funcionam. Vamos para lá. execução Provavelmente disse em ciência da computação, tempos de execução são importantes porque eles nos permitem analisar essas estruturas de dados e entender seus pontos fortes e fracos. Então, vamos fazer uma atualização rápida sobre os tempos de funcionamento do nosso raio aqui. Então o que temos aqui é que temos os tempos de execução que saímos para o array e então eu vou colocar isso aqui. Isto é para a matriz. E também, quero designar isto para exclusão aleatória. Se você estiver excluindo, por exemplo, em uma matriz, um, no início, como, por exemplo, é uma matriz circular desconhecida e você excluiu o início bem aqui. Então você exclui este e você quer que tudo para mudar para trás que também será ove em apenas como o em tipo de frente. Então este pode ser dois diferentes, dependendo de como você quer olhar para ele. Mas excluir aleatório sempre vai ser sobre o único enquanto excluir. Basicamente, frente de ladrão será devida até o fim. Então eu só queria colocar essa pequena ressalva lá sozinho, esse tipo de complexidade temporal pode obter um pouco de exatamente o que você está olhando, como especificamente para que eles possam ficar um pouco confusos nesse aspecto. Mas se você realmente apenas pensar sobre eles intuitivamente pode entender. Então, por exemplo, na matriz, se estamos excluindo da taxa inicial aqui, tudo tem que mudar de volta. Então temos que nos mover em número de, hum, em número de lugares na pior das hipóteses. E vamos apenas uma espécie de intuição por trás disso. Mas podemos ver algumas dessas coisas aqui. Temos a inserção aleatória. Temos em busca na frente. Excluir pesquisa, pesquisa não classificada classificada. Então vamos passar por essas operações em uma lista vinculada. Então vamos criar um pouco de um exemplo de lista vinculada aqui. Então o que precisamos criar é criar nossos nós. Então nós temos o início da lista, que nós podemos apenas criar como, começar aqui para que pudéssemos criar, como Iniciar, e então ele aponta para o início do nosso primeiro nó. Digamos que nossa primeira nota tem um três, e então esta é uma única lista de links. Nós ainda não falamos sobre o dobro, então nós vamos apenas ir com uma lista de comprimento único. Eu dobro apenas melhora pequenas partes de coisas, pequenos cálculos, e então vamos para, tipo, tipo,digamos, 19 aqui ou algo assim, e então este é o fim. Então esse é um, então aponta para saber aqui. Ok, então nós temos são listas vinculadas assim, e vamos em frente e criar nosso 1º 1 Então aqui em cima nós tivemos inserir aleatoriamente. Então, se você quiser inserir algo e isso é aleatoriamente assim em qualquer lugar dentro da estrutura de dados , na verdade vamos fazer o mesmo. notação é a última também. Então queremos inserir aleatoriamente em uma matriz que nos levou tempo instantâneo porque estaríamos substituindo as coisas se você estivesse tentando calcular a substituição. Então talvez você possa ter algumas advertências nisso, mas se nós apenas vamos sobrescrever algo perfeitamente bom, você poderia apenas dizer ex de cinco é igual a algum número qualquer que seja, e ele irá substituí-lo em uma lista vinculada. No entanto, torna-se um problema é que você só pode entrar daqui. Você não pode simplesmente pular para qualquer uma dessas posições. Então, se eu quisesse chegar a 19 aqui, eu teria que ir desde o início acima de 123 e então chegar a ele, e eu teria que fazer isso por qualquer quantidade dentro disso. Então o que isso significa é que nossa inserção aleatória realmente se resume a em O de na notação. E isso porque nosso pior cenário é inserir aleatoriamente na parte de trás. O que significa que vai inserir 1234 estão dentro. Esta situação é quatro. Então vai levar quatro para voltar para aqui, e isso vai com qualquer lista de qualquer comprimento. Há 1000 destes e você quer inserir perto da parte de trás. Pode levar de 950 a 1000. Então isso significa que nosso pior caso cenário para inserção aleatória realmente se torna realmente O de N. E isso é só porque não há acesso instantâneo. Não há nenhuma maneira que nós sabemos como saltar entre estes mais rápido do que ir desde o início e seguida, movendo-se para baixo assim e assim o nosso próximo vai ser inserido na frente, então inserir frente e na frente, então com inserir frente e vai fazer inserir de volta também com um básico, hum, uma lista básica ligada. Vai ser o até o fim também. Ou, na verdade, a resposta para a frente será um tempo constante. Bem, no começo, a parte de trás vai ser O até o fim. E isso é porque vamos inserir a frente primeiro. Se quiséssemos inserir um novo nó, digamos que temos uma nota aqui. Uma nova nota aqui de quatro. Se quiséssemos inserir isso na frente, como exatamente faríamos isso? Bem, na verdade é bem fácil. Seja qual for a nossa frente, seja qual for o nosso ponteiro, tudo o que temos para dialogar é que temos que dizer OK, em vez de apontar para este ponto, e então tivemos que definir quatro para o nosso antigo. Então eu tive que definir quatro para a nossa antiga frente. E então o que isso faz é que ele vai realmente apenas adicioná-lo em 123 passos cada vez, não importa o que você está inserindo lá, então sempre vai ser um tempo constante e a maneira como você realmente quer fazer isso. Na verdade, há uma maneira que você deve inserir aqui porque este tipo de entra com perda memória. Se eu excluir isso e, em seguida, fazer este ponto para este como então eu perder a habilidade Eu perder esta primeira nota aqui, Eu não tenho mais permitir para agarrá-lo mais porque nós excluímos o único ponto que temos para ele. Então, se você quiser inserir na frente, o que temos que fazer é pegar nosso nó. Nós temos o primeiro disse isso para os três. E isso ainda está apontando para a frente. Então nós vamos dizer, Ei, quatro, quatro, nós vamos dizer, Ei, quatro, quatro, agora você está apontando o seu próximo em vez de Não, agora está apontando para três. Está apontando para o nosso começo. Vamos dizer que aponta para o início, e isso vai alocá-lo para o início. Então, uma vez que ele está apontado para aqui, nós vamos excluir daqui, e nós vamos fazer o ponto de partida para baixo para aqui, e então isso vai criar nossas inserções ou inserir é sempre tempo constante. Vai ser sempre aquelas três operações criar atribuído para o início um sinal começar dois novo não para nova nota. Então será sempre um tempo constante. Então esse é o tempo constante. E então temos inserção na parte de trás. Então inserir na parte de trás, no entanto, vai nos levar um pouco de trabalho porque, como eu disse, não há maneira de voltar aqui, a menos que mais tarde, eu vou para cima como você pode criar pouco dicas para ajudá-lo. Mas agora, com apenas uma lista básica ligada ao Singley, não há como chegar aqui sem passar por toda a lista. E assim isso vai ser sempre dentro. Vai estar sempre dentro, que significa que, por padrão, é o pior caso também. Então é o pior caso também será porque, como eu disse, não há maneira de saltarmos aqui. Não podemos começar do início e depois ir para o fim. Não há nada nos apontando para o fim. Não sabemos o que está aqui. Não sabemos quantos nós de ar entre isto. Tudo o que sabemos é por onde começar e como chegar ao próximo. Então vamos ter que fazer é começar a correr. Tivemos que criar um novo nó. Então, se você quiser adicionar um ao final, digamos que queremos adicionar este quatro ao final. A única maneira de fazermos isso é termos de ir. Ok. Bem, o que há no final? Desça 4 a 3. Pague um 2 a 10 este é o Não, estamos no final. Ótima. Agora, uma vez que estamos no final, temos a nota final. Então podemos contar. Ei, você vai se mudar. Você não sabe mais que vai ser definido para quatro. Assim e então, é claro, por padrão. Quando criamos isso, isso foi apontado para saber que nossa lista funciona novamente. Então, uma vez que você chegar aqui, a operação é apenas como um ou dois tipos de números de criação. Mas chegar aqui é devido até o fim. E é por isso que nossa corrida pode tempo será Odeon também. E então o próximo que queremos pegar será deletar aleatório. Então, queremos excluir aleatoriamente. E assim, com um delish nele tipo de depende de como você está excluindo e onde você deseja excluir. Então o problema é que se estamos excluindo da frente, é muito fácil. Se apagarmos da frente, tudo o que temos que fazer é dizer, começar igual à frente a seguir. Então deixe-me escrever isso porque esse tipo de entra em algum. Como se você começar a escrever essas coisas, vai ser como, hum, começar é igual a esta nota aqui. Iniciar ponto em seguida. E essa flecha seria chamada a seguir. Então o que estamos dizendo é que o início agora é igual a começar a seguir e então este apenas obter tipo de removido fora do ciclo e a seta recebe re ID associado fora daqui, e então ele vai direto de volta para aqui. Então, se apa