Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa 4 - Coggle Diagram
Mapa 4
Eficiência
Time complexity
Measurint Running Time: identificar a operação básica de um algoritmo (comparações, aritmética, etc) e quantas vezes ela é executada.
Limites para comparar as ordens de crescimento entre 2 funções, se o limite de t(n)/g(n), quando n tende infinito for:
-
-
-
-
Para ambos tempo e espaço, é necessário levar algumas variáveis em consideração:
input size: com maiores inputs, será necessário maior tempo para processamento dos dados, além de mais memória; podemos fazer as funções de eficiencia com base no tamanho do input, que por sua vez tem diversas formas de ser escolhido, dependendo do tipo de dado em questão
Worst-Case, Best-Case, Average-Case
-
-
-
Notação
O(expressao) serve para representar todas as funções com uma ordem de crescimento menor ou igual a da expressão dentro de O
Ω(expressão) serve para representar todas as funções com uma ordem de crescimento maior ou igual a da expressão dentro de Ω.
Θ(expressão) serve para representar todas as funções com uma ordem de crescimento igual a da expressão dentro de Θ .
-
Brute Force
Baseada em uma abordagem mais direta, sem utilizar nenhuma estratégia mais sofisticada, fácil de implementar, porém geralmente é pouco eficiente, comparado aos algoritmos de drecrease and conquer e divide and conquer