Questão 2337031

• Banca: FUNECE
• Órgão: UECE
• Ano: 2017
• Provas: FUNECE - 2017 - UECE - Analista de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Conceitos Básicos e Algoritmos

Considere o seguinte algoritmo de criptografia. Ele irá receber na entrada um string S de caracteres s₁,s₂,…,s_m e irá gerar uma nova sequência C de caracteres de saída c₁,c₂,…,c_n, baseada nas seguintes instruções:

1. Inicialmente, faça ci =

•  rote1(si), se i mod 3 = 1, onde rote1 é a operação de rotação de 1 bit para a esquerda
•  rotd2(si), se i mod 3 = 2, onde rotd2 é a operação de rotação de 2 bits para a direita
•  rote3(si), se i mod 3 = 0, onde rote3 é a operação de rotação de 3 bits para a esquerda para 1 ≤ i ≤ m.

2. Após isso, insira em C um novo caractere aleatório a cada três bytes.

Sobre o algoritmo de criptografia acima, é correto afirmar que

• A. o algoritmo criptografa o string S em tempo computacional esperado de log(m * n).
• B. se todos os caracteres de S têm o mesmo valor, então C será estritamente igual a S.
• C. ao final da operação, a sequência C tem o triplo do comprimento de S, quer dizer, n = 3 * m.
• D. o tempo estimado para encontrar o string original S a partir da sequência C é linear.

Gabarito: D

Comentários

• Força Guerreiro!!!!!!

• Primeiro laço tem complexidade m

  Segundo laço tem complexidade m/3

  "m + m/3" é linear (GAB D)

  Na notação BigO, posso eliminar as constantes e a complexidade será: O(m)