hsfhffs

Inteligência Artificial Aplicada – Complexidade de Algoritmos
1) Hoje, dos algoritmo de ordenação mais utilizados, o que possui menor complexidade é o inserção, considerando o seu melhor caso, O(n). Podemos dizer que nenhum outro algoritmo poderá atingir uma complexidade melhor do que esta? Justifique.

2) Dois algoritmos A e B possuem complexidade n5 e 2n, respectivamente. Você utilizaria o algoritmo B ao invés do A. Em qual caso? Exemplifique.
3) Considerando, que as chaves inseridas em uma tabela hash não provocaram colisão. Independente do algoritmo, podemos dizer que a pesquisa por uma chave na tabela será de ordem de complexidade constante, ou seja, O(1)? Podemos dizer que este algoritmo é ótimo? Justifique.
4) Para duas funções g(n) e f(n) temos que f(n)=”teta”(n) se somente se f(n)=Ω(g(n)) e f(n)=O(g(n)). Explique o teorema acima.

5) Podemos definir o seguinte algoritmo para calcular a ordem de complexidade de algoritmos não recursivos:
1. Escolher o parâmetro que indica o tamanho da entrada;
2. Identificar a operação básica (comparação, atribuição);
3. Estabeleça uma soma que indique quantas vezes sua operação básica foi executada (pior caso);
4. Utilize regras para manipulação de soma e fórmulas definindo uma função de complexidade;
5. Encontre a ordem de complexidade.
a) Baseando-se no algoritmo acima determine a ordem de complexidade do algoritmo abaixo:
MaxMin(vetor v) max=v[1]; min=v[1]; para i=2 até n faça se v[1]> max então max=v[1]; fimse se v[1]< min então min=v[1]; fimse fimpara; fim. b) Podemos dizer que o algoritmo acima é O(n2)? Justifique.

6) Uma outra métrica muito utilizada para avaliar algoritmos é a Métrica Empírica. Essa consiste em escolher uma métrica (tempo, número de instruções executadas etc.), propor entradas diferenciadas (geralmente com alguma característica pré-definida), ou seja, amostras. Finalmente executar o algoritmo com as entradas e analisar os resultados. Esta medida é muito utilizada