Questão 1302043

• Banca: FGV
• Órgão: SUSAM
• Ano: 2014
• Provas: FGV - 2014 - SUSAM - Analista de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

 Considere  o  seguinte  pseudocódigo,  no  qual  uma  rotina  com  complexidade O(n) é aplicada em um laço duplo. 

PARA i ←1 ATÉ n FAÇA      

           INÍCIO           

                      PARA j ←1 ATÉ i FAÇA               

                                 INÍCIO 

rotina com complexidade Ο(n);                

                         FIM;           

             FIM PARA;      

      FIM; 

FIM PARA; 

• A. O(n)
• B. O(n.log(n))
• C. O(n² )
• D. O(n³ )
• E. O(n⁴ )

Gabarito: D

Comentários

• Qual é a pergunta??

• Pior banca que eu conheço. Fazem questões que só eles entendem.

• O que é isso? Que questão horrível!

• Pelo contesto da questão eles estão querendo saber a complexidade do algoritmo. Para isso é preciso analisar a complexidade de dentro pra fora dos laços:
  
  

  Dentro do segundo laço a complexidade é O(n) (a rotina)

  
  

  A quantidade de vezes que o segundo laço será executado depende do valor de i, ou seja, em cada iteração do primeiro laço ele será executado:(1 + 2 + 3 + ... + n) vezes. A complexidade fica: O(1) + O(2) + ... + O(n)

  
  

  O primeiro laço será executado n vezes, então a complexidade será O(n).

  
  

  Juntando todas as complexidades: O(n) x (O(1) + O(2) + ... + O(n)) x O(n), removendo as constantes temos O(n) x O(n) x O(n) = O(n³)

  
  

  GABARITO: Letra D

• La Pregunta? o.O

• Força Guerreiro!!!!!!