Questão
ID 1545816Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2022 Banca: CESPE CEBRASPE - Centro de Seleção e de Promoção de Eventos UnB Órgão: Defensoria Pública do Estado de Rondônia
função algoritmo1()
0: _ inicio
1: _ se n = 0 então
2:____ retorne 0
3: _ senão
4: _____ se n = 1 então
5: ________retorne 1
6: _____ senão
7: ________ retorne algoritmo1(n−1)+algoritmo1(n−2)
8: _______ fim se
9: _ fim se
10:fim
função algortimo2(n)
0: _ inicio
1: _ se n = 0 então
2: ____ retorne 0
3: _ senão
4:_ _____ se n = 1 então
5: _____+++ retorne 1
6: _____ senão
7: _______ penultimo = 0
8: _______ ultimo =1
9: _______ para i =2 até n faça
10: _________ atual = penultimo + ultimo
11: _________ penultimo = ultimo
12: _________ ultimo = atual
13: _______ fim para
14: _______ retorne atual
15: ______ fim se
16: ___ fim se
17: _ fim
As complexidades dos algoritmo1 e algoritmo2 precedentes são, respectivamente, iguais a