Observe o seguinte código em Python:Considerando que a compl...
Observe o seguinte código em Python:
Considerando que a complexidade de tempo média da função sorted é o (nlogn), em que n
é o tamanho do vetor de entrada, a ordem de chamadas das funções func1, func2 e
func3, da mais rápida para a mais lenta, é:
Comentários
Veja os comentários dos nossos alunos
Gabarito: Letra A.
Essa questão mistura Python com complexidade de algoritmos. Para respondê-la, é preciso saber que a instrução: [codigo for i in colecao] vai executar o codigo para cada item na colecao, e retornar a coleção resultante.
O cálculo do tempo médio vai depender de quantos elementos estão na colecao. Apenas a operação [i for i in var1 < 0.5] filtra os valores, então, quanto mais cedo for executada, melhor será o desempenho.
func1() realiza o filtro no 3o. passo, func2() realiza no 4o. passo, e func3() no 2o. passo. Portanto, func3() < func1() < func2(). Letra A.
Se você quiser uma análise mais detalhada de todos os passos:
No caso 1 (considerando n = 500.000):
param1 - gera 500.000 elementos randômicos, complexidade O(n), lista resultante de tamanho n.
var1 - ordena param1 (tamanho n), portanto, complexidade O(n log n), lista resultante de tamanho n.
var2 - filtra var1 (tamanho n) valores < 0.5, complexidade O(n), lista resultante de tamanho aprox. n/2.
var3 - gera 1-i para var2 (tamanho n/2), complexidade O(n/2).
Tempo acumulado: O(n) + O(n log n) + O(n) + O(n/2).
No caso 2 (considerando n = 500.000):
param1 - gera 500.000 elementos randômicos, complexidade O(n), lista resultante de tamanho n.
var1 - ordena param1 (tamanho n), portanto, complexidade O(n log n), lista resultante de tamanho n.
var2 - gera 1-i para var1 (tamanho n), complexidade O(n), lista resultante de tamanho n.
var3 - filtra var2 (tamanho n) valores < 0.5, complexidade O(n),
Tempo acumulado: O(n) + O(n log n) + O(n) + O(n).
No caso 3 (considerando n = 500.000):
param1 - gera 500.000 elementos randômicos, complexidade O(n), lista resultante de tamanho n.
var1 - filtra param1 (tamanho n) valores < 0.5, complexidade O(n), lista resultante de tamanho n/2.
var2 - ordena var1 (tamanho n/2), portanto, complexidade O(n/2 log n/2), lista resultante de tamanho n/2.
var3 - gera 1-i para var2 (tamanho n/2), complexidade O(n/2), lista resultante de tamanho n/2.
Tempo acumulado: O(n) + O(n/2 log n/2) + O(n/2) + O(n/2).
Portanto: func3 < func1 < func2, letra A.
Prof Judah Reis-Estratégia Concursos
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo
Conheça nossos planos