COMPLEXIDADE de ALGORITMOS I - Noção INTUITIVA

pagas sejam bem vindos ao país um café solução país neste vídeo vou te ensinar sobre o conceito muito importante para analisarmos a eficiência dos nossos programas esse conceito se chama complexidade embora não esteja bem estranho e no gmail a idéia de complexo que nos associamos a dificuldade e não é uma idéia tão difícil assim de ser compreendida de todo modo eu vou explicar o que a gente precisa saber em dois vídeos nesse primeiro vídeo vou abordar uma noção intuitiva do que a complexidade enquanto no vídeo seguinte eu vou dar uma nota são matemática de que

nós utilizamos para expressar a beleza mas eu tinha começar gostaria de convidar você ainda não se inscreveu no canal a se inscrever não esqueça de levar o cinema para receber notificações de vídeos novos também pode curtir a página para um café no facebook além é claro de conferir os artigos que escrevi um site para um café no último vídeo eu te falei sobre os recursos que nós gerenciamos quando programamos se você não se lembra surgiu da mulher no vídeo recursos computacionais aqui no canal lá tem tudo explicadinho basicamente que nós vimos foi que os nossos

programas exigem dois tipos de recursos do nosso computador o primeiro deles é o processamento capacidade de realizar cálculos do computador e o segundo é a capacidade de armazenamento em memória do computador está tendo essa noção bem praia nós vamos voltar nossa atenção neste momento para tentar calcular de uma maneira bem grosseiros bem aproximada a quantidade de recursos demanda do nosso programa e aí nesse contexto nós utilizaremos o termo complexidade para nos referirmos exatamente essa quantidade de recursos que é demandado até o momento utiliza de uma maneira bem informal o termo programa vai me referia tudo

aquilo que nós temos escrito e executado por aqui mas a partir de agora eu vou utilizar o termo algoritmo quando foi adequado programa algoritmo não são a mesma coisa nós poderíamos entrar numa discussão até razoavelmente longa para tentar definir com precisão quais são essas diferenças nesse momento não vou te dar uma definição precisa das diferenças entre um programa com um algoritmo mas os exemplos que vou te apresentar fonte da instituição nesse saiba que você assine e aquilo que é importante beleza então vamos analisar um exemplo de um algoritmo aqui bem simples está curto para que

nós possamos entender como é que vamos calcular complexidade aqui nós temos um algoritmo que inverte uma lista ou seja um elemento da lista para pagar seu último eo último será o primeiro o segundo elemento será o penúltimo eo último será o segundo e assim sucessivamente neste momento não importa que isto é essa será uma lista de números maiores de stream ou qualquer outro tipo de alimento também não nos importa da onde veio essa lista se o usuário de todos elementos se nós vemos cada um dos elementos de um arquivo csv da internet na hora de

nos importa pois esses aspectos são específicos do programa que utiliza esse é o ritmo tá certo então nós vamos começar calculando a quantidade de memória que esse algoritmo exige no computador se você se lembra do vídeo anterior sobre recursos computacionais deve ter lembrado que a idéia de memória está muito associada à variáveis aos valores que nós vemos no programa de uma maneira geral vamos começar contando isso tá nós temos aqui uma duas três quatro cinco variáveis contando a lista certo não tem tamanho limite e alx lista cinco aliados contudo a lista é uma variável que

tem vários valores dentro delas é certa ela tem um tamanho que nós vamos referir como n ta ela tem elementos são e nem valores então aqui nós temos a exigência de 4 mas n valores em memória certo aí você vai me dizer puxa água mas nós temos um forte aqui na linha 7 que vai rodar mais vezes essas três linhas de código aqui dentro e uma delas cria a variável alx al x isso vai aumentar a quantidade de memória que nosso programa exige não não vai aumentar que repara que nós estamos reaproveitando a mesma variável

colocar novos valores então nós abrimos mão do valor antigo que tem na integração antiga do do audax e ficamos apenas com um valor mais recente então isso não vai aumentar a quantidade de memória que nós que exige tá só existe uma variável ao psa em cada interação tá nós vamos com cálculo da quantidade de memória que esse algoritmo demanda do computador e agora nós vamos ver como calcular a quantidade de processamento e essa parte é um pouco mais delicada porque se você se lembra do vídeo recursos computacionais lá uma das três coisas que eu pedi

