Complexidade De Algoritmo

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)