Algoritmos Flashcards
Qual a ideia principal da busca binária?
Controlar a faixa atual de suposições razoáveis, diminuindo as suposições para resolver o problema de maneira mais eficiente por utilizar de menos processos.
A cada vez, você faz uma suposição que divide o conjunto de suposições razoáveis em duas faixas de tamanho aproximadamente iguais.
Como adivinhar o ponto do meio inicial de uma busca binária?
A média do primeiro índice pelo último índice arredondada para baixo.
Exemplo: chute = arredonda_para_baixo((min+max)/2);
O que fazer se o palpite for muito baixo? e muito alto? (no algoritmo de busca binária)
Se muito baixo: min = chute + 1
Se muito alto: max = chute - 1;
O que fazer se o alvo não estiver no array em busca binária? Explique o processo que deve acontecer.
Verá que se o alvo não estiver no array, max vai se tornar menor que min pelo laço por muitas vezes ter adicionado + 1 à variável min e por isso retornará um erro, geralmente -1.
Qual a função matemática que significa o mesmo que o número de vezes que reduzimos pela metade de forma repetida até chegarmos ao valor de 1?
O logaritmo de n na base 2, ou log2(n), que também pode ser encontrado como lg n em textos de ciência da computação.
Se n for 128, a busca vai precisar de no máximo quantas tentativas em busca binária? (log2(128)+1)
Nesse caso ocorre a divisão de 128 por 2 até resultar em 1, chegando em 1 conta-se quantas divisões por 2 foram efetuadas mais um (+1) e esse é o resultado de quantas tentativas no máximo seriam efetuadas para ser o alvo ser encontrado, o mais um (+1) é para o caso de o valor não estar no array, ou seja, o pior caso.
Nesse caso a busca precisou de no máximo 8 suposições razoáveis.
Para um algoritmo ser considerado bom, o que é preciso?
É preciso que resolva o problema de maneira correta e de maneira eficiente (baseada em operações feitas que impactam diretamente o tempo de execução).
Para saber entre dois códigos qual o mais eficiente, independente da máquina ou linguagem de programação utilizada, utiliza-se qual método?
Análise assintótica.
Existem algoritmos para solucionar problemas de localização, de rotas ou caminhos de busca, um dos principais algoritmos é uma variação do Greedy Best-First Search. Qual a meta dele? Qual a metáfora por trás dele?
A meta dele é encontrar o melhor caminho entre duas informações cuja posição possa ser estimada.
“A cada passo que você caminha a mais, menos um passo no caminho que você precisa percorrer.”
Se a posição do objetivo estiver desordenada, quais são os principais algoritmos para encontrar o objetivo?
Busca em largura (Breadth First Search - BFS) e busca em profundidade (Depth First Search - DFS).
Em notação assintótica, o que chamamos de taxa de crescimento do tempo de execução?
Taxa de crescimento do tempo de execução é o enfoque no quão rápido uma função cresce com o tamanho da(s) entrada(s).
Suponha que um algoritmo, sendo executado com uma entrada de tamanho n, leve 6n² + 100n + 300 instruções de máquina. Este algoritmo cresce a qual taxa?
Este algoritmo cresce a uma taxa n², deixando de fora o coeficiente 6 e os termos restantes 100n + 300.
Quando usamos notação assintótica? Como usamos nessa situação?
Quando queremos analisar o comportamento de um código diante de uma quantidade arbitrariamente grande de entradas, descartamos os coeficientes constantes e os termos menos significativos, considerando apenas o que importa.
O pior tempo de execução possível da busca linear aumenta de acordo com o que? Qual a notação que usamos para esse tipo de execução?
Com o tamanho do array n. A notação que usamos para esse tipo de execução é Θ(n).
Suponha que o tempo de execução de um algoritmo leve 6n² + 100n + 300 microssegundos, sendo n o tamanho da entrada. Este algoritmo tem qual tempo de execução?
Θ(n²).
