TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Complexidade De Algoritmo

Dissertações: Complexidade De Algoritmo. Pesquise 859.000+ trabalhos acadêmicos

Por:   •  2/4/2014  •  214 Palavras (1 Páginas)  •  310 Visualizações

ETAPA 1

Passo 1

A Complexidade de um Algoritmo consiste na quantidade de trabalho necessário para a 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 .

Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou função de complexidade f.

f(n) é a medida do tempo necessário pare executar um algoritmo para um problema de tamanha n.

Existem três perspectivas para análise de complexidade:Melhor Caso, Caso Médio, Pior Caso sendo que nas três perspectivas, a função f(n) retorna a complexidade de um algoritmo com entrada de tamanho n

Ômicron (0)

A medida de complexidade Ômicron representa o algoritmo de pior caso, ou seja, dada uma entrada de tamanho n o seu tempo de execução será o maior.

Ex: f(n) = 0 (1)

Ômega (Ω)

A medida de complexidade Ômega representa o algoritmo de melhor caso, ou seja, dada uma entrada de tamanho n o seu tempo de execução será o menor.

Ex: f(n) = Ω(1)

Theta (θ)

A medida de complexidade Theta representa o algoritmo de caso médio, ou seja, a média dos tempos de execução das entradas de tamanho n.

Ex: f(n)= θ (n/2)

...

Disponível apenas no TrabalhosGratuitos.com