que você gravar se é que uma linha de código pode na verdade é gerar várias operações está mais de uma operação que o computador tem que executar se nós formos contar cada uma dessas operações primeiro nós precisaríamos ter um conhecimento mais aprofundado sobre a arquitetura de computadores e microprocessadores porque nós não temos em segundo nós chegaremos no final nós iremos perceber que essas operações elas não são tão relevantes para entendermos a eficiência de um algoritmo tá certa então o tipo de conta que nós vamos fazer é mais aproximadas e mais gols e nós vamos contar

operações elementares que vai ser uma operação elementar pra gente mas é uma operação que tem o número de passos constantes que ela não esconde um outro algoritmo então que seja um exemplo de pensão alimentar olha aqui por exemplo na linha 9 ea linha 9 ela já era pra gente vários passos porque primeiro nós temos que fazer essa subtração dn - e está a tomar um chocolate esse resultado da bn - pagar o ir vai dar resultado dá um valor e nós vamos pegar esse valor vamos utilizar ele pra ir lá na variável está aqui é

uma lista e olharmos a posição correspondente a esse resultado olhamos vamos recuperar com o valor que está lá naquele endereço de memória e vamos atribuir a outra posição a iese uma posição da lista você tem pelo menos três operações aqui uma subtração depois buscamos recuperamos uma ou e finalmente a tribo desse valor há outro espaço pelo menos três operações estão sendo executadas porém independente do tamanho da lista sejam sempre três operações há uma quantidade constante de passos então essa linha aqui pra gente vai contar como uma única operação elementar então vamos contar a quantidade de

operações mentais que nós temos nesse ritmo de inverter isto então nós temos aqui uma duas e depois três tá então cada linha dessa aqui está sendo uma obrigação alimentar mas repare que essas três aqui elas sejam executadas várias vezes são executados quantas vezes o limite vezes que é o que está aqui no fórum pra gente limite é igual tamanho da lista sobre dois então na verdade nós temos duas operações alimentares que estão aqui fora do foco e depois três vezes o limite tá nós sabemos que o limite é n sobre dois e que n é

o tamanho da lista então essa aqui é a nossa complexidade olhando para o processamento e aqui de cima quando a gente conta memória a quantidade de memória necessária pra execução do programa chamamos de complexidade de espaço tá então apagar a memória no colocar a complexidade de espaço ea quantidade de processamento necessário para a execução do nosso programa chama de complexidade de tempo então é a complexidade de processamento embora já esteja contando operações também na conversão de operações com a quantidade de operações nós conseguimos ter uma noção do tempo que vai ver que vai levar pra

esse algoritmo executar e pra nós seres humanos é muito mais importante saber a quantidade de tempo já tem uma noção de tempo do que ter uma noção de de operações então o computador realiza milhões as operações por segundo e pra gente é muito mais relevante saber se esse é o ritmo vai rodar num tempo razoável que estou disposto a esperar ou não tá certo ela presta atenção que há três coisas muito importante eu quero que você repare a primeira delas é que as duas expressões que nós calculamos tanto com a complexidade de tempo quanto para

o espaço elas dependem do tamanho da lista já então em todas elas apareceu e se n zinho aqui que é o tamanho da lista essa lista que entrou na lista que nós colocamos como argumento como parâmetro da função é chamada de entrada do algoritmo ea lista invertida ou seja o resultado que foi calculado ele é a saída do ritmo então esses temas também são importantes mas nós vamos votar nele está o foco é o as expressões elas dependiam um tamanho da lista a segunda coisa que você deve reparar é que as contas que nós fizemos

a versão bem grosseiros bem aproximado está então no caso da complexidade de tempo nós deixamos de contar várias pequenas operações que poderiam estar escondidos ali por trás de cada linha no caso da complexidade de espaço nós desconsideramos do tipo das variáveis né então uma variável um valor como o número sete é número inteiro sete e ocupa um espaço bem diferente provavelmente muito menor do que uma string e como se você gostou do vídeo deixa o seu lic tá certo mas na próximo vídeo no próximo vídeo seguinte sobre complexidade eu vou te dar uma fórmula matemática

