Complexidade de Algoritmos

Prévia do material em texto

ATC Prova 1 Página 3 de 3 25/09/2026 4. (2 pontos) Considere seguinte algoritmo que verifica se dois arrays têm, pelo menos, um elemento igual, onde Contem é 0 algoritmo definido na questão anterior. Entrada: Dois arrays L₁ e L₂, ambos de tamanho n. Saída: Verdadeiro se OS dois arrays têm um elemento igual, Falso caso contrário Comum(array L_1, array L_2, int n) Para i de 0 a n: Se Contem(L_1, n, L_2[i]) : retorne Verdadeiro retorne Falso Qual é a complexidade deste algoritmo na notação O? A. O(lg(n)) B. O(n) C. O(nlg(n)) D. O(n²) E. 5. (2 pontos) Considere 0 seguinte algoritmo abaixo que verifica se um array tem dois elementos iguais. Entrada: Um vetor de inteiros de tamanho n. Saída: se vetor contém dois números iguais. Dois_Iguais(array V, int n) Para i de 0 a n: Para j de i+1 a n: Se V[i] == V[j]: retorne Verdadeiro retorne Falso Qual é a complexidade deste algoritmo na notação O? A. O(lg(n)) O(n) C. D. O(n²)