Análise de complexidade

(1) 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.
O caso que utilizaria o algoritmo B ao invés do A é quando n = 1.

(2) 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- Estabelecer uma soma que indique quantas vezes sua operação básica foi executada (pior caso)
4- Utilizar regras para manipulação de soma e fórmulas definindo uma função de complexidade
5- Encontrar 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.
Onde há as comparações de v[] indexado até n existe uma ordem de complexidade f(n) = 2n-2 por i iniciar em 2.
b) Podemos dizer que o algoritmo acima é O(n2)? Justifique.
Não, pois a complexidade é dada por 3(n-1), portanto o algoritmo é da ordem de complexidade O(n).

(3) O que significa dizer que um algoritmo executa em tempo proporcional a n?
Significa que é a medida de tempo necessária para executar um algoritmo de tamanho n.

(4) Por muitas vezes damos atenção apenas ao pior caso dos algoritmos. Explique a razão para esta escolha.
Pois queremos saber qual o limite máximo gasto para executar um determinado algoritmo, e o pior caso é o mais fácil de se perceber.

(5) Determine as ordens de complexidade das seguintes funções:

f1(x) = 3x2 + 2x + 5 Pior caso f2(x) = 4x2 + 2y + 5x Pior caso f3(x) = 2x + logx + 1 Caso médio f4(x) = 542 Melhor caso

Qual destas funções possui maior ordem de complexidade?
A que possui maior ordem é f2(x), onde O(n).

(6) O que significa dizer que f(n) é O(1)?
Significa que f(n) é constante.

(7)