Resumo Prova ADA

Prévia do material em texto

Complexidade de Algoritmo
A complexidade de um algoritmo mede o tempo e o espaço necessários para executá-lo. Esta medida é geralmente expressa em função do tamanho da entrada (n) e pode ser classificada em diferentes ordens de grandeza, como O(1) (constante), O(n) (linear), O(n²) (quadrática), entre outras.
Análise dos Algoritmos
A análise de algoritmos envolve determinar a eficiência de um algoritmo em termos de tempo de execução (complexidade temporal) e memória utilizada (complexidade espacial). Isso é feito através da análise do pior caso, caso médio e melhor caso.
Exemplo de Código - Complexidade do Algoritmo
python
def soma_elementos(lista):
 soma = 0
 for elemento in lista: # Laço Simples
 soma += elemento
 return soma
A complexidade deste algoritmo é O(n), onde n é o número de elementos na lista, pois o tempo de execução cresce linearmente com o tamanho da entrada.
Sentença Simples
Uma sentença simples é uma operação que é executada uma vez, como uma atribuição ou uma comparação. A complexidade de uma sentença simples é O(1).
Laço Simples
Um laço simples (ou loop) percorre uma sequência de elementos. Sua complexidade depende do número de iterações:
python
for i in range(n):
 # operação constante O(1)
A complexidade é O(n).
Laços Aninhados
Laços aninhados envolvem um laço dentro de outro, aumentando a complexidade:
python
for i in range(n):
 for j in range(n):
 # operação constante O(1)
A complexidade é O(n²).
Classes de Complexidade
As classes de complexidade categorizam problemas com base na quantidade de recursos necessários para resolvê-los. Principais classes incluem P, NP, CoNP, NP-hard e NP-complete.
Classe P
Problemas que podem ser resolvidos em tempo polinomial por um algoritmo determinístico.
Exemplo: Ordenação (Merge Sort, Quick Sort).
Classe NP
Problemas para os quais uma solução pode ser verificada em tempo polinomial.
Características: Solução verificável em tempo polinomial.
Exemplo: Problema do Caixeiro Viajante (verificação de uma solução dada).
Classe CoNP
Problemas cuja negação está na classe NP.
Características: Negação da solução verificável em tempo polinomial.
Exemplo: Verificar se um número não é composto.
Classe NP-hard (NP-difícil)
Problemas tão difíceis quanto qualquer problema em NP; não precisam estar em NP.
Características: Todos os problemas em NP podem ser reduzidos a eles.
Exemplo: Problema da Parada.
Classe NP-complete (NP-completo)
Problemas que são tanto NP quanto NP-hard.
Características: Solução verificável em tempo polinomial e tão difícil quanto qualquer problema em NP.
Exemplo: Problema da Satisfatibilidade Booleana (SAT).
 Algoritmo Determinista
Um algoritmo que, dado um estado inicial e uma entrada, produzirá a mesma saída sempre.
Algoritmo Não-determinista
Um algoritmo que pode produzir diferentes saídas para a mesma entrada em execuções diferentes.
Algoritmos de Busca
Busca Sequencial
Procura elemento por elemento até encontrar o alvo ou terminar a lista.
Complexidade: O(n).
Busca Binária
Divide repetidamente a lista ordenada ao meio até encontrar o alvo.
Complexidade: O(log n).
Ordenação Bubblesort
Compara e troca elementos adjacentes repetidamente até que a lista esteja ordenada.
Complexidade: O(n²) no pior caso.
Recursividade
Técnica onde a função se chama a si mesma para resolver subproblemas menores.
Exemplo: Fatorial de um número.
Técnicas de Projeto de Algoritmo
Divisão e Conquista: Divide o problema em subproblemas menores, resolve cada subproblema e combina as soluções.
Programação Dinâmica: Resolve subproblemas de forma otimizada armazenando resultados intermediários.
Guloso (Greedy): Escolhe a melhor solução local em cada etapa, visando encontrar uma solução global ótima.
Backtracking: Explora todas as possibilidades recursivamente e retrocede quando encontra um caminho sem solução.