Complexidade algoritmos

SUMÁRIO

COPLEXIDADE DE ALGORITMOS 02

COMPLEXIDADE DE ALGORITIMOS MELHOR CASO Ω (ÔMEGA) 03

COMPLEXIDADE DE ALGORITIMOS CASO MÉDIO θ (THETA) 04

COMPLEXIDADE DE ALGORITMOS PIOR CASO O(ÔMICRON) 05

COMPARAÇÃO DE FUNÇÕES PASSO 3 06

CÁLCULO COMPLEXIDADE DO ALGORTIMO PASSO 4 08

BIBLIOGRAFIA 09

Complexidade de Algoritmos

A Complexidade de Algoritmos consiste na quantidade de “trabalho” necessária para sua execução, expressa em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados.
Algoritmos podem ser avaliados utilizando-se vários critérios. Geralmente o que interessa é a taxa de crescimento ou espaço necessário para resolver instâncias cada vez maiores de um problema. Podemos associar um problema a um valor chamado de ‘tamanho’ do problema, que mede a quantidade de dados de entrada.
O tempo que um algoritmo necessita, expresso como uma função do tamanho do problema, é chamado de complexidade temporal do algoritmo. O comportamento assimptótico dos algoritmos (ou funções) representa o limite do comportamento de custo quando o tamanho cresce. O comportamento assimptótico pode ser definido como o comportamento de um algoritmo para grandes volumes de dados de entrada.
A complexidade temporal de um algoritmo pode ser dividida em 3 aspectos: • Melhor caso – o melhor caso representa uma instância que faz o algoritmo executar utilizando o menor tempo possível. • Pior caso – o maior tempo demorado pelo algoritmo para executar alguma instância. • Caso médio – a média de tempo que o algoritmo demora para executar.

Geralmente, o mais importante é avaliar o pior caso (porque pode inviabilizar o algoritmo) e o caso médio, porque representa como o programa vai se comportar, na prática, na maioria dos casos.
Nas três escalas, a função f(N) retorna a complexidade de um algoritmo com entrada de N elementos.
Complexidade de