CS50CS50x em Português - Aula 3 - Algoritmos
CS50
Introdução aos algoritmos de ordenação e busca 2:13
A aula começa retomando a ideia da Semana 0 de que um algoritmo é apenas uma sequência de instruções passo a passo para resolver um problema. O foco do dia são os algoritmos de ordenação, que organizam informações do menor para o maior, alfabeticamente ou por outro critério, e os algoritmos de busca, que procuram informações dentro de um conjunto de dados. O objetivo é mostrar modelos mentais que ajudam a traduzir problemas do mundo real em soluções que um computador pode executar.
A demonstração da contagem na sala 3:01
Para ilustrar diferentes velocidades de algoritmos, o professor propõe contar as pessoas presentes de três formas. Primeiro, contando uma a uma, depois de dois em dois, e por fim usando um método de dividir e conquistar: cada pessoa pensa no número um, forma dupla com outra, soma os valores e uma delas se senta, repetindo o processo até restar pouca gente de pé. O resultado final do método rápido aponta 141 pessoas, enquanto a contagem manual de Kelly chega a cerca de 160, mostrando uma pequena diferença atribuída a erros de execução, mas evidenciando que o terceiro método deveria ser, em teoria, muito mais veloz.
Crescimento linear versus divisão do problema 8:31
Analisando os três métodos de contagem, o professor mostra que contar um a um ou de dois em dois gera uma relação linear entre o tamanho do problema e o tempo necessário, ou seja, cada pessoa extra exige mais um passo. Já o terceiro método, que divide o grupo repetidamente pela metade, cresce muito mais lentamente: dobrar o número de pessoas exige apenas mais um passo, e quadruplicar exige apenas dois passos adicionais. Essa comparação retoma a ideia da lista telefônica da Semana 0 e introduz a noção de que o desenho de um algoritmo determina quão rapidamente seu custo, seja tempo, dinheiro ou espaço de armazenamento, aumenta com o tamanho do problema.
Arrays como blocos de memória 11:02
O professor revisita o conceito de array como um bloco de memória onde valores ficam armazenados um atrás do outro, em posições contíguas. Diferente da visão humana, que enxerga tudo de uma vez, o computador só pode acessar uma posição por vez, como se precisasse abrir e fechar portas de armários individualmente. A partir daqui a numeração das posições passa a começar do zero, então um array de sete elementos vai do índice zero ao índice seis.
Demonstração com armários e dinheiro de Banco Imobiliário 14:01
Usando sete armários com notas de dinheiro de Banco Imobiliário escondidas, dois voluntários buscam a nota de cinquenta dólares. José tenta uma busca linear, abrindo cada porta da esquerda para a direita até encontrar o valor no último armário, mostrando que esse método funciona mas pode ser lento. Caitlin, com os números já ordenados por Kelly, aplica uma busca binária, começando pelo armário do meio e descartando metade do problema a cada tentativa, encontrando o cinquenta com muito menos passos.
Pseudocódigo da busca linear e da busca binária 19:31
O professor formaliza os dois métodos em pseudocódigo. Na busca linear, o algoritmo percorre cada porta da esquerda para a direita e retorna verdadeiro se encontrar o valor, ou falso ao final se não encontrar, destacando que usar um else incorretamente faria o algoritmo parar cedo demais e dar uma resposta errada. Na busca binária, o algoritmo verifica o elemento do meio do array e, dependendo se o valor procurado é menor ou maior, repete a busca apenas na metade esquerda ou direita, sempre excluindo o elemento do meio já verificado, além de prever o caso de não haver mais portas para checar, retornando falso imediatamente.
Comparando algoritmos pelo tempo de execução 27:01
A partir de comparações visuais entre os algoritmos vistos antes, o professor mostra que a lista telefônica da semana 0 e a chamada de presença levam n passos no pior caso, o segundo algoritmo leva n dividido por 2, e o terceiro leva log base 2 de n. Esse último valor representa quantas vezes é possível dividir um problema de tamanho n pela metade até sobrar apenas um elemento, como uma pessoa em pé ou uma página de lista telefônica.
A notação Big O e seus termos dominantes 28:32
Em vez de contar passos com precisão matemática, os cientistas da computação preferem falar em ordem de grandeza usando a notação Big O, escrita como um grande O seguido de parênteses. Assim, busca linear fica em Big O de n, um algoritmo que divide pela metade fica em Big O de n sobre 2, e outro fica em Big O de log n. Como o que importa é como o tempo cresce quando o problema cresce muito, termos de ordem inferior são ignorados e conta apenas o termo dominante, já que ao ampliar a escala do gráfico até bilhões, curvas com a mesma natureza acabam parecendo praticamente idênticas.
Limite superior, limite inferior e teta 37:00
Big O descreve o pior caso possível, ou seja, um limite superior de passos. Já o símbolo ômega descreve o limite inferior, o melhor caso possível: tanto a busca linear quanto a busca binária podem ter sorte e levar apenas 1 passo, então ambas ficam em ômega de 1. Quando o limite superior e o inferior coincidem, usa-se o símbolo teta maiúsculo, que transmite mais informação de uma só vez. Esses três símbolos formam o que se chama de notação assintótica, usada para descrever como um valor cresce à medida que n se torna muito grande.
Ordenar antes de buscar nem sempre compensa 37:00
A busca binária só funciona corretamente em dados já ordenados, porque suas decisões de ir para a esquerda ou para a direita dependem de comparações de maior e menor que só fazem sentido nesse contexto. Ordenar os dados antes tem um custo, e se a busca for feita apenas uma vez, pode não valer a pena pagar esse custo, sendo mais eficiente simplesmente usar busca linear. Empresas como o Google, que fazem buscas repetidas vezes, conseguem diluir o custo de ordenar os dados ao longo de muitas pesquisas, enquanto em outras situações, como às vezes acontecia na pós-graduação do professor, pode ser mais prático rodar um código simples e ineficiente durante a noite, mesmo correndo o risco de perder tempo caso haja um erro.
Implementando busca linear em C 38:32
No VS Code, um programa chamado search.c é criado com um array de números fixos e uma chamada a get_int para perguntar ao usuário qual número procurar; um loop for percorre o array comparando cada posição ao valor buscado, imprimindo found ou not found conforme o resultado. Ao adaptar o mesmo código para comparar strings, como peças do jogo de Banco Imobiliário, o uso do sinal de igualdade duplo falha, porque comparar strings exige checar caractere por caractere. A solução é usar a função strcmp da biblioteca string.h, que retorna 0 quando as strings são iguais, e um valor positivo ou negativo quando são diferentes, informação que também serve para ordenar as strings, já que a comparação segue os valores ASCII dos caracteres.
Construindo uma lista telefônica em C 50:00
Para aproximar o exemplo do problema original da semana 0, o professor cria um novo arquivo chamado phonebook.c, com um array de nomes contendo Kelly, David e John Harvard, e um array paralelo de números de telefone. Os números de telefone são declarados como strings, e não como inteiros, porque contêm caracteres que não são dígitos, como sinais de mais, traços e parênteses, além de números como o de Seguro Social nos Estados Unidos apresentarem o mesmo problema; usar inteiros também apagaria zeros à esquerda, necessários em certos formatos de discagem local em outros países.
Busca linear numa agenda telefônica 52:33
O professor implementa uma busca por nome usando a função strcmp para comparar strings, percorrendo dois arrays paralelos, um de nomes e outro de números, da esquerda para a direita. Quando o nome digitado pelo usuário coincide com um nome do array na posição i, o programa imprime o número armazenado na mesma posição i do outro array. Essa é chamada de busca linear, porque percorre os dados em ordem sem exigir que estejam classificados, e o exemplo funciona corretamente ao procurar por John.
O problema de usar dois arrays separados 55:30
Apesar de funcionar, essa solução depende de um sistema de honra, já que os dois arrays precisam ter exatamente o mesmo comprimento e a mesma ordem para que o nome na posição i corresponda ao número na posição i. Isso é aceitável com três pessoas, mas se torna arriscado com trinta, trezentas ou milhões de registros, porque nada impede que os arrays se desalinhem. O professor observa que boa parte da programação consiste justamente em não confiar ingenuamente que tudo vai permanecer sincronizado, mas sim programar de forma defensiva e agrupar dados relacionados de maneira mais coesa.
Criando o tipo struct person 58:00
Para resolver isso, é apresentada a palavra-chave typedef struct, que permite inventar um novo tipo de dado em C combinando vários campos, neste caso uma string name e uma string number, agrupados sob o nome person. Com isso é possível declarar um único array chamado people, onde cada posição guarda uma pessoa completa com seu nome e seu número juntos, acessados por meio da notação de ponto, como people[0].name. O programa é reescrito usando esse novo tipo, preenchendo manualmente os dados de Kelly, David e John Harvard, e a busca volta a funcionar corretamente ao procurar John, agora com os dados encapsulados de forma mais organizada, como armários que guardam junto tudo o que pertence a uma mesma pessoa.
O próximo desafio: ordenar dados 1:02:32
Antes de seguir, o professor lembra que a busca binária, embora mais rápida, só funciona se os dados já estiverem classificados, o que levanta a questão de quanto custa, em tempo ou recursos, ordenar dados antes de buscar neles. O novo problema proposto é, dado um conjunto de números fora de ordem, como 7, 2, 5, 4, 1, 6, 0, 3, produzir esses mesmos números em ordem crescente, de 0 a 7.
Demonstração com voluntários no palco 1:04:00
Oito voluntários sobem ao palco representando números fora de ordem e primeiro se organizam de forma intuitiva, sem seguir um método formal. Em seguida, o professor demonstra dois algoritmos passo a passo: o selection sort, que a cada passagem procura o menor elemento restante e o troca para a posição correta, resolvendo um problema por vez; e o bubble sort, que compara pares vizinhos e troca os fora de ordem, fazendo os maiores valores subirem gradualmente até o final da lista a cada passagem completa.
Pseudocódigo e custo do selection sort 1:12:32
O selection sort é formalizado em pseudocódigo, percorrendo o array da posição i até n-1 para encontrar o menor valor e trocá-lo para a posição i, repetindo isso enquanto i avança. O professor explica que esse método usa pouca memória, apenas uma variável para guardar o menor valor encontrado a cada rodada, mas exige refazer comparações repetidamente. Contando o número de comparações, chega-se à soma n-1 mais n-2 e assim por diante, que equivale a n vezes n-1 dividido por 2, ou seja, da ordem de n ao quadrado, o termo que domina o tempo de execução quando n é muito grande, segundo a notação O-grande.
Selection sort e seu limite inferior 1:18:02
O selection sort, quando analisado com cuidado, fica na ordem de n ao quadrado passos, porque exige muitas comparações repetidas. Isso o torna bem mais lento que a busca linear, que era apenas da ordem de n. Mesmo no melhor caso possível, quando a lista já está ordenada, o pseudocódigo do selection sort não verifica isso e continua repetindo o processo inteiro, encontrando o menor elemento a cada passagem sem necessidade. Por isso, tanto o limite superior quanto o limite inferior desse algoritmo são n ao quadrado, o que permite dizer que ele está em theta de n ao quadrado, ou seja, sempre lento, não importa o caso.
Bubble sort e sua melhoria possível 1:20:02
O bubble sort compara pares de elementos vizinhos e os troca quando estão fora de ordem, repetindo isso n vezes. Analisando o pseudocódigo linha por linha, o loop externo roda n-1 vezes e o loop interno também n-1 vezes, o que multiplicado dá aproximadamente n ao quadrado passos, ignorando os termos menores. No pior caso, portanto, o bubble sort também é da ordem de n ao quadrado. Mas há uma melhoria possível: se numa passagem completa nenhuma troca for feita, o algoritmo pode parar imediatamente, pois isso significa que a lista já está ordenada. Com essa modificação, o limite inferior passa a ser ômega de n, já que basta uma única passagem para confirmar que tudo está em ordem. Ainda assim, no caso médio e no pior caso, o desempenho continua próximo de n ao quadrado.
Visualização com barras coloridas 1:26:31
Uma animação com barras verticais roxas mostra visualmente esses algoritmos em ação. No selection sort, uma barra rosa percorre repetidamente a lista da esquerda para a direita buscando o menor elemento, corrigindo um problema por vez. No bubble sort, as barras rosas indicam os dois números sendo comparados naquele instante, e os maiores valores vão subindo para o topo aos poucos, em pares. A visualização deixa claro como o número de comparações cresce demais, tornando ambos os algoritmos frustrantemente lentos, mesmo com poucas dezenas de valores, o que sugere a necessidade de abordagens melhores.
O que é recursão 1:29:01
Recursão é uma técnica em que uma função é definida em termos de si mesma, ou seja, ela se chama dentro do próprio código. Isso pode parecer perigoso, como um caminho certo para um loop infinito, mas funciona quando cada chamada recebe um problema menor. O exemplo dos armários mostrado antes já era recursivo: ao buscar na metade esquerda ou direita, o mesmo algoritmo é aplicado novamente, só que a um pedaço menor da lista. As condições que respondem imediatamente sim ou não são chamadas de casos base, enquanto os casos recursivos são aqueles em que é preciso fazer mais trabalho, chamando a função novamente com uma versão reduzida do problema.
Pirâmide de Mario feita com recursão 1:34:01
Usando a pirâmide de Super Mario Bros. como exemplo, uma pirâmide de altura 4 pode ser definida como uma pirâmide de altura 3 mais uma linha, e assim por diante até chegar a uma pirâmide de altura 1, que é apenas um único tijolo, funcionando como caso base. No VS Code, o professor primeiro implementa essa pirâmide de forma iterativa, usando loops aninhados para desenhar cada linha com o número certo de tijolos, e o programa funciona corretamente ao imprimir uma pirâmide de altura 4. Depois, ele tenta reescrever a função de forma recursiva, fazendo a função chamar a si mesma para desenhar uma pirâmide de altura n-1 antes de imprimir a última linha. O compilador, porém, recusa a compilação porque falta um caso base: sem ele, a função chamaria a si mesma indefinidamente, e é exatamente esse elemento que fica faltando ao final do trecho.
Caso base na pirâmide recursiva de Mario 1:42:33
O professor retoma a função que desenha a pirâmide de Mario e propõe verificar primeiro se há algo a desenhar. Se n for menor ou igual a zero, a função simplesmente retorna sem imprimir nada, usando o valor de retorno void, que significa que nada é devolvido. Esse cuidado evita problemas caso alguém passe um número negativo. Depois de compilar e testar com o valor 4, o programa imprime exatamente a mesma pirâmide de antes, mas de um jeito considerado mais elegante do que a versão com laços aninhados, especialmente depois de remover comentários e chaves desnecessárias.
Limite de memória na recursão 1:44:32
Ao testar a função com um número muito grande de linhas, o programa apresenta um erro nunca visto antes em sala. Isso acontece porque cada chamada da função usa um pouco mais de memória do computador, e a versão iterativa do mesmo programa não sofre desse problema. O professor explica que isso é uma prévia do que será discutido na próxima aula sobre como a memória funciona, e reconhece que essa é uma desvantagem real da elegância ganha com a recursão.
Merge sort: ordenar e mesclar metades 1:49:00
O merge sort é apresentado como um terceiro algoritmo de ordenação, que usa recursão para ordenar a metade esquerda de uma lista, ordenar a metade direita e depois mesclar as duas metades já ordenadas. O caso base ocorre quando a lista tem apenas um elemento, que já está ordenado por definição. A mesclagem é demonstrada com duas listas de quatro números já ordenadas, escolhendo sempre o menor valor entre as duas pontas, o que exige apenas n passos no total, sem o vai e vem repetitivo de outros algoritmos. Aplicando o processo a oito números fora de ordem, o professor mostra como as chamadas recursivas quebram o problema em pedaços cada vez menores até restar apenas mesclar listas simples.
Complexidade n log n e comparação final 1:53:32
Analisando o trabalho feito, o professor conta três níveis conceituais de mesclagem para oito elementos, e relaciona esse número três ao logaritmo de base dois de oito, já que dois elevado a três é oito. Isso mostra que o tempo de execução do merge sort é da ordem de n log n, tanto no limite superior quanto no inferior, bem menor que o n ao quadrado do bubble sort e do selection sort. Para encerrar, ele exibe uma visualização com selection sort, bubble sort e merge sort ordenando dados aleatórios ao mesmo tempo, deixando visível a diferença de velocidade entre eles antes de despedir a turma.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
