[Música] muito bom vamos lá então terceira parte né da nossa conversa aqui sobre algoritmos e programação então o que que a gente viu na aula 1 na aula 1 a gente viu definição de algoritmos formas de representação de algoritmos né na aula 2 a gente estudou uma aula importantíssima né as estruturas de controle de algoritmos então existem outras né a gente viu as principais e agora a gente vai adentrar avançar essa discussão falando algumas coisas um pouquinho mais vamos dizer assim sofisticadas vamos dizer tá bom a gente vai falar um pouquinho de qualidade de algoritmos
um pouquinho de eficiência de algoritmos Tá bom então a gente vai falar um Pouquinho bem pouquinho né de estratégias de busca e ordenação eficiência né busca ordenação busca linear busca linear e comparar Então o meu programa funciona tá bom não sei se tá bom Depende de quanto tempo ele leva para executar alguma coisa Puxa mas o computador é tão rápido o tempo é importante é importante sabe porque porque você pode estar processando milhões de dados E aí Mesmo ele sendo muito rápido esse processamento pode demorar muito tá legal então vamos lá o que que a
qualidade no sentido da eficiência de um algoritmo né é análise de algoritmos que é uma é uma outra disciplina mas que eu acho que vale a pena trazer para cá ela tem o objetivo de estudar o desempenho proporcional ao tempo de execução de um algoritmo envolve facilidade de compreensão codificação depuração que é uma forma de correção né e eficiência dos recursos do computador Poxa isso é bem bacana viu se você pensar bem quase tudo que fazemos em termos de computação é busca em uma lista ou ordenação de elementos em uma lista Aí é uma coisa
um pouquinho sofisticada né mas eu acho que você consegue entender se você parar e pensar um pouquinho puxa eu tô buscando eu tô comparando eu estou executando mas no fundo no fundo eu tô buscando e classificando o computador é uma máquina Fabulosa para buscar informação e para classificará-la quase tudo que a gente faz é em termos computacionais é busca e classificação isso é muito interessante tá a medida que você avançar no curso você vai entender melhor então vamos olhar um pouquinho para essa história de busca e comparação né e métodos de busca então aqui tá
é o seguinte eu tenho uma lista de valores Tá bom vou pedir para você abrir a mente assim não se assustar a gente tá fazendo exercício de abstração Tá certo não vou entrar no mérito de como é que os números estão armazenados como é que eles vão ser manipulados nada disso eu só queria dizer para você o seguinte eu tenho uma lista de elementos eu vou buscar um elemento nessa lista Tá bom pode ser que o elemento exista Pode ser que ele não exista essa busca é quando ela visita todas as posições de memória ela
é chamada de busca sequencial então a busca sequencial é o algoritmo simples de entender porém pouco eficiente né porque se a lista for grande para saber se existe ou não elemento dentro dela eu vou ter que varrer toda a lista vamos ver um exemplo aqui eu tenho aqui um vetor né uma lista com 234 é 67 pararam uma série de números eu vou buscar o número 54 tá na primeira posição não vou avançar tá na segunda posição não está na terceira posição não está na quarta posição não está na quinta posição ou na posição quatro
né se a gente começar do zero que nem Aqui começou do zero até a posição 4 está na posição quatro está Opa Esse é o valor que eu queria Então a busca sequencial ela é muito assim simples evidencia o método muita clareza né Fácil de programar Mas ela é problemática Porque se você tiver uma lista muito grande de elementos Puxa você corre o risco de ter que visitar o último ou visitar a lista inteira para dizer que o número não existe a outros métodos de busca diferentes da busca sequencial que não é muito eficiente tá
bom outro desempenho aqui né na verdade é o mesmo do anterior que reforçando né fui comparando não achei fui para o próximo comparei não achei foi para o próximo compa fui para o próximo que eu falei não achei fui para o próximo comparei achei aí eu paro de executar Mas pode ser que eu não parasse né Poderia acontecer bom como é que funciona a busca binária a busca binária ela funciona assim ela a lista tem que estar ordenado só funciona com isso ordenado eles têm que estar classificados em ordem crescente ou decrescente né E aí
você vou buscar um número que que eu faço eu comparo com do Meio você tá procurando um determinado número ele é menor do que o número do meio eu não vou me preocupar com a metade acima do meio da lista Você concorda se eu tô procurando um número e ele está acima do número do meio da lista eu descarto os números que estão abaixo do elemento do meio da lista Então ela é muito rápida né eu vou muito rápido encontrar o elemento ou chegar à conclusão de que o elemento não existe Então veja que interessante
né busca sequencial linear é busca todos os elementos busca binária eu vou eliminando grandes pedaços da lista né A medida que eu comparo com elemento do meio de uma lista restante então por exemplo nesse caso aqui eu comparei com elemento do meio a ele é menor descarto tudo que tá direito vou comparar só com a lista da esquerda comparado com elemento do meio Ah ele é maior descarta tudo que está escrito agora eu vou andar aqui até chegar no elemento que eu tô procurando Ah mas e se eu tiver o número par de elementos bom
aí você convenciona qual que é o do meio né Então essa é a brincadeira quando a gente conversa sobre busca binária até que um outro exemplinho né vou buscar os 54 eles estão ordenados aqui é 24 54 Eles não estão ordenados Opa Então esse exemplo aqui nem faz muito sentido mas foi bom colocar para lembrar do seguinte busca binária só funciona em sequência ordenada portanto não dá para executar busca binária nesse caso né Vamos lá comparando as estratégias de busca qualidade dos métodos né ou até dos algoritmos se a lista não está ordenada busca binária
funciona a busca binária só vale para isso ordenado busque a sequencial é muito ineficiente para conjunto grandes de valores costuma-se dizer que busca sequencial tem complexidade n que é o tamanho da lista n elementos né No pior caso vou ter que visitar todo mundo e a busca binária tem complexidade log n ou seja ela é uma um método que cresce uma cresce cada vez mais devagar como uma função logarítmica né então se você comparar o gráfico de um logaritmo uma função logaritmo ele inicialmente cresce muito rápido depois ele começa a crescer bem devagarzinho logo de
100 é 10 logo de mil é três Olha só logo de 10 é um né logo de 100 a dois logo de mil é três puxa o número gigantesco 10 100 mil e o y vai para um dois três cada vez mais devagar agora busca linear é uma é um gráfico linear então no começo se você vamos riscar aqui a busca linear no começo até um certo n a busca binária pode ser até mais custosa né a partir de um certo ponto a busca linear custa mais quanto mais rápido cresce essa curva maior o meu
custo computacional dá para ter uma ideia assim um pouquinho de eficiência de algoritmos isso é super importante e eu achei legal trazer para você logo no começo embora esse assunto não esteja discutido diretamente no material tá bom isso vale a pena para você pelo menos considerar o seguinte não é porque o programa funciona que ele que ele é eficiente que ele é interessante que ele pode ser aplicado né preciso buscar melhorias e verificar se eu não consigo melhorar o meu algoritmo tá bom isso que eu queria dizer para você bom eficiência de algoritmos é muito
importante quando a gente tem muitos dados da processar tá então no mundo bem comportado né com n pequeno Beleza você pode fazer do jeito que você quiser desde que funcione Mas se você tiver o número grande de elementos para serem processados e não em nenhum n2 N3 N1 n2 Não não são três quatro elementos são milhares centenas de milhares aí a brincadeira fica um pouco diferente tá bom eu queria trazer isso para você para valorizar esse momento de Introdução ao Estudo de algoritmos tá bom Por enquanto é isso a gente se encontra de novo na
próxima aula tá lá
