Melhor caso, pior caso e caso médio
Na ciência da computação, melhor caso, pior caso, e o caso médio de um determinado algoritmo, expressa a quantidade de recurso usado nesse algoritmo, no mínimo, no máximo e em média, respectivamente. Normalmente, o recurso a ser considerado é o tempo de execução, isto é, complexidade do tempo, porém poderia ser também a quantidade de memória usada ou outros recursos.
No tempo real da computação, o pior caso em tempo de execução é muitas vezes motivo de especial preocupação, pois é importante saber quanto tempo pode ser necessário no pior caso para garantir que um algoritmo sempre termine no tempo.
O desempenho médio e o desempenho do pior caso são os mais utilizados na analíse de algoritmo. O menos usado é o desempenho do melhor caso. Porém existe uso para ele: por exemplo, quando se conhece os melhores casos das tarefas individuais, eles podem ser usados para melhorar a precisão da análise do pior caso. Cientistas da computação usam técnicas de análise probabilística, especialmente a do valor esperado, para determinar o tempos de execução esperado.
Esses termos são usados em outros contextos; por exemplo o pior e o melhor caso do resultado de um planejamento para a epidemia, o pior caso da temperatura à qual um elemento de um circuito eletrônico é exposto, etc. Em lugares onde componentes com especificas tolerância são utilizados, os dispositivos devem ser feitos para funcionar corretamente em um pior caso da combinação de tolerâncias e das condições externas.
Desempenho do melhor caso para algoritmo[editar | editar código-fonte]
O termo desempenho do melhor caso é usado na ciência da computação para descrever um comportamento de um algoritmo sob condições ideais. Por exemplo, o melhor caso para uma simples pesquisa linear em uma lista ocorre quando o elemento desejado é o primeiro elemento da lista.
O desenvolvimento e a escolha de algoritmos raramente é baseado no desempenho do melhor caso, a maioria dos acadêmicos e empresas comerciais estão mais interessados em melhorar a complexidade do caso médio e desempenho do pior caso. Algoritmos também podem ser trivialmente modificados para ter um bom desempenho no melhor caso em tempo de execução, codificando soluções para um conjunto finito de entradas, fazendo com que a medida se torne quase que insignificante.[1]
Performance do pior caso versus caso médio[editar | editar código-fonte]
A análise do desempenho do pior caso e caso médio têm algumas semelhanças, mas na prática, geralmente, requerem diferentes ferramentas e abordagens.
Determinar o que significa a entrada média é difícil, e muitas vezes a entrada média tem propriedades que tornam difícil caracteriza-la matematicamente (considere, por exemplo, os algoritmos que são projetados para operar em cadeias de caracteres de um texto). Da mesma forma, mesmo quando uma descrição apropriada de um determinado "caso médio" (que provavelmente só será aplicável para alguns usos do algoritmo) é possível, eles tendem a resultar em análises de equações mais difíceis.
A análise do pior caso tem problemas semelhantes: é normalmente impossível determinar o exato cenário de um pior caso. Em vez disso, considera-se um cenário de tal forma que ele seja no mínimo tão ruim quanto o pior caso. Por exemplo, ao analisar um algoritmo, pode-se encontrar o maior caminho possível utilizando o algoritmo (considerando o número máximo de ciclos, por exemplo), mesmo que não seja possível determinar a exata entrada que geraria esse caminho (na verdade essa entrada pode nem existir). Isso dá uma segurança na análise (pior caso nunca é subestimado), mas ela pode ser pessimista, pois pode não existir uma entrada que exija esse caminho.
Como alternativa, um cenário que acredita-se estar perto do real pior caso (mas não necessariamente ser o pior) pode ser considerado. Isso pode levar a um resultado otimista, o que significa que a análise, na verdade, pode subestimar o verdadeiro pior caso.
Em algumas situações pode ser necessária a utilização de uma análise pessimista, a fim de garantir a segurança. Muitas vezes, no entanto, uma análise pessimista pode ser demasiadamente pessimista, e então, uma análise que se aproxima do valor real mesmo sendo otimista (talvez com alguma conhecida e baixa probabilidade de falha) pode ser muito mais prática.
Ao analisar algoritmos, os quais muitas vezes necessitam de um pequeno tempo para serem concluídos, mas que periodicamente necessitam de uma quantidade maior de tempo, pode-se usar analises amortizadas para determinar o pior caso em tempo de execução através de uma série de operações (possivelmente infinitas). O custo desse amortizador de pior caso pode estar muito mais perto do custo de caso médio e continua garantindo o limite superior do tempo de execução.
A análise do pior caso está relacionada a complexidade do pior caso.[2]
Consequências práticas[editar | editar código-fonte]
Muitos problemas com mau desempenho no pior caso tem bom desempenho no caso médio. Para os problemas que queremos resolver, isso é uma coisa boa: nós podemos esperar que os casos particulares com os quais nos preocupamos sejam casos médios. Para criptografia, isso é muito ruim: nós queremos que casos típicos de um problema de criptografia sejam difíceis. Métodos como reduções aleatórias próprias podem ser usados em problemas específicos para mostrar que o pior caso não é mais difícil do que o caso médio, ou, equivalentemente, que o caso médio não é mais fácil do que o pior caso.
Por outro lado, alguns algoritmos, como o da tabela hash tem poucos comportamentos de pior caso. Porém uma tabela hash bem escrita, de tamanho grande o suficiente nunca irá, estatisticamente, dar um pior caso; o número médio de operações executadas segue uma curva de decaimento exponencial e, portanto, o tempo de execução de uma operação é estatisticamente limitado.
Exemplos[editar | editar código-fonte]
Algoritmos de ordenação[editar | editar código-fonte]
| Algoritmo | Estrutura De Dados | Complexidade do Tempo:
Melhor Caso |
Complexidade do Tempo:
Caso Médio |
Complexidade do Tempo:
Pior Caso |
Espaço de Complexidade:
Pior Caso |
|---|---|---|---|---|---|
| Quick Sort | Array | O(n log(n)) | O(n log(n)) | O(n2) | O(log(n)) |
| Merge sort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Heap sort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Smooth sort | Array | O(n) | O(n log(n)) | O(n log(n)) | O(1) |
| Bubble sort | Array | O(n) | O(n2) | O(n2) | O(1) |
| Insertion sort |
Array | O(n) | O(n2) | O(n2) | O(1) |
| Selection sort | Array | O(n2) | O(n2) | O(n2) | O(1) |
- AplicandoInsertion sort a uma lista de n elementos, os quais assume-se serem todos diferentes e estão inicialmente em ordem aleatória. Em média, metade dos elementos na lista de A1 ... Aj são menores do que o elemento Aj+1, e a outra metade é maior. Portanto, o algoritmo compara o elemento j+1 a ser inserido na média, com metade da sub-lista já ordenada, dessa forma então tj = j/2. Trabalhar com a resultante do caso médio em tempo de execução produz uma função quadrática do tamanho da entrada, assim como o pior caso em tempo de execução.
- Aplicando quicksort a uma lista de n elementos, novamente assumindo que todos os elementos são diferentes e inicialmente estão aleatóriamente ordenados. Este popular algoritmo de ordenação tem um caso médio de desempenho de O(n log(n)), o que contribui para torná-lo um algoritmo muito rápido na prática. Mas com uma entrada de pior caso, o seu desempenho é degradado para O(n2). Além disso, quando não é implementado com a política do "shortest first", o pior caso da complexidade de espaço é degradado para O(log(n)).
Estruturas de dados[editar | editar código-fonte]
| Estrutura de Dado | Complexidade do Tempo: Caso Médio: Indexing | Complexidade do Tempo: Caso Médio: Busca | Complexidade do Tempo: Caso Médio: Inserção | Complexidade do Tempo: Caso Médio: Remoção | Complexidade do Tempo: Pior Caso: Indexing | Complexidade do Tempo: Pior Caso: Busca | Complexidade do Tempo: Pior Caso: Inserção | Complexidade do Tempo: Pior Caso: Remoção | Espaço de Complexidade: Pior Caso |
|---|---|---|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | - | - | O(1) | O(n) | - | - | O(n) |
| Array Dinâmico | O(1) | O(n) | O(n) | - | O(1) | O(n) | O(n) | - | O(n) |
| Lista Simples | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Lista Duplamente Encadeada | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Tabela Hash | - | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) |
| Árvore com
Busca Binária |
- | O((log n)) | O((log n)) | O((log n)) | - | O(n) | O(n) | O(n) | O(n) |
| Árvore-B | - | O((log n)) | O((log n)) | O((log n)) | - | O((log n)) | O((log n)) | O((log n)) | O(n) |
| Árvore Rubro-Negra | - | O((log n)) | O((log n)) | O((log n)) | - | O((log n)) | O((log n)) | O((log n)) | O(n) |
| Árvore AVL | - | O((log n)) | O((log n)) | O((log n)) | - | O((log n)) | O((log n)) | O((log n)) | O(n) |
- Pesquisa Linear em uma lista de n elementos. No absoluto pior caso, a pesquisa visita cada elemento uma vez. Isso acontece quando o valor a ser procurado é o último elemento na lista, ou não está na lista. No entanto, em média, assumindo que o valor procurado está na lista e cada elemento da lista tem a mesma probabilidade de ser o valor procurado, dessa forma a pesquisa visita apenas n/2 elementos.
Veja também[editar | editar código-fonte]
- Algoritmo de ordenação – uma área onde existe uma grande quantidade de análise de desempenho de vários algoritmos.
- Estrutura de dados para pesquisa – qualquer estrutura de dados que permite a eficiente recuperação de itens específicos
- Análise dos piores casos em circuitos
- Alnálise Suavizada
- Intervalo de elementos finitos
- Big O
Referências[editar | editar código-fonte]
- ↑ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".
- ↑ Worst-case complexity