Questão 5526559

• Banca: FGV
• Órgão: FUNSAÚDE - CE
• Ano: 2021
• Provas: FGV - 2021 - FUNSAÚDE - CE - Analista de Tecnologia da Informação - TI e Infraestrutura de Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Considere o pseudocódigo abaixo, que define uma função que recebe dois arrays, A1, A2, cada um com N elementos indexados a partir de 1, e retorna o número de elementos do array A1 que não aparecem em A2.

function xpto(A1, A2, N)

     contagem=0

     for i=1 to N

            flag=0

            for j=1 to N

                 if A1[i] == A2[j] then flag=1

                 if flag == 0 then contagem=contagem + 1

        return contagem

Exatamente como foi codificado, o algoritmo da função xpto tem complexidade

• A. O(1)
• B. O(n)
• C. O(2.n)
• D. O(n²)
• E. O(2.n²)

Gabarito: D

Comentários

• 2 laços aninhados = O(n^2)

• Complementando o colega Leandro, nem sempre 2 laços aninhados serão O(n^2), se existir alguma condição de parada em algum dos laços for a complexidade será O(n).

• Sentenças simples: Possuem complexidade constante, ou seja, O(1).

  # Sentenças simples

  s = "Brasil"

  i = 42

  i += 1

  Laços simples: Possuem complexidade linear no tamanho da entrada, ou seja, O(n), em que nn é o tamanho da entrada.

  # Laços simples

  for i in range(n):

    # Sentenças simples

  Laços aninhados: Possuem complexidade quadrática no tamanho da entrada, ou seja, O(n2), em que nn é o tamanho da entrada.

  # Laços aninhados

  for i in range(n):

    for j in range(n):

      # Sentenças simples

  https://algoritmosempython.com.br/cursos/algoritmos-python/analise-complexidade/regras-analise-complexidade/