DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos e Estruturas de Dados/Análise de Pior Caso, Caso Médio e Melhor Caso

Análise de Pior Caso, Caso Médio e Melhor Caso

Em ciências da computação, a complexidade de um algoritmo se refere a uma forma de mensurar a qualidade de um algoritmo. Alguns parâmetros são levados em consideração, como o tempo de execução e a quantidade de memória que o algoritmo precisaria para finalizar a sua execução, além da qualidade da resolução do problema. Tendo esses parâmetros, existem três cenários em que o algoritmo é testado, sendo eles:

Melhor caso:

Se refere ao melhor tipo de entrada n em que o algoritmo conseguiria executar seus passos de maneira menos custoso. Ou seja, em condições ideias, qual séria os recursos (tempo, memória) que ele precisaria para finalizar. Normalmente esta análise não é muito usada, pois a compreensão do melhor caso, tem poucas utilidades.

Caso médio:

O caso média é um pouco difícil a definição, pois, dependendo dos parâmetros usados para medir, o conceito de "médio" pode mudar. Mas, de maneira geral, o caso médio seria o cenário em que o algoritmo teria uma certo trabalho na execução do problema, porém, não chegando ao pior caso. Outra definição para o caso média, seria determinar a média da complexidade de entrada de dados. Ou seja, o quanto o pior e melhor caso pode aparecer.

Pior caso:

O pior caso se refere a uma forma de mensurar a qualidade de um algoritmo testando em cenário de mais estresse. Ou seja, a entrada de dados passaria por todos os passos do algoritmo de maneira a esgotar todos os recursos possíveis do algoritmo, ou seja, seria o pior tempo e ocuparia o máximo de memória possível. Este tipo de teste é o usado para nivelar a qualidade do algoritmo, pois, com ele, temos a garantia que o algoritmo funcionará mesmo nos piores cenários.