Loading AI tools
Da Wikipédia, a enciclopédia livre
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
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 TA:'N→’N, definido por TA(n):= maxx∈{0, 1}n{tA(x)}.
Definições similares podem ser dadas para complexidade de espaço, complexidade de aleatoriedade, etc.
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(n2) passos para ordená-los; portanto a complexidade de pior caso do insertion sort é O(n2).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.