[MÚSICA] Vamos agora então conversar pouco sobre complexidade computacional, que é, na verdade, conversar se os algoritmos, os programas que estamos escrevendo, se eles são eficientes, se eles são rápidos, ou não. No vídeo passado a gente viu uma busca sequencial, que, dado que se tem uma lista, normalmente vai ser uma lista muito grande, com muitos elementos, a gente quer percorrer todos os elementos da lista para definir se determinado elemento está lá dentro ou não. Se determinado valor ou número, uma música, dependendo do tipo de objeto que está sendo guardado nessa lista. E essa busca sequencial, ela funciona dessa forma que vocês estão vendo aqui, percorrendo todos os elementos para ver, se encontrar devolve imediatamente dizendo que encontrou, caso contrário, se chega até ao final e não encontrou, ele devolve falso. Então, vamos falar sobre a complexidade computacional deste algoritmo de busca. A complexidade computacional é uma análise matemática que a gente faz do desempenho de determinado algoritmo. Nós refletimos utilizando mecanismos, ferramentas matemáticas sobre determinada natureza de determinado algoritmo. Então, a gente pode dizer que é estudo analítico de quantas operações determinado algoritmo requer para que ele seja executado, ou quanto tempo vai demorar para executar esse algoritmo. Às vezes a gente quer saber também quanta memória esse algoritmo vai ocupar, porque às vezes o algoritmo é rápido mas gasta muita memória. Ou tem algoritmos que gastam pouca memória mas eles são mais lentos, então, a gente quer estudar essas grandezas. Vamos analisar então a busca sequencial que a gente viu, mas eu quero pensar num exemplo, vamos supor, a lista telefônica da cidade de São Paulo. Supor que a gente quer buscar entre, supondo que a cidade tem dois milhões de telefones fixos, eu dou o nome de uma pessoa e você tem que me dar o telefone dessa pessoa, ou dizer que não encontrou o telefone. Então, usando busca sequencial, a gente teria uma lista de dois milhões de registros, cada registro vai ter o nome da pessoa, o telefone da pessoa, eventualmente pode ter o endereço também, alguma outra informação sobre a pessoa. E usando busca sequencial a gente vai ter que, de percorrendo esses dois milhões de elementos, até encontrar o nome da pessoa ali, comparando, fazendo comparação de string, o string do nome que a gente dá com o nome das duas milhões de pessoas que estão naquela lista. Então, vamos supor que cada interação do for ali do algoritmo de busca que tem que fazer essa comparação de string pelo nome da pessoa, vamos supor que dure milissegundo, que o nosso computador consiga fazer uma interação do for com a comparação de strings milissegundo. Nesse caso, qual seria no pior caso, o desempenho ou complexidade aí do nosso algoritmo? Se a gente pensar, o pior caso seria a gente procurar por alguém que não está na lista telefônica, ou alguém que é o último nome da lista, Zarzur Zu Zu Zu com bastante Z, que é o último nome da lista telefônica, daí, para encontrar esse último nome, a gente precisa percorrer dois milhões de registros, fazer duas milhões de comparações de strings. Se cada uma demora milissegundo, a gente consegue fazer mil por segundo, então, a gente vai demorar dois mil segundos no pior caso, que é 33,3 minutos para encontrar, no pior caso, alguém nessa lista telefônica. Agora, o pior caso geral é muito ruim, a gente muitas vezes quer saber qual é o caso médio de execução de determinado algoritmo. É muito mais útil saber o caso médio do que o pior caso. Aqui na busca sequencial, o caso médio, se a gente pensar que os nomes ali estão distribuídos aleatoriamente nessa sequência, no melhor caso de todos você acha o elemento na primeira vez, na primeira comparação de string. No pior caso, você acha na última. Nos outros casos intermediários, para cada nome você vai achar na segunda, o nome que está na segunda posição, você vai achar na segunda, o nome que está na terceira, você vai achar na terceira. Então, a média, você tem que fazer uma média de dois, três, quatro, cinco, seis, até dois milhões. Mas a média disso vai ser o número do meio ali da lista. Então, a gente pode dizer que na média, se a gente fizer uma busca por todos os nomes que estão lá, na média a gente vai demorar milhão, vai ter que olhar milhão, que é bem o meio da lista, a lista tem dois milhões, o meio é no milhão. Na média a gente vai ter que fazer milhão de comparações de string para encontrar o nome que a gente está procurando. Então, no caso médio, se é milhão de comparações que a gente tem que fazer, e cada vai demorar milissegundo, então a gente precisa de mil segundos, que é dezesseis minutos, que é número muito grande, alguém aguenta esperar dezesseis minutos para achar número na lista telefônica? Não, não aguenta, então a nossa busca sequencial está com algum problema aí. Que é que é? Vamos pensar então nessa complexidade computacional na busca sequencial. Vamos pensar termos genéricos. A gente vê exemplo concreto, vamos agora termos genéricos, dada uma lista de tamanho n qualquer, a complexidade computacional da busca sequencial vai ser n no pior caso, eu vou precisar fazer n operações para encontrar, e no caso médio vai ser n sobre dois. Então essa é a complexidade, falando termos abstratos da busca sequencial. Qual é a conclusão? A busca sequencial, ela é boa porque ela é bem simples, três linhas quase que a gente implementa a busca sequencial, é muito fácil de entender, vocês entenderam rapidamente. Mas ela funciona bem quando a busca é feita num volume muito pequeno de dados, a gente fez esse exercício mental de pensar na lista telefônica de São Paulo com dois milhões de elementos. A busca sequencial não atende esse caso, não funciona. Ninguém vai esperar dezesseis minutos para encontrar alguém na lista telefônica. Não dá certo. Então, a complexidade computacional é muito alta, esse negócio de você ter complexidade n ou n sobre dois no caso médio, não é bom nesse caso. Ela é muito lenta quando o volume de dados é grande, portanto, dizemos que esse é algoritmo ineficiente, a busca sequencial é algoritmo ineficiente para volume de dados médio ou grande. Você só vai usar esse tipo de coisa quando o volume de dados é muito pequeno. Então, nós precisaremos de algoritmos mais eficientes e a gente vai estudar aqui nas próximas aulas, algoritmo mais eficiente para isso. Obrigado. [MÚSICA] [MÚSICA] [MÚSICA]
