Timing e notação em big O

1. Vídeo de introdução: Olá a todos, bem-vindos a este curso sobre notação Big O. Esse é um ótimo tópico de ciência da computação que o ajudará a se tornar mais eficiente em seu trabalho. E também ajudará você a entender um pouco melhor a ciência da computação. Isso é ótimo para todos os tipos de profissões, incluindo programadores, bem como para qualquer pessoa na área de negócios Isso o ajudará a aumentar sua produtividade, pois você entenderá um pouco mais com o que está trabalhando, que lhe dará mais informações e ações as etapas necessárias para tornar as coisas mais eficientes. E é isso que abordaremos neste curso. Vamos abordar a notação por trás de como analisamos diferentes algoritmos e escalabilidade Queremos entender se estamos construindo um programa ou um trecho de código ou mesmo apenas uma unidade organizacional. Ele pode escalar? Se estivermos criando tarefas e procedimentos de natureza exponencial , eles nunca serão capazes de escalar E isso é o que queremos ser capazes de analisar: funciona da mesma forma se tivermos dez pessoas ou 100.000 pessoas? Pense se você deseja verificar cada arquivo em um armário de arquivamento Há uma maneira de extrair cada arquivo e examiná-lo individualmente, ou criar um procedimento em que ele seja organizado e classificado para que você saiba onde encontrar coisas E é isso que você também pode fazer no espaço de programação, mas também com as coisas ao nosso redor. Outro exemplo seria se precisássemos adicionar alguém a uma organização, mas para fazer isso, precisaríamos primeiro entrar em contato com todos os outros membros da organização. Essa é uma solução não escalável. É um procedimento não escalável. E queremos ser capazes de analisar isso, reformulá-lo e torná-lo um procedimento mais escalável Então, nós dois vamos nos concentrar no código, mas entendemos que esses princípios também se aplicam à vida diária. Eles se aplicam às coisas ao nosso redor. Então, vamos entrar nesse tópico de ciência da computação e dar uma olhada em algumas matemáticas realmente interessantes. 2. Introdução de Big O: Vamos falar sobre nosso primeiro assunto importante na análise de algoritmos, que será essa ideia de notação. Então, na verdade, vamos evoluir isso para algo chamado notação Big O, que será algo chamado notação Big O, mais ou menos assim , onde você tem um O, e então a notação in vai para dentro dela Mas antes que possamos fazer isso, precisamos descobrir o que exatamente está na notação. Então, na notação está esse tipo estranho de relacionamento, onde está uma função de Agora, fique comigo. Isso é confuso no começo Então, vamos ter que descompactar isso um pouco É esse tipo de forma em que saída é uma função da entrada e, por acaso , elas são a mesma coisa. Então, vamos criar uma espécie de modelo visual disso. Sempre que criamos um algoritmo ou um programa, o que estamos fazendo é criar esse tipo de caixa preta. Então, o que temos é que temos no lado esquerdo uma entrada. Temos coisas entrando na caixa. Talvez sejam seus amigos do Facebook, talvez seja seu Google Drive, todos os dados que você está enviando para ele. É a Internet. Quando você está fazendo upload de algo, essa é a entrada É enviado para algum tipo de lógica, algum tipo de programa. Então essa é, você sabe, a lógica ou a taxa do controlador aqui. E então ele tem algum tipo de saída. Algo acontece porque adotou essa lógica aqui. Algo aconteceu? Algo se moveu, algo foi salvo. Isso é realmente o que a lógica está fazendo. Então, por exemplo, digamos que estamos fazendo upload de fotos. A entrada são as imagens. Nós o enviamos para o controlador. Ele tira as fotos, talvez as reduza para facilitar o armazenamento. Em seguida, ele tira essas fotos e as salva em um banco de dados. Então, ele os coloca e os grava na memória física em um disco rígido. E então essa é a saída. Portanto, a entrada, as imagens, a saída são todas essas operações de salvamento em um disco rígido. Então, o que estamos tentando descobrir é dada a entrada. Então essa é a entrada de in. Qual será a nossa saída. Em relação a isso. E aqui está apenas uma variável. É só porque não sabemos quantos dados estão chegando. Se, por exemplo, tivéssemos um programa que fizesse amigos no Facebook, eu poderia ter talvez, você sabe, talvez eu tenha 182 amigos no Facebook Bem, talvez você tenha 1.373, e seu primo distante tenha 10.157 amigos no Facebook, você sabe, e assim por diante E digamos que não há limite. Eu acho que há um limite. Mas digamos que não haja limite de amigos no Facebook. Isso significa que você pode ter zero até o infinito. Então, não sabemos qual número vai entrar aqui. Então, em vez de tentar inventar apenas um número, dizemos que será apenas o valor do espaço reservado Então, vamos colocar uma entrada de aqui. Pode ser qualquer um desses números do zero ao infinito. Então, qualquer número. E então vai passar por nossa lógica. E então, no final, teremos um certo número de operações. Então, entre essa taxa de pontos aqui, teremos lógica e, em seguida, operações, e então ela produzirá. E queremos saber o que está acontecendo durante esse momento. Como isso se relaciona com isso? Então, isso aqui vai ser a saída da nossa função. Essa será a notação. E o que normalmente escrevemos é que, na verdade, também o escrevemos como um em. Mas escrevemos isso em função de, o que significa que não é a única coisa que colocamos aqui. Na verdade, há um monte de coisas diferentes que poderíamos colocar aqui. Então, o que poderíamos ter está dentro, e isso significa que sempre que inserimos, digamos, 1.000 dados, são necessárias apenas 1.000 operações. Por exemplo, algo assim é se você encontrar vários arquivos no seu disco rígido e quiser movê-los para outro local? Bem, não há mais nada que realmente precise acontecer. Pegamos um e o movemos. Pegamos um e o movemos. Isso está dentro. Para cada dado que você inclui, há apenas mais uma operação. Agora, há coisas diferentes, é claro. Então, em vez de, pode haver um quadrado. Existe algo chamado log of. Há apenas um pedaço de n. Há um cubo. Aí está a raiz quadrada de. E assim por diante e assim por diante. Então, tudo que estamos fazendo é pegar tudo isso e torná-los uma função da entrada. Isso sempre permanecerá o mesmo. Isso sempre vai aparecer. É a sua opinião. É a quantidade de dados que está chegando. À direita está apenas o relacionamento, e usamos apenas porque mostra que é disso que estamos fazendo uma função. Quero dizer, poderíamos usar x e o x ao quadrado e , em seguida, x log de x e coisas assim, e assim por diante e assim por diante Mas o problema é que você pode se confundir com, você sabe, o que exatamente é x. E então temos que colocar algo aqui que diga: Bem, x é igual a n, x é igual E então estamos pensando, por que não ficamos com N para fazer tudo isso. Então, essa é realmente a maior parte confusa da notação: N parece que pode ser a entrada e a saída Mas o importante é que seja a entrada e, em seguida, a saída seja apenas uma função de N. É uma representação de quanto tempo ou quantas operações N deve usar para superar. Para as saídas. Agora vamos dar uma olhada em um pequeno exemplo concreto. Vamos voltar à questão dos amigos do Facebook, porque isso é algo que todos nós podemos visualizar muito rapidamente Digamos que eu tenha um algoritmo aqui. Eu tenho um algoritmo que pega uma quantidade de amigos do Facebook e os insere em um banco de dados no momento ou no relacionamento de E digamos que eu tenha outro algoritmo aqui. Que faz exatamente a mesma coisa. Exceto que, em vez disso, recebe o mesmo valor de entrada, então recebe, mas produz ao quadrado Há um pouco menos de eficiência aqui. Então, agora podemos olhar para esses dois e compará-los um pouco. Qual desses algoritmos é mais rápido? Então, se prosseguirmos e fizermos algumas contas rápidas, digamos que vamos testar isso com 100 Facebook France. Então, neste primeiro, bem, serão apenas 100 entradas em nossa pequena caixa preta e sairá com 100 operações diferentes para fazer o que quer que faça. Bem, na parte inferior aqui, temos 100 entradas em nossa pequena caixa preta. Lembre-se de que sempre permanecerá o mesmo, mas nossa função é n ao quadrado, que significa que agora precisamos pegar 100 e elevar ao quadrado, que acaba sendo 100 vezes 100, que significa que nosso total será Opa, temos que colocar os zeros Quatro zeros ou 10.000. Então você pode ver que o primeiro levou apenas 100 operações, enquanto o segundo levou 10.000 operações. Nós vamos falar sobre isso um pouco mais tarde. No entanto, os padrões de crescimento deles são o que importa. Dentro do que temos na verdade, temos algo chamado linear e, em seguida, com o quadrado, temos algo chamado exponencial, que significa que o crescimento aumenta cada vez mais com o tempo Mas, como eu disse, falaremos sobre isso mais tarde. O que eu meio que queria te mostrar é como nós olhamos para isso. Portanto, temos um valor de entrada e um valor de saída. Temos outro valor de entrada e outro valor de saída, e há dois algoritmos diferentes, algoritmo A e algoritmo B. E podemos dizer rapidamente: Bem, é definitivamente mais rápido que B. A é que você poderia dizer que é maior que B, ou você poderia dizer que ele usa menos tempo do que B ou como você quiser compará-los. Mas este é rápido e este é lento por causa de quantas operações eles realizam. Então, qual é o objetivo? O que estamos tentando fazer aqui? Isso nos permite ver como um algoritmo é dimensionado com o tamanho da entrada. Se projetarmos um algoritmo, queremos saber se ele é eficiente com mais pessoas e informações? Queremos que nossos programas tenham sucesso. Então, queremos criar soluções que escalem. E isso é algo que você ouvirá muito. Queremos criar soluções escaláveis. E uma solução escalável é uma solução que não funciona apenas para a quantidade exata de pessoas que a estão usando atualmente Então, por exemplo, como eu disse, vamos continuar com esse exemplo do Facebook. Imagine se o Facebook usasse esse. Imagine se ele usasse o algoritmo quadrado porque não achava que eles iriam escalar Bem, o fato é que somos programadores. Estamos tentando tornar nosso produto o melhor produto possível. E isso significa que queremos que o produto tenha sucesso. E quando um produto é bem-sucedido, mais pessoas o usam, mais dados são inseridos e o algoritmo terá que usar essas novas peças Se não criarmos um programa que seja escalável, nos depararemos com todo o problema exponencial, onde sim, isso funcionará para 100 e talvez funcione para 1.000 e, ei, talvez funcione para Mas se você perceber que é uma parte muito pequena da população. Digamos que talvez 1 milhão de pessoas. Quer usar nosso programa. Bem, agora temos uma solução que não funciona para 1 milhão de pessoas. Se fizéssemos 1 milhão vezes 1 milhão. Bem, teríamos um número extremamente grande. Um número que nem mesmo é compreensível pelo nosso cérebro. E isso, na verdade, faremos algumas dessas contas um pouco mais tarde. Um número tão grande acaba levando dias ou até anos para ser executado. Então, um computador, o computador que pode, você sabe, conectar on-line e fazer todas essas contas rápidas levará dias ou anos para realizar uma tarefa simples, porque o programa não é escalável Então essa é a base da notação. É uma forma padronizada de notação que nos permite comparar dois algoritmos em um ambiente completamente estéril, o que significa que não precisamos implementá-los Podemos simplesmente olhar para eles. Isso nos permite compará-los e descobrir qual deles é mais escalável Qual deles será mais rápido sempre que adicionarmos mais pessoas, mais dados ou mais operações a ele E esse é o objetivo da notação. E na próxima aula, continuaremos mergulhando nisso e continuaremos descompactando a caixa que é a notação para que possamos obter essa base sólida para poder comparar 3. Notação de N: Vamos nos aprofundar um pouco aprofundar notação final e examinar alguns dos objetivos por trás do motivo pelo qual nós, cientistas da objetivos por trás do motivo pelo qual nós computação, usamos a notação final e o que estamos tentando extrair Porque a notação final pode ser usada de várias maneiras diferentes Há vários tipos diferentes de combinações ou informações que podemos extrair usando essa notação. Mas o que eu quero abordar é o núcleo, para o qual a maioria dos cientistas da computação o usa. E quais são alguns dos objetivos? Por que o usamos? Então, quando usamos a notação, o que estamos fazendo é procurar padrões grandes, e estamos procurando por esses padrões em uma espécie de espaço teórico, o que significa que não vamos realmente ter um programa implementado ou algo parecido Estamos apenas procurando por esses padrões grandes. Estamos procurando, por exemplo, se um gráfico é assim e o outro é assim. Não nos importamos se em algum momento temos esse gráfico na parte inferior, talvez seja assim , e então esse de cima fique assim ou algo assim? Neste momento, não nos importamos que, sim, haja um ponto aqui quadrado é, na verdade, um pouco mais eficiente Isso é essencial quando você realmente tem um algoritmo à sua frente e está tentando otimizá-lo Isso é o que talvez um otimizador de servidor possa fazer ou gerenciamento de banco de dados, coisas assim Só nos preocupamos com isso, com a teoria em geral. Estamos procurando qual equação piora com o tempo. Então, à medida que avançamos em direção ao infinito, à medida que avançamos em direção à quantidade desconhecida de dados que poderiam vir do algoritmo interno, o que acontecerá com nossa equação Vamos obter aquela equação que não pode ser concluída neste século por causa de quantos cálculos serão necessários, ou vamos obter algo assim, em que não importa quantos cálculos façamos. Só vai continuar funcionando. E é isso que queremos ver. Queremos ver essa grande mudança de eficiência entre diferentes algoritmos. Esse é o objetivo da notação e é por isso que usamos a notação. Portanto, por causa disso, há algumas regras que normalmente usamos com notação. E são apenas uma espécie de abreviatura que usamos para não nos confundir E, novamente, para chegar a esse panorama geral. Portanto, não passamos todo o nosso tempo nos detalhes. Na verdade, podemos simplesmente olhar para duas equações e dizer, sim, esta escala um pouco melhor A primeira é que não nos importamos com múltiplos. E o que isso significa é, por exemplo, se tivermos n ao quadrado e depois três n ao quadrado. Eles são, para todos os efeitos, iguais. Eles são basicamente iguais um ao outro. Nós não nos importamos. Quero dizer, três, você sabe, talvez você possa justificar para si mesmo Sim, três é bom, mas isso pode ser, você sabe, isso pode ser como 3 milhões, 3 bilhões, 30 bilhões, 30 trilhões Pode ser qualquer número que quisermos, e isso não importa. Pegamos esse múltiplo e o apagamos. Não nos importamos com os múltiplos. E isso se resume, novamente, à grande coisa geral, não importa quão grande seja esse número em algum ponto entre zero e Em algum momento, n ao quadrado fará com que esse número nem seja efetivo Imagine se em algum momento fosse igual a, eu não sei. 300 Google, e o Google é 100 zeros no final. Então você tem 100 zeros no final disso. Você acha que os 3 milhões que estão sendo multiplicados realmente importam nesse momento Quero dizer, vai ser uma diferença muito, muito pequena no resultado final. Estamos falando como, você sabe, vai ser a diferença de um número parecido com este ou entre um número que tem isso nele. Você sabe, um pouco mais sobre isso. Isso não importa em nada. É por isso que, em teoria, sempre que vamos do zero ao infinito, não nos importamos com os múltiplos Então, para comparar dois algoritmos, pode ser de 3 milhões ao quadrado, e estamos comparando isso com “não , não importa Ainda estamos apenas comparando n ao quadrado com n ao cubo. Então você sempre remove os múltiplos no começo. Agora, como obtemos esses múltiplos? Bem, digamos que temos uma equação que faz isso. Nós temos a caixa preta, então temos as entradas vindo aqui Temos uma operação quadrada. Em seguida, trazemos todas essas entradas para outra caixa preta, outra operação quadrada Ok. E digamos que, no final, temos outra, mas essa é apenas uma operação de login. Então, com um algoritmo como esse, na verdade, criamos uma pequena equação aqui. Nós fazemos algo assim. Entramos ao quadrado mais quadrado mais o login. E então podemos realmente combiná-los em um múltiplo. Então, isso é dois n ao quadrado mais login. E é assim que criamos um múltiplo, e você sabe que o que estamos dizendo aqui é que realmente não nos importamos com o múltiplo. Eu posso fazer isso quantas vezes quisermos. Estamos apenas analisando esse grande fator de mudança. Então, isso se torna quadrado mais o login. Então, isso chega à nossa segunda regra. Pegamos a maior equação. Então, sempre que temos uma equação como essa, novamente, ela não vai escalar tão rápido quanto isso. Quando entramos nesses números gigantes com 50 zero, 1 bilhão de zeros no final, quero dizer, dois e terminamos, então em algum momento pode haver 1 bilhão de zeros Pode haver 1 bilhão de zeros no final disso, não o número bilhão Estou falando de 1 bilhão de zero real. Seria um número tão longo que, você sabe, você não poderia encaixá-lo em toda a Terra. Pode haver um número como esse. Quero dizer, estamos indo para o infinito aqui. Então, em algum momento, isso vai se tornar tão maior do que esse número que não nos importamos Este é apenas um pequeno obstáculo no caminho para qualquer que seja esse número Isso só vai afetá-lo em talvez 0,000.000 1% em algum momento Em algum momento, é afetado por quase nada. Vai ser um número muito pequeno. É quase zero. E por causa disso , também o removemos do final e deixamos uma equação como essa para dizer: Ei, todo esse algoritmo aqui, todo esse algoritmo aqui é na verdade, apenas quadrado Portanto, há algumas regras de escalonamento. Agora, se você quiser ser técnico, se estivermos otimizando o servidor ou qualquer outra coisa em que realmente temos uma equação à nossa frente, sim, isso provavelmente é algo que queremos analisar, porque se estamos olhando para um servidor real e temos uma equação que pode executá-lo n quadrado mais login, em vez de dois quadrados mais n login queremos fazer isso porque será mais rápido na prática real. Mas, novamente, isso não é prática. Isso é teoria. Estamos tentando descobrir apenas as diferenças das aplicações de grande escala. Então, nesse sentido, fazemos essas duas regras, dividimos em apenas o que é o grande tempo de execução disso. E, na verdade, temos pequenos modificadores de O grande, pequeno O e Beta falaremos sobre eles daqui a pouco , o que tornará isso um pouco mais fácil de entender. Então, vamos dar uma olhada em alguns gráficos aqui. Vamos dar uma olhada, você sabe, no que venho detalhando aqui com todos os números, eles superarão seus parceiros, eles superarão seus parceiros, então só nos importamos realmente com os grandes Então, aqui, temos uma espécie de representação de um gráfico aqui. Temos todas as coisas sobre as quais estamos falando. Este é um, que é o tempo constante. Isso significa que podemos colocar 1.000, podemos colocar 1 bilhão, podemos colocar qualquer número que quisermos, e isso exigirá apenas um número constante de operações. Então, talvez sejam necessários apenas três. Talvez sejam 62 operações diferentes. Não importa o número que coloquemos , são necessárias 62 operações. Então é isso que é o tempo constante. E então obtivemos esse tempo de login, e você pode ver que tem esse tipo de gráfico que é assim. Então, temos apenas a raiz quadrada de N, que é semelhante ao login, mas aumenta com o tempo. Temos linear ou. Linar é apenas uma linha reta em um ângulo. No login, parece um pouco assim, mas depois entra em uma linha linear, talvez com pequenas tendências para cima Então chegamos ao quadrado, o que é exponencial. Então temos dois fatoriais n, que são ainda mais exponenciais e quase que vão direto para o ar E então entramos em fatorial, que pode muito bem ser assim Ele vai quase direto para o ar e cria números tão grandes que, se algum programa for executado em fatorial, está errado Isso tem que ser feito de uma maneira melhor. entanto, vamos dar uma olhada nos exemplos do que tudo isso aconteceria se adicionássemos números a eles, quais seriam os tempos de execução. Então, nessa situação, estamos dizendo que podemos ver aqui, é o número de entradas, e em capital, aqui está o número de operações Então, aqui, esses são os pequenos. Isso é o que estamos inserindo. Estamos inserindo 100.000 ou 10.000 ou 1110 ou um. E essa é a saída quanto tempo levaria para ser executado. E você percebe que na primeira linha, na verdade, é meio interessante que com apenas uma peça, não importa o que você tenha, ela sempre funcionará basicamente ao mesmo tempo. Claro, pode haver algumas pequenas diferenças, por exemplo, talvez um tempo constante. Talvez seja uma vez em que, se constantes vezes 62, tudo isso funcionaria um pouco mais rápido Mas, novamente, isso está no âmago da questão e realmente não nos importamos Queremos analisar essas tendências à medida que elas avançam com o tempo. Então, se formos para fatorial, o E mais no final aqui, isso significa quantos zeros estão no final Então isso significa que isso é 9,3 ou nove três com 157 ou 156 zeros se você De qualquer forma, há muitos zeros no final desse. E este é, você sabe, é quatro com 2567350000, 456.000 E você pode perceber o quanto isso muda com o tempo. E então temos dois aqui. Isso é dois e depois dois, algum fatorial. Então, você sabe, nessa situação, dois décimos ou dois para 100 e assim por diante e assim por diante Mas de qualquer forma, você pode notar que até mesmo esses dois. Esses dois estão basicamente no ar. Há uma grande diferença. É a diferença de 400 a 56 mil zeros e 300 ou 30.000 zeros e 300 ou 30.000 E então seguimos em frente cada vez mais e mais. E o que temos é que reduzimos até n ao quadrado, o qual estamos falando, mostramos o quão ineficiente é E isso, na verdade, parece muito pequeno em comparação com dois dos fatoriais n e n quando aumenta cada vez mais. Então, temos N login. Na verdade, estamos obtendo números legíveis aqui, apenas 1.660.000, depois apenas n, o que, é claro, será equivalente a quantos colocarmos porque N sempre vai para N. É isso que está representando E então começamos a entrar nesses aqui embaixo, onde você percebe que eles são realmente legais. Eles são algoritmos eficientes aqui. Colocamos 100.000 e fazemos apenas 316 operações. Há uma mudança cada vez menor à medida que avançamos com o tempo. E isso, você pode perceber como poderíamos fazer algum tipo de algoritmo se tornasse realmente muito eficiente. Quero dizer, olha isso. Então, temos a diferença entre 90 aqui. E nessa diferença, aumentamos em três operações. Agora, temos a diferença de 900 aqui. E quanto subimos? Bem, apenas por cerca de três operações. Então, temos a diferença de 9.000 novos dados. Quanto vamos subir? Bem, cerca de três operações. E então aumentarmos em 90.000 é o próximo passo. E quanto temos? Bem, apenas três operações. É exatamente o oposto. Quanto mais adicionamos, menos ele sobe. Aumenta cada vez menos com o tempo. E, na verdade falaremos sobre algoritmos ao longo deste curso que funcionam assim. Ele usa algo chamado dividir e conquistar, onde na verdade nos separamos Informações como essa, e dessa forma, podemos acessá-las muito, muito rápido, em vez de ter que examinar cada peça para chegar ao que queremos. Mas de qualquer forma, isso é apenas outro resumo da notação, como ela escala e, em seguida, alguns dos termos que usamos com notação Na próxima palestra, vamos dar um exemplo do mundo real, talvez adicionar um pouco do lado teórico e examinar as diferenças delas se realmente aplicarmos, você sabe, 0,01 segundo a cada operação Podemos ver o quão massivos esses números se tornam e as diferenças entre eles. 4. Exemplo de notação de N: Vamos colocar alguns números que estamos falando para colocar isso um pouco de respeito que todos possam entender. Então, vamos analisar esse problema aqui e dar uma olhada nas diferenças entre a aparência de seu login e do quadrado Na última palestra, analisamos esse tipo de taxa gráfica aqui Então, o que estamos vendo é essa taxa aqui, logada e quadrada E nesse tipo de pequena taxa gráfica aqui, quero dizer, eles parecem muito próximos um do outro, certo? Parece que não haveria muita diferença entre eles. E isso é o que eu quero mostrar é que existem grandes diferenças até mesmo entre eles aqui, e a mudança de eficiência é muito importante. Então, vamos dar uma olhada neste exemplo. Vou simplesmente rever isso e espero que mostre as diferenças Portanto, temos ou dizemos que cada ciclo de um programa leva aproximadamente 0,001 segundos, que acredito ser um milissegundo Então, o que estamos dizendo é quanto mais rápido login será obtido do que o quadrado, se 1.000 dados forem inseridos e, mais abaixo, se 25.000 dados forem inseridos E então, com isso, o que vamos fazer é simplesmente conectar isso. Vamos calcular quantas operações são necessárias, multiplicar por um milissegundo e, em seguida, obter quanto tempo um programa que fosse executado dessa forma levaria Então, nosso primeiro exemplo, temos isso logado. Multiplicamos 1.000 por log de 1.000, e estamos usando log baseado em dois, lembre-se Então, todos esses são baseados em registros dois. Então, o que obtemos é 9.960 vezes milissegundos, e tudo isso resulta Então, se formos com o quadrado, vamos fazer 1.000 ao quadrado Isso vai ser 1.000 vezes 1.000, o que acaba nos dando o número 1 milhão aqui. E com 1 milhão, multiplique os milissegundos e obtemos 1.000 segundos ou 16 minutos Portanto, a diferença entre usar esses dois algoritmos é que um deles levará 9,96 segundos. Então, você sabe, 10 segundos. Não é muito longo, e o outro levará 16 minutos para ser concluído. Imagine se você estiver on-line e enviar um formulário, e um deles usar o login n , enquanto outro formulário usa n quadrado, muitas pessoas poderiam esperar 10 segundos para que um formulário fosse enviado Mas se tivéssemos que esperar 16 minutos, isso não aconteceria. Ninguém vai fazer isso. Então, vamos dar um exemplo um pouco mais alto. Digamos que temos 25.000 dados. Então, fazemos as 25.000 peças. É 25 vezes baseado em registros, dois de 25.000. Recebemos 365.000 vezes milissegundos. Isso então resulta em 6 minutos e 5 segundos. Observe aqui que é importante observar que, mesmo com $25.000 ou 24.000 a mais de dados. Isso ainda leva 10 minutos a menos do que se usássemos n ao quadrado no anterior De qualquer forma, agora vamos dar uma olhada aqui no quadrado n. Então, fazemos 25.000 vezes 25.000. Isso nos dá 625 milhões multiplicando por milissegundos, e temos algo Temos sete dias e 5 horas para fazer isso. Então, são apenas 25.000 dados Agora passamos de 6 minutos para sete dias E, por exemplo, se fizéssemos 250.000 dados, essa taxa aqui seria algo em anos ou milhares de anos Seria algo em que não seria realizado em nossa vida, ou na vida de nossos netos, ou na vida de nossos netos, o sol poderia se apagar antes de chegarmos à conquista, antes que o programa realmente termine a Então, espero que este pequeno exemplo aqui, apenas com essa pequena matemática e adicionando os milissegundos aqui, você possa ver a grande diferença, mesmo que pareçam iguais aqui e talvez até um pouco aqui embaixo Quando aumentamos para mais e mais números, começamos a ter inconsistências gigantescas E essas inconsistências gigantescas são a essência do teorema da ciência da computação É disso que trata o currículo de ciência da computação. Se estamos apenas tentando descobrir que tipo de estrutura de dados ou técnicas devemos usar em cada situação específica para que possamos criar os algoritmos mais eficientes possíveis para que acabemos realizando as coisas rapidamente, em vez de gastar mais tempo, recursos ou nem mesmo sermos capazes de realizar anúncios porque isso levaria muito tempo Então, isso é apenas um pequeno exemplo disso. Ok. 5. Big O: Então, agora que temos uma boa compreensão de N e de como exatamente ele funciona, e isso está ligado à nossa análise de algoritmos, podemos começar a adicionar algo a isso. Então, sabemos que é uma forma de classificar a rapidez com que um algoritmo é executado, dado um determinado número dado um determinado número, em quanto tempo levará em relação a esse número? Então, vai levar na hora certa? Então, se fosse 1.000, seria igual a 1.000 ou seria necessário algo como n vezes ao quadrado, onde quando for 1.000, será igual a 1 milhão E esse é um tipo de classificação muito importante. No entanto, os programas não são tão fáceis. Eles não funcionam apenas na hora exata o tempo todo. Muitas vezes eles têm um vínculo. Então, por exemplo, talvez quando estiver carregando, ele execute um n ao quadrado, mas execute um in e, em seguida, exporte o login no login Então, temos que ser capazes de analisar isso, analisar o programa e dar uma classificação do programa como um todo. Então, por exemplo, neste programa, sempre analisaríamos o pior caso sempre indo para o pior caso, considerando o quadrado No entanto, em determinadas etapas, ele será executado mais rápido. E por causa disso, na verdade temos esse tipo de taxa de sistema aqui, que classificará os limites em nossa notação Então, vamos isso e dar uma olhada nisso. Esses aqui em cima são chamados de Omicron. Você tem Theta no meio e depois Omega, e este é Omega minúsculo aqui embaixo Então você pode ver que eles são alfabetos gregos, mas muitas vezes, em matemática, usamos grego porque o alfabeto fica confuso Então, usamos o grego para representar simbolicamente as coisas. E neste caso, cada um desses símbolos gregos representa simbolicamente um limite Então, o que você tem aqui é desenhar, por exemplo, um limite bem no meio aqui. E aqui em cima é mais rápido. Então eu vou dizer que aqui em cima vai ser mais rápido, e aqui embaixo vai ser mais lento Então, nossa primeira notação é pequena O, e você pode ver que simplesmente não gostamos de dizer Omicron, como uma grande notação Omicron Então, dizemos um pequeno grande O. E tão pouco aqui. Significa apenas que será mais rápido, que significa que o programa sempre será mais rápido do que esse limite. Então, por exemplo, se nosso limite fosse quadrado, aqui mesmo, se tivéssemos um pequeno O de n ao quadrado. Aqui, veríamos que isso significa que nunca tocará n ao quadrado Na verdade, sempre será mais rápido do que n ao quadrado. Então, sempre estará logo acima dessa linha, mas mais rápido do que n ao quadrado Então, o que podemos fazer é usar isso para descobrir o limite. Então, o próximo que temos é que temos o grande O. E o grande O significa que será mais rápido ou igual a. Isso significa que ele tocará essa linha ou será mais rápido. Então, na pior das hipóteses, isso é algo muito importante aqui. Isso significa, na pior das hipóteses. Vai ficar em quadrados. O próximo que temos é Theta, o que significa que não vai tocar em nenhum desses dois Não vai baixar e não vai subir. O que vai acontecer está nesta linha. Portanto, não importa o que seja em quadrado, estará ao longo desta linha em algum lugar E então a próxima descida que temos é mais lenta ou igual a. Então, temos este é Omega, e este é mais lento ou igual a. Então, ele toca essa linha e é sempre mais lento. Então, você sabe, temos n para o terceiro n para o quarto aqui embaixo, aqui em cima, talvez tenhamos. Portanto, é sempre mais lento do que isso, ou igual a n ao quadrado. Então, na melhor das hipóteses. Então, este é, na melhor das hipóteses. Vai funcionar assim se você colocar isso. Então, por exemplo, se escrevermos de n ao quadrado assim. Vamos cortar um pouco aqui, mas se n ao quadrado assim, entendemos que esse programa sempre funcionará da melhor forma, será executado com n ao quadrado O que significa que pode funcionar pior do que isso. E, abaixo disso, temos mais lento que, o que significa que sempre funcionará pior do que n Nunca tocará ao quadrado, mas funcionará pior do que o nSquared E então, por que isso é importante? Por que queremos nos concentrar nesse de todos esses? E isso porque Big O dita o pior cenário possível E estamos preocupados com o pior cenário possível porque, dadas as probabilidades e as estatísticas, nosso programa pode abordar o pior cenário possível em um ponto, e queremos saber, sem dúvida, qual é o pior cenário possível? É por isso que usamos o grande O. É, na pior das hipóteses, o que vai ser. E você pode ver, eu vou abrir o gráfico novamente aqui. Quando temos essa ideia, quando temos a capacidade de dizer qual será nosso programa, podemos realmente começar a preencher isso. Então, se tivermos, por exemplo, talvez um grande O de N. Entendemos que, na pior das hipóteses, ele estará dentro. Então, pode estar dentro, mas também pode ser algo maior do que dentro. Assim, podemos preparar todos os nossos diagramas de tempo e esboços e qualquer coisa assim, partindo do pressuposto de que nunca vai ficar desse lado da linha Sempre vai ficar desse lado. E isso é muito poderoso porque agora podemos começar a comparar os piores casos de programas, e podemos começar a ver que talvez quando um programa é escalado, por exemplo, se tivéssemos um programa de login versus um programa de login, poderíamos ver que quando este for escalado, será pior do que este. Então, vamos analisar isso um pouco, e podemos ver por que algumas delas não têm sentido Então, temos um programa que roda em Little O n quadrado, que significa que é mais rápido do que n quadrado. Isso significa que pode ser de n ao quadrado até Basicamente, tem que ser apenas mais rápido do que isso Portanto, não será quadrado, mas pode ser qualquer coisa mais rápida do que quadrado E este é como o grande O. Mas o problema é o que nos é dado, então é o pequeno O de N. Na verdade, não podemos tocar nisso. Então, isso só torna tudo um pouco confuso. Isso nos dá um limite, mas não facilita a nossa visão. Não podemos olhar imediatamente para isso e dizer : Oh, isso vai durar. Temos que olhar para isso e dizer: Oh, vai correr mais rápido do que, mas não sabemos realmente onde. E isso realmente não nos dá muito espaço de manobra. E então temos nossa grande notação O. E isso é o que acabamos de ver, é que podemos ver isso e dizer: Oh, na pior das hipóteses, ele será executado no login. Theta seria ótimo se pudéssemos sempre usar theta. Isso é igual ou às vezes é usado como média, mas na maioria das vezes, significa igual a. Então, isso seria ótimo. Mas o problema é que os programas nem sempre funcionam exatamente de acordo com uma linha. Às vezes, eles podem ser executados em um ponto, ele executa um, mas em um ponto, ele é executado e faz login, e vai para qualquer lugar entre isso. Então, Theta é muito específico para que possamos realmente gostar. E então, eles são praticamente insignificantes porque não nos fornecem muitas informações Pense sobre isso. Esse aqui, que é Omega Então Omega ao quadrado. Isso significa que será mais lento ou igual ao Omega quadrado, o que é como você está dizendo, nosso programa será executado ao quadrado ou será mais Como devemos planejar com isso em mente? Porque mais devagar poderia ir para o infinito. Pode ser o mais lento possível, e nunca seríamos capazes de nos preparar para isso, porque nunca teríamos um limite. Nós diríamos: Ok, então vamos ver o quão rápido pode levar n ao quadrado, pode levar em fatorial, pode levar o infinito Isso não nos ajuda a analisar o programa porque há esse lado infinito nele. E exatamente a mesma ideia com o pequeno Omega aqui também, é que ele vai para o infinito do lado ruim, o que não nos ajuda Então, isso nos ajuda porque o lado ruim é, deixe-me correr um pouco disso aqui e abrir um pouco mais de espaço. Então, isso nos ajuda porque o lado ruim. Então, digamos que aqui está indo 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. Tipo, se ele voltar e funcionar tão constantemente, tudo bem. Isso está perfeitamente bem. Isso significa que nossos programas estão funcionando muito bem. Claro. Mas podemos planejar isso. Significa apenas que nosso programa será executado mais rápido do que esperávamos. Então, o que podemos fazer é planejar o pior cenário possível. No entanto, se você for do outro lado dessa linha, não poderá planejar o infinito. É por isso que Big O é tão importante , pois é a mais útil de todas essas notações Isso nos dá o pior cenário possível. Então, vamos dar um exemplo de como podemos aplicar isso a um problema específico. Então, normalmente, o que você sempre faz é usar o pior cenário possível, seja, em que ponto do programa ele será o mais ineficiente Então, aqui, por exemplo, digamos que temos um grande O de n ao quadrado Tivemos um grande número de login. Grande O de N e depois grande O de tempo constante. E então esses aqui embaixo são ótimos. Mas o fato é que, não importa o que aconteça, sempre seremos asfixiados por esse cara aqui E isso é porque nosso tempo de carregamento aqui em cima está em quadrados, o que significa que esse programa vai aumentar em quadrados mais o login, mais, mais o primeiro, o me permite mantê-lo meio que Vamos mais um. E você pode estar pensando, por que estou fazendo isso? E isso porque você pode realmente somar cada parte das etapas. 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. Então, você pode realmente adicioná-los todos juntos. E eu me lembro do que estávamos fazendo antemão quando falávamos sobre como tentamos ver um programa à medida que ele vai até o infinito Então, se olharmos para esse número, qual deles vai superar os outros quando chegarmos ao infinito Bem, por exemplo, vamos colocar em 1 milhão. Quão significativo é 1 milhão, que será verso 1 milhão, será verso, talvez algo em torno de 3 milhões, talvez algo em torno de 3 milhões, será verso 1 quatrilhão ou talvez 1 trilhão, seis um e Este vai ser substancialmente maior. Essas serão uma porção cada vez menor do número à medida que ele vai para o infinito. Até o ponto em que eles chegarão perto de zero como significância. Então você vai começar a ter, você sabe, um número do Google, que é 100 zero mais talvez 8 milhões aqui ou algo parecido. E isso significa que essa parte aqui é completamente insignificante neste momento Então, o que fazemos é eliminar os inferiores e o tempo de execução desse programa está em quadrados E então, vamos meio que cimentar isso com outro exemplo aqui. Digamos que tivéssemos uma grande palavra, tivéssemos um grande O de n ao quadrado. Grande O de n ao quadrado. Big O ou eu tenho que desenhar o s aqui. O grande O de n ao quadrado novamente, e então digamos que agora temos um grande O de n terceiro. E agora o que temos aqui é que temos n ao quadrado mais n ao quadrado mais n ao quadrado mais E então podemos realmente combiná-los até três n ao quadrado mais n no terceiro E agora, lembre-se do que falamos na última palestra sobre a notação final Esses não importam. A taxa constante aqui não importa porque, à medida que avançamos para o infinito, ela se torna cada vez menos significativa até que, quando chegamos a um número suficientemente alto, ela se torna basicamente zero Então, podemos riscar esse. E agora temos n ao quadrado mais n terço. E então, é claro, este vai decolar muito mais alto do que o outro. Então, nosso programa acaba ficando em terceiro lugar. E agora, como todas essas são grandes notações O, sabemos que, na pior das hipóteses, nosso programa será executado em terceiro, que significa que agora temos esse limite de terceiro e o infinito do tempo de execução é executado dessa E agora podemos planejar que, na pior das hipóteses, teremos a terceira, e podemos planejar tudo até o tempo constante, porque agora tudo o que temos é exatamente esse limite aqui. Entendemos que, você sabe, se colocarmos 1 milhão de dados, isso pode não funcionar. Talvez possamos tentar trazer isso de volta, mas isso nos dá um lugar para começar. Isso nos dá um lugar para compará-lo com os outros. Então essa é uma grande notação O. Muito importante e, com o tempo, você começará, basicamente, isso se tornará natural só de ser capaz de ver isso. Você realmente nunca verá esses outros com muita frequência. Às vezes, você verá este. Se disser que um determinado ponto de um programa é igual a esse tempo de execução , você verá este. Mas, além disso, esses dois provavelmente nunca verão e você provavelmente nunca verá o pequeno mercão dois Então, essas anotações aqui meio que as memorizam, entendem o que significam, e você deve estar pronto para começar Você começará a entender muito mais documentos de ciência da computação. 6. Mundo real: Agora, aprendemos muita teoria. Vamos dar um passo atrás e examinar algumas análises de código do mundo real. Agora, não vou usar código complexo ou qualquer tipo de código que você precise saber aqui. É tudo pseudocódigo, e vou explicar isso em cada etapa do processo, como se você nunca tivesse tocado em código antes porque é assim que eu quero explicar todo esse tipo de curso, é que estamos analisando a teoria por trás de tudo, não o No entanto, aplicá-lo a algo real pode ajudá-lo a conhecer , a descobrir alguns dos conceitos, e é por isso que estamos fazendo isso. Então, vamos dar uma olhada no nosso primeiro trecho de código. Eu vou seguir em frente e passar por isso aqui. Então, o que temos é que diz, eu escrevi em pseudo, que meio que é lido diretamente da língua, algo que você pode ver e entender o que está acontecendo Então, diz, para cada dado na lista de dados. Então, vamos criar uma lista de dados aqui em um segundo, imprimir os dados na tela. Ok, fácil o suficiente. Digamos que inserimos aqui um dado, uma lista aqui que talvez seja três, dois, dez. E depois vamos para Buffalo. Então, são três números inteiros e uma string. É assim que seria tecnicamente classificado, mas nem vamos analisar isso Esses são quatro dados. Então, o que estamos dizendo é que, para cada dado, para cada dado em nossa lista, vamos imprimir esses dados na tela. Então, em nossa situação aqui, o que está acontecendo? Bem, nesta situação aqui, em iguais, um, dois, três, quatro, porque temos quatro dados Então, nessa situação, n é igual a quatro. Então, agora vamos ver qual seria o tempo de execução disso. Então, temos para cada dado e depois imprimimos na tela. Então, ok, vamos ver a lista aqui. Vamos usar nosso primeiro dado. Portanto, nosso primeiro dado é três. Pegamos três da nossa taxa de documentos aqui. Então isso é zero em uma matriz ou, se você quiser pensar sobre isso, isso é um, dois, três, quatro. Os computadores geralmente usam zero, um, dois, três, é apenas a maneira como eles funcionam. Então, vamos pegar nosso primeiro dado aqui e depois imprimi-lo na tela. Então pegamos nossos três e imprimimos na tela. Então, isso é um tempo de execução. Portanto, nosso tempo de execução agora é um. E agora vamos pegar os dois porque estamos analisando a lista. Então, para cada dado, abordamos esse. Então, agora vamos para este. Agora pegamos dois e imprimimos na tela. Então, agora nossa tela se parece com isso. Então, esse é um tempo de execução adicional. Esse é um tempo de execução. E agora imprimimos nosso próximo dado , que é dez. Então agora temos três, dois, dez. Esse é o tempo de execução adicional aí mesmo. E agora imprimimos búfalos, que seriam três, dois, dez búfalos. Assim. E isso é um tempo de execução adicional. Porque tudo o que estamos fazendo é pegar os dados e imprimi-los Não há nenhum processo de pensamento especial acontecendo aqui. Estamos apenas pegando, imprimindo, pegando, imprimindo, pegando, imprimindo E agora, se somarmos tudo isso, veremos que resulta em um mais um mais um mais um, o que é igual Portanto, nosso tempo de execução nessa situação é quatro, e você verá que nosso tempo de execução igual à quantidade de taxa E se pudéssemos pensar nisso teoricamente por um segundo, se tivéssemos 1 milhão de dados aqui, haveria em nenhum momento do programa que precisaríamos tocar em mais de 1 milhão de dados Então, não importa o que façamos aqui, execução será qualquer que seja o nosso n, o que significa que o que temos aqui é um tempo de execução de N. Nessa situação específica, poderíamos realmente usar Theta como n porque na verdade igual a n. Não há nenhum tipo de espaço de manobra aqui, mas vamos dizer que, na pior das hipóteses, estará dentro, porque essa é a notação que gostamos de Então, este é um exemplo de um in, que é chamado de quatro loops. Portanto, quatro loops são normalmente um exemplo de entrada em uma situação Vamos abordar um problema um pouco mais complexo aqui. Então, deixe-me detalhar isso também. O que temos aqui é que diz, para cada dado em uma lista de dados. Então, isso significa que, em vez de chamá-lo de data agora, cada dado em uma lista entrará. Verifique se os dados estão na lista. Então, vamos usar cada dado na lista de dados, se n for igual a W, imprima verdadeiro Então, vamos detalhar isso um pouco também. Vamos usar o mesmo exemplo anterior, que foi três, dois, dez búfalos. Assim. E nessa situação, nossa entrada ainda é igual a quatro. E agora o que vamos fazer é analisar o primeiro problema aqui. Então, vamos dar uma olhada, certo. Agora, digamos que vamos pegar cada um desses dados, então vamos pegar os três, e agora estamos prontos. Agora, para cada dado nessa lista de dados, você pode ver que esses nomes são exatamente os mesmos. Então isso significa que essa é a lista de dados. Estamos verificando os dois. Então, temos nossos três. Pegamos nossos três. E agora estamos tentando verificar se esses três aqui são equivalentes a qualquer coisa aqui em cima. E a única maneira de fazer isso é a força bruta. Então, vamos pegar esses três. Vamos verificar isso com o primeiro. Vamos verificar isso com o segundo. Vamos verificar isso com o terceiro. Vamos verificar isso com o quarto. Então, isso vai ser uma, duas, três, quatro operações. Então, vamos quebrar isso, tipo, bem longe aqui embaixo. Nós temos nossos três. Pegamos nossos três e agora estamos verificando se é igual Deixe-me fazer isso um pouco menor , porque será um gráfico um pouco maior. Então, estamos dizendo que três igual ao primeiro pedaço de nossos dados, é igual ao primeiro pedaço de nossos dados, que será o três novamente porque não dissemos que ele começasse um número que não fosse ou qualquer coisa sofisticada desse tipo Estamos apenas verificando essa lista pela segunda vez. Então, temos nossos três e estamos verificando se é igual ao primeiro. Então, é igual a três? Sim, é verdade. Então, isso imprimirá uma mensagem verdadeira. E isso exigiu uma operação. Agora, nossos três são iguais a dois, não é? Portanto, não imprimimos nada. Essa é uma operação. Nossos três são iguais a dez? Isso não acontece. Então essa é uma operação. Nossos três são iguais a Buffalo? Isso não acontece. 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 segundo aqui embaixo. Vamos ver que T one será aquele com quem estamos verificando. Eles são exatamente iguais, mas eu só quero tornar isso um pouco mais visual para todos vocês. Então, terminamos com os três. Então, vamos passar para os dois agora. Então, dois é igual a três? Isso não acontece. Essa é uma operação. Dois é igual a dois? Faz. Essa é uma operação. Dois é igual a dez? Isso não acontece. Essa é uma operação. Dois são iguais a Buffalo Isso não acontece. Essa é uma operação. E então vamos ver a lista mais uma vez. Dez é igual a três? Não tem? Essa é uma operação. Dez é igual a dois, não é? Essa é uma operação. Dez é igual a dez? Faz. Essa é uma operação. Dez é igual a Buffalo? Isso não acontece. Essa é uma operação. Faz Buffalo? Vou apenas abreviá-lo como B aqui, então não quero continuar escrevendo Buffalo é igual a três? Isso não acontece. Então essa é uma operação. Buffalo é igual a dois Isso não acontece. Então essa é uma operação. Buffalo é igual a dez? Isso não acontece. Então essa é uma operação. Buffalo é igual a Buffalo? Faz. Então essa é uma operação. E agora, se somarmos todas essas taxas aqui, o que vamos ver é que isso vai ser um, dois, três, quatro, cinco, seis, sete, oito, nove, dez, 11, 12, 13, 14, 15, 16. Então, nessa situação, nossa entrada foi quatro, mas nosso tempo de execução foi aproximadamente 16. E o que isso acaba sendo? Bem, isso acaba por ser quadrado. Então, vamos considerar que se pegássemos quatro e elevássemos ao quadrado, seria igual a 16 E podemos teoricamente pensar sobre isso também. Se expandirmos isso para cinco, teríamos não apenas mais cinco aqui, mas teríamos que multiplicá-lo porque agora também teríamos que verificar um adicional Então, em cada instância, teremos cinco e teremos outras cinco inteiras, o que equivale ao quadrado Então, nessa situação, nosso tempo de execução está ao quadrado E a razão para isso é embora tenhamos dois quatro loops, existe o que é conhecido como aninhamento Nós aninhamos um loop de quatro dentro de outro quatro loop. Então, essa parte aqui. Vamos desenhar isso em vermelho. Essa parte aqui está dentro. Embora essa parte interna também esteja dentro. Então, o que fazemos é absorver o que está do lado de fora. Nós multiplicamos pela entrada do lado de dentro e chegamos ao quadrado E esse será nosso tempo de execução final para essa situação. Então, como eu disse, este curso não é muito específico para escrever código ou superação, mas ainda assim define a teoria, mas achei que isso poderia ajudar a mostrar do que estamos falando esse tempo todo, como o código pode ser realmente analisado para que possamos entender essas E você pode ver que, não importa o que aconteça, acabamos de aprender algo muito importante. Sempre haverá quatro loops, mas quatro loops aninhados sempre existirão quantos aninhados existirem Então, se este aqui aninhasse um terceiro, essa seria uma fórmula de n ao quadrado, e você começa a formar números muito grandes para começar a verificar todas essas coisas Então, espero que esse exemplo prático ajudado você a entender esse conceito um pouco melhor. 7. Exemplo de estrutura de dados: Então, agora vamos discutir um exemplo um pouco mais concreto. E vamos discutir a diferença entre uma matriz e uma lista e como isso vai se relacionar com o que estamos aprendendo? E o que estamos aprendendo é escalabilidade, armazenamento de informações e como isso reage com o tempo de execução à medida que obtemos mais e mais Então, com esses dois exemplos aqui , analisaremos uma matriz e veremos uma lista e veremos seu acesso e adicionaremos aos tempos de retorno dessas matrizes Então, com isso, o que vamos ver é como isso se expande ao longo do tempo com essas duas maneiras diferentes de armazenar dados? Como podemos usar essa análise para descobrir qual solução gostaríamos de usar no futuro. Vamos dar uma olhada rápida. Vamos fazer uma visão geral do que essas estruturas de dados são, uma visão geral muito leve. Você não precisa saber muito de ciência da computação para acompanhar esta lição, mas será muito importante adicionar um elemento concreto ao que estamos aprendendo. Então, a primeira estrutura de dados que vamos examinar aqui é a matriz. Então, com uma matriz, o que estamos basicamente fazendo é pegar uma parte dos dados contínuos da nossa memória Agora, o processador basicamente nos dirá onde vamos pegar isso Pode ser a memória RAM , pode ser o cache. Pode ser o disco rígido. Isso não importa. Nesse caso, é a memória, e isso é tudo o que precisamos saber. Então, com a memória, basicamente, estamos separando toda a nossa memória em pequenos blocos de dados Quando pedimos ao processador uma matriz, ele encontra um pequeno pedaço de memória para nós. Isso é contínuo e pode se encaixar no que estamos solicitando. Nesse caso, estamos solicitando quatro dados aqui Portanto, é um tamanho de matriz de quatro. Agora, quando fazemos isso, estamos criando, é contínuo, mas por outro lado, não temos acesso a eles, que significa que, se precisarmos aumentar o tamanho dessa matriz, precisamos criar uma nova matriz e copiar coisas para ela. E essa será a desvantagem. Então, vamos examinar nossos dois aqui, nosso acesso e nosso anúncio. Então, sempre que estivermos acessando dados em uma matriz, o melhor é que eles serão em tempo constante, porque sempre que solicitamos isso, é contínuo. Portanto, podemos solicitar dados muito específicos aqui. Então, se precisarmos descobrir, se precisarmos pegar algo da segunda ou dessa posição, o terceiro lugar na matriz, que é indexado por dois Isso significa apenas que tudo na ciência da computação tem índice zero, então a primeira coluna é zero, não um. Podemos usar essa pequena taxa de fórmula aqui, que funciona basicamente em todas as linguagens de programação. Significa apenas pegar aquele elemento ali mesmo. Ele vai devolvê-lo para nós em tempo constante. Basicamente, exibirá o que está lá em tempo constante Poderíamos ter toneladas e toneladas de informações. Isso pode durar 2000. Isso pode ter 3.000 de comprimento. Isso poderia ser 20.000 $30.000 e assim por diante. E se colocarmos isso aqui, vamos recuperá-lo constantemente todas as vezes. E é isso que permite que nossa matriz tenha acesso ao pior cenário possível, em tempo constante. Sempre será constante. Agora, aqui está o problema. Lembra quando eu disse que, ao adicionar ao final disso, se atingirmos nosso limite de matriz, preenchemos a matriz, precisamos solicitar uma nova matriz, o que significa que o módulo de memória basicamente eliminará nossa matriz antiga e, em seguida, encontrará um conjunto maior no qual possamos colocar informações. Bem, para garantir que não percamos nossos dados antigos, temos que copiar cada peça. Mais de um de cada vez. Então, se temos 300.000, 3 milhões, 3 bilhões de entradas, todas elas precisam ser copiadas e cada dado aqui precisa ser E isso é muito, muito importante porque significa que , à medida que o tamanho da nossa matriz, à medida que o número de entradas que temos aumenta, o número de operações que precisamos usar também aumenta E aumenta de forma linear, o que significa que temos o pior cenário de O ao adicionar a uma matriz. Então, agora, cobrimos a matriz muito bem. Vamos dar uma olhada aqui em nossa outra estrutura de dados. A lista. A lista é interessante porque o que estamos fazendo com uma lista é basicamente acessar nossos dados aqui. Estamos solicitando isso. E, em vez de nos fornecer dados contínuos , basicamente nos fornece um elemento por vez. Então, podemos solicitar um, ele estará aqui. Solicitamos outro. Ele cria um ponteiro e depois vai para aquela peça. Queremos outro. Bem, vai passar por aqui, e assim por diante. E você pode ver que não há uma maneira realmente definida de fazer isso. Tenho certeza de que, você sabe, os módulos de memória avançados e tudo mais têm uma forma eficiente, mas não serão contínuos. Eles estarão em todo lugar da maneira mais eficiente que acharem melhor. Ou seja, se estamos tentando acessar nossas informações e queremos pegar essa informação aqui, bem, veja essa bagunça aqui Temos que seguir o ponto. Então, temos que começar aqui e ir aqui. Então aqui, depois aqui, depois aqui. E, Oh, aí está nosso dado. E isso significa que, quando acessamos nossos dados, se estamos tentando encontrar algo no final da lista, algo mais distante, e, você sabe, pode ser algo como um número, uma letra, uma frase, uma imagem, qualquer coisa Vamos colocar PE aqui. Para chegar a P, precisamos executar toda a lista vinculada para encontrá-la. Então, qual é o nosso tempo de acesso? Bem, isso não parece constante. Parece que, à medida que o número de elementos aumenta, nosso tempo de acesso também aumenta, que parece ser o acesso, na pior das hipóteses, seja, um tempo linear até a entrada. Agora, a lista tem a vantagem da matriz com a adição, desde que mantenhamos o que é conhecido como ponteiro para trás, que é essencialmente apenas um dado que atualizamos, de forma que seja uma seta direta para trás Então, se adicionarmos uma nova peça, basicamente pegamos aquela flecha e a movemos para a nova peça. Se mantivermos isso atualizado, o que é apenas uma única operação constante, bem, adicionar dados a isso é tempo constante. Sempre será exatamente a mesma operação. Apontamos para trás e adicionamos à próxima. Na verdade, neste caso, não temos. Sim, sim, temos. Então, temos o ponteiro traseiro aqui. Portanto, se precisarmos adicionar na parte de trás, seguimos o ponteiro de volta até o final da lista de links e, em seguida, adicionamos um novo elemento e atualizamos o ponteiro para o novo É uma operação constante. Mesmo que haja algumas etapas, sempre será a mesma coisa. Se houver 1 bilhão de peças ou uma peça, exatamente as mesmas coisas precisam acontecer. Seguimos o ponteiro traseiro, adicionamos um novo e depois colocamos nossos dados nele Então isso significa que nosso tempo de adição realmente sairá constante. Agora podemos ver que, com essas duas estruturas de dados, temos duas possibilidades diferentes de solução aqui. Se precisarmos de um tempo de acesso rápido, pense na lista em seu telefone, sua lista de contatos em seu telefone. Precisamos de um tempo de acesso rápido com isso. Você não quer encontrar alguém na lista de contatos e ter que esperar que ela pesquise todos os outros dados. Isso não parece nem um pouco eficiente. Isso seria bobagem. E não adicionamos nada a isso com muita frequência. Você sabe, adicionamos um contato aqui e ali, mas não é algo que adicionamos continuamente. Portanto, a matriz pode ser a melhor solução para esse problema específico. Agora, com uma lista, talvez tenhamos uma operação que precise armazenar muitos e muitos elementos ao longo do tempo, mas quase nunca precisa acessá-los. Portanto, precisamos de tempo constante, você sabe, adicionar tempo, mas na verdade não precisamos de muito tempo de acesso. Bem, então estaríamos analisando uma lista dessa solução. Então, o que estamos aprendendo nisso pode ser usado para descobrir melhores soluções para nossos problemas. E neste caso em particular, são problemas de armazenamento na programação de computadores. Mas isso pode se aplicar a outras áreas do mundo da computação e também à vida real. A solução que você tem é escalável. E com isso, podemos ver quais são e quais não são. 8. Projeto com vídeo: Agora que examinamos a notação, a intolerância e toda a escala que acontece O projeto aqui será pegar tudo o que você aprendeu e analisar algo em sua vida e nos dizer qual é o procedimento e, em seguida, qual é o cronograma. Então, isso pode estar relacionado à ciência da computação. Você pode criar um algoritmo, um algoritmo de busca ou pensar em, você sabe, como uma solicitação de amizade no Facebook pode funcionar ou algo parecido, mas também pode ser apenas observacional ao seu redor Pode ser como eu disse no início do curso, como um arquivo ou como alguém pode se juntar a um membro da sua organização ou como você pode pesquisar e encontrar algo em um grande conjunto de dados ou em um grupo de pessoas ou qualquer coisa dessa natureza Eu quero que você seja criativo e apenas analise o mundo ao seu redor com o conhecimento que você aprendeu e compartilhe. É um exercício muito divertido, e é muito legal ver que basicamente o que estamos fazendo é apenas matemática aplicada sempre que estamos programando ou trabalhando com esse tipo de teoria da matemática em si Se estamos aplicando isso, estamos aprendendo como o mundo funciona e opera e, em seguida, estamos interagindo com ele. E é disso que trata este projeto. Para criar um pensamento crítico e depois analisá-lo e reforçar o que aprendemos Estou muito empolgada em ver o que todos inventam e estarei na seção de projetos respondendo a eles. Então, pronto, obrigado a todos por participarem deste curso.