complexidade de caso médio

Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis. É frequentemente contrastada com a complexidade de pior caso que considera a complexidade máxima do algoritmo sobre todas as entradas possíveis. Existem três motivações principais para estudar a complexidade de caso médio. Primeiramente, apesar de alguns problemas serem intratáveis no pior caso, as entradas que elicitam esse comportamento podem raramente ocorrer na prática, e portanto a complexidade de caso médio pode ser uma medida mais precisa da performance de um algoritmo. Segundo, a análise de complexidade de caso médio fornece ferramentas e técnicas para gerar instâncias difíceis de problemas que podem ser utilizadas em áreas como criptografia e probabilidade algorítmica. Terceiro, complexidade de caso médio permite diferenciar o algoritmo mais eficiente na prática entre algoritmos equivalentes em complexidade (por exemplo, quicksort). A análise de caso médio requer uma noção de uma entrada "média" para um algoritmo, o que leva ao problema de conceber uma distribuição de probabilidade sobre as entradas. Alternativamente, um algoritmo probabilístico pode ser usado. A análise de tais algoritmos leva à noção relacionada de uma complexidade esperada.