que explica por que nós podemos fazer as contas dessa maneira ok a terceira coisa para você repare é que quando nós temos complexidade tempo de complexidade espaço mas quando foi a complexidade sem me referir a tempo ou espaço você deve entender a complexidade de tempo porque vão precisar de espaço ela também é importante mas na maioria dos casos mas a complexidade de tempo que vai nos dizer se uma solução determinado algoritmo é viável ou não assim vai executar em um tempo que não achamos razoável que estamos dispostos a esperar ou não ou sim vai executar

um tempo que pode ser inclusive superior às nossas vidas pode ser milhões de anos bilhões de anos tá certo então se você é iniciante na computação pode ser difícil de crer que que há programas algoritmos que vão demorar tanto a executar mas nós vamos acabar vendo alguns deles daqui a pouco conselho de complexidade é muito importante para analisarmos o comportamento do algoritmo nós vamos nos preocupar em entender como é complexidade muda com o tamanho da entrada no nosso caso concreto nós vimos que a complexidade é linear com o tamanho da lista porque ganhar se nós

olharmos a complexidade de tempo por exemplo nós temos dois mais três vezes ele sobre dois isso tem a cara de uma função do primeiro grau se nós passarmos o gráfico dessa dessa função utilizando o enem como essa variável nós julgamos que ela é uma reta o gráfico de uma reta o resultado ideal é o melhor que nós conseguimos obter para esse caso pois para inverter uma lista nós precisamos no mínimo conhecer cada um dos seus elementos vamos ter que executar pelo menos ele passos um para cada elemento eu escrevi aqui uma outra solução para esse

mesmo problema pra gente dar uma analisada então aqui magicamente eu escrever função inverter lista dois então nesse caso eu estou criando aqui uma nova lista e adicionando os elementos da lista de entrada na ordem inversa tá eu retorno essa lista aqui de saída então nesse caso nós temos como complexidade de tempo 22 operações aqui mais uma que se repete tamanho vezes e aqui tamanho realmente o tamanho da lista n toda essa complexidade de tempo é essa que dois mais n repare que na sua complexidade de espaço ela aumentou porque nesse caso nós não estamos aproveitando

o próprio espaço da lista de entradas não estamos criando uma nova lista a saída então em algum momento nosso programa vamos ter duas listas de tamanho n então a complexidade de espaço aqui em linguagem que esteja utilizando menos variáveis né porque essa variável ao x ela não existe aqui vai aumentar a quantidade de valores presentes dentro do organismo tá nesse caso a quantidade de recursos continua dependendo de energia maneira linear nas duas soluções mas nós vamos ver exemplos de alguns problemas mais à frente em que esse tipo de comportamento não é o comportamento da complexidade

de tempo ou espaço vai variar bastante e aí nós vamos conseguir identificar algoritmos que são mais ou menos eficiente tá certo em que o ritmo vai ser mais eficiente se consegue fazer resolver o mesmo problema com uma quantidade de recursos menor dito isso tudo vou resumir para você o que deve ser absorvido duas coisas que você não pode encerrar esse vídeo sem saber a primeira delas é que complexidade é uma medida da quantidade de recursos que são demandadas por um algoritmo nós podemos falar em complexidade de tempo ou complexidade de espaço a segunda coisa que

você deve absorver é que para calcular complexidade nós iremos fazer contas que são pouco detalhados não parecer pouco detalhadas ou até mesmo ou seja porque porque o nosso interesse não é no número exato mas sim entender como que a complexidade varia com o tamanho da entrada no ritmo do bairro vai ficando por aqui e espero que você tenha entendido a idéia por trás do concelho e complexidade no próximo vídeo e apresentar mais detalhes sobre esse conceito e também uma anotação matemática que utilizaremos para representar os valores de complexidade se você gostou do vídeo não esqueça

de deixar o seu líquido nem se inscrever no canal para dar aquele apoio ao trabalho dúvidas sugestões são sempre bem-vindos aqui nos comentários muito obrigado e até a próxima