Questão 1530406

• Banca: FGV
• Órgão: SUSAM
• Ano: 2014
• Provas: FGV - 2014 - SUSAM - Técnico de Nível Superior - Análise 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 O(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

• PARA + PARA + Rotina = 3

  Logo, n³

• Força Guerreiro!!!!!!

• Fala concurseiro, professor Martins na área...

  Para calcular a complexidade de questões como essa, basta seguir esses três passos:

  1. Considerar apenas as repetições do código

  2. Verificar a complexidade das funções / métodos

  3. Ignorar as constantes e utilizar o termo de maior grau

  Vejamos:

  PARA i ←1 ATÉ n FAÇA -------------> O(n)

                                            INÍCIO

                                                      PARA j ←1 ATÉ i FAÇA -------------> O(n)

                                                                 INÍCIO

                                rotina com complexidade O(n); -------------> O(n)

                                                         FIM;

                                              FIM PARA;

                                       FIM;

                           FIM PARA;

  Identificamos que as repetições são de complexidade O(n), como são iguais e estão dentro uma da outra, então basta multiplicar os valores:

  O(n)*O(n)*O(n) = O(n^3)

  Vamos juntos ser aprovados, guerreiro(a)!

  Para mais dicas me segue no insta @profmartinz