30

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 3keyboard_arrow_downkeyboard_arrow_up

Existe uma diferença entre algoritmos determinísticos e algoritmos aleatorizados ao calcularmos tempo de execução. Um algoritmo determinístico pode ter tempos de execução de melhor caso, pior caso ou caso esperado. Quando um algoritmo desse tipo executa múltiplas vezes a mesma entrada, o tempo de execução é o mesmo em cada uma delas, pois o tempo de execução depende da entrada.

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

Algoritmos aleatorizados, por outro lado, fazem escolhas aleatórias quando executados. Logo, quando executa múltiplas vezes a mesma entrada, o tempo de execução pode variar pois depende das escolhas aleatórias feitas pelo algoritmo. Assim, não existe melhor caso ou pior caso. O algoritmo pode escolher qualquer uma das possíveis permutações da entrada, então todos os tempos de execução possíveis são considerados. (o que é igual ao cálculo do caso esperado).

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Portanto, para um algoritmo aleatorizado, somente o tempo de execução esperado é calcualdo.

Navegar por capítulo

O passo a passo dos exercícios mais difíceis

12xR$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca