Complexidade de pior caso

Na Ciência da computação a “Complexidade de pior caso” (usualmente denotada em notação assintótica) mede os recursos (ex. tempo de execução, memória) que um algoritmo precisa no pior caso. Isto dá um limitante superior dos recursos necessários ao algoritmo.

No caso de tempo de execução, a complexidade de pior caso indica o maior tempo de execução de um algoritmo dado “qualquer" entrada de tamanho “n”, e assim isto garante que o algoritmo termine no tempo. Além disso, a ordem de crescimento da complexidade de pior caso é usado para comparar a eficiência de dois algoritmos.

A complexidade de pior tempo de um algoritmo deve ser contratada com o seu complexidade de caso médio, que é uma medida média da quantidade de recursos que o algoritmo usa numa entrada aleatória

Definição

Dado um modelo de computação e um algoritmo “A" que para em cada entrada “x”, o mapeamento “t"_A:{0, 1}*→N é chamado de "a complexidade de tempo de A" se, para cada "x", A pára exatamente após “t”_A (“x”) passos.

Como normalmente estamos interessados na dependência da ‘complexidade de tempo’ sobre entradas de comprimentos diferentes, abusando de terminologia, a complexidade de tempo é, algumas vezes, uma referência ao mapeamento T_A:'N→’N, definido por T_A(n):= max_{x∈{0, 1}ⁿ}{t_A(x)}.

Definições similares podem ser dadas para complexidade de espaço, complexidade de aleatoriedade, etc.

Exemplos

Considere executar o insertion sort sobre “n" números numa ram. O melhor caso para o algoritmo é quando os números já estão ordenados, o que leva O(n) passos para executar a tarefa. Entretanto, a entrada no pior caso para o algoritmo é quando os números estão na ordem reversa, e leva O(n²) passos para ordená-los; portanto a complexidade de pior caso do insertion sort é O(n²).

Veja também

Análise de algoritmos

Referências

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 0-521-88473-X, p.32.