O algoritmo abaixo foi desenvolvido empregando uma lógica iterativa:
Função Calcula (n: inteiro, x: inteiro): inteiro
y: inteiro
para i de 0 até n faça
se (x < 0) então
para i de 0 até n faça
y = y + 1
fimpara
senão
para i de 0 até x faça
y = y + 1
fimpara
fimse
fimpara
retorne y
Fimfunção
Acerca ao algoritmo acima, e trabalhando com os conceitos de complexidade assintótica e recursividade, assinale a alternativa CORRETA:
A A função contém três laços de repetição, sendo que todos os três laços podem acabar sendo executados cada vez que esta função por chamada.
B A complexidade da função, para o pior caso será O(n³).
C A função não realiza chamadas de si mesma, portanto pode ser considerada uma função recursiva.
D Caso exista a possibilidade de implementação deste algoritmo usando uma função recursiva, e sem uso de laços de repetição, a complexidade em tempo de execução da implementação irá melhorar.
E Caso substituíssemos todos os laços de repetição do tipo para, por laços do tipo enquanto, o desempenho do algoritmo em tempo de execução irá melhorar significativamente, uma vez que o laço enquanto tem um custo inferior ao do para.
Soluções para a tarefa
B) A complexidade da função, para o pior caso será O(n³).
Algoritmo é uma sequência finita de instruções definidas e sem ambiguidade, onde cada uma deve ser executada mecanicamente ou eletronicamente considerando um intervalo finito de tempo. São muito utilizados na programação.
O algoritmo é considerado a receita para a resolução de uma tarefa computacional, pois compreende o passo a passo dos procedimentos a serem realizados. Os comentários nos algoritmos são utilizados para facilitar o entendimento do algoritmo em questão.
Bons estudos!
Resposta:
Caso exista a possibilidade de implementação deste algoritmo usando uma função recursiva, e sem uso de laços de repetição, a complexidade em tempo de execução da implementação irá melhorar.
Explicação:
Pois implementando com recursividade teremos uma complexidade atrelada a um crescimento logarítmico.
OBS: Como temos somente 2 laços aninhados, a complexidade será O(n²) e não O(n³).