Complexidade algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1021 palavras )
  • Download(s) : 0
  • Publicado : 13 de agosto de 2012
Ler documento completo
Amostra do texto
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 AlgoritmosA 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 deum 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. Ocomportamento 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 algumainstâ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 deAlgoritmos Melhor Caso – Ω (Ômega)

É o menor tempo de execução em uma entrada de tamanho N, é pouco usado, por ter aplicação em poucos casos; é utilizada para analisar o melhor caso.
Uma função f(n) é Ω(g(n)) se з c>0 e n0 tais que f(n) ≥ c*g(n) para n ≥ n0.

Explicação: uma função f(n) é da ordem de complexidade de g(n) e escreve-se f(n) = Ω(g(n)) se existe uma constante c e um valor n0 tal quequalquer valor de n maior do que n0, f(n) é maior ou igual a c*g(n). Isso significa que g(n) é um limite inferior para f(n) .

Exemplo: Mostre que f(n) = Ω(g(n)) sendo f(n) = n³ e g(n) = 6n² + 20

n0≥5
g(n) = 6n² + 20 ≤ 6n² + n²
= 7n² ≤ 7n³
= 7f(n)
Para n0 = 4 e d = 7 temos f(n) = Ω(g(n))







Complexidade de Algoritmos CasoMédio – θ (Theta)

Definido pela letra grega θ (Theta), é a mais difícil de se determinar; deve-se obter a média dos tempos de execução de todas as entradas de tamanho N, ou baseado em probabilidade de determinada condição ocorrer.
Uma função f(n) é Θ(g(n)) se з c1, c2 e n0 tais que c1. g(n) ≤ f(n) 0 e n0 tais que f(n) ≤ c*g(n) para n≥n0.

Explicação: uma função f(n) é da ordem de complexidadede g(n) e escreve-se f(n) = O(g(n)) se existe uma constante c e um valor n0 tal que para qualquer valor de n maior do que n0 f(n) é menor ou igual a c*g(n).
Isso significa que: g(n) é um limite superior para f(n) e f(n) denomina assintoticamente f(n) .

Exemplo: Mostre que a função f(n) = 5n² +10 é ômicron (g(n)) onde g(n) = 2n³ + 5

n0≥4
f(n) = 5n² +10 ≤ 5n² + n
=6n² ≤ 6n³
= 6(2n³ + 5)
=6g(n)

Existe n0 = 4 e c = 6 tal que f(n) é O(g(n)




Comparação de Funções - Passo 3

1. Comparar uma função linear f(n) com uma função quadrática g(n) e mostre que f(n) é Ômicron (g(n)), determinando constantes n0 natural e c real positivo;

f(n) = 7n + 5 g(n) = 3n² + 4

n0≥5
f(n) = 7n + 5 ≤ 7n + n...
tracking img