Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM4, 2.1, 2.2, 2.3, 2.4, 2.6, 2.7 - Coggle Diagram
MM4
-
-
-
Notações usadas para comparar e classificar as ordens: O, Ω(ômega) e Θ(teta). Iformalmente:
-
-
-
-
Para calcular tempo de execução é melhor procurar a operação mais importante, chamada de operação básica, que contribui mais para o tempo total de execução e ver quantas vezes é executado
-
Eficiência de pior caso: eficiência da entrada de pior caso de tamanho n, que é a entrada de tamanho n em que o algoritmo é executado por maior tempo entre as entradas possíveis desse tamanho
Analisar o algoritmo e ver qual entrada produz o maior tempo possível na operação básica entre todas as entradas de tamanho n
Eficiência de melhor caso: eficiência da entrada de melhor caso de tamanho n, que é a entrada de tamanho n em que o algoritmo é executado mais rápido entre as entradas possíveis desse tamanho
Analisar o algoritmo e ver qual entrada produz o menor tempo possível entre todas as entradas de tamanho n
Eficiência amortizada: aplicasse a uma sequência de operações executadas da mesma estrutura de dados
Acontece em algumas situações uma única operação pode ser cara, mas o tempo total para uma sequência inteira de n operações é sempre significante melhor do que a eficiência de pior caso
-
-
Eficiência de espaço/complexidade de espaço: quantidade de memória exigida pelo algoritmo além do espaço necessário para sua entrada e saída
-
A eficiência do caso médio não pode ser tomada obtendo a média do melhor e pior caso, embora essa média coincida ocasionalmente com o custo do caso médio, não é uma forma legitima de realizar o teste do caso médio
-
-
-
-
-
-