Complexidade De Algoritmos

Sumario

Etapa 1 3

Passo 2 3

Passo 3 3

1.)Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3 3

2.)Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2 3

3.)Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2 3

Passo 4 4

Etapa 2 5

Passo 1 5

Selection sort 5

Insertion sort 5

Passo 2 5

Passo 3 6

Passo 4 6

Etapa 1

Passo 2

A medida de complexidade Ômicron, ou o pior caso, é representado pela letra grega 0 e baseia-se no maior tempo de execução entre todas as entradas.

Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n).

Por sua vez, a medida de complexidade ômega, representada pela letra grega Ω, representa o melhor caso, onde exprime o menor tempo de execução de um algoritmo para uma entrada n.

Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n)=Ω(1).

Por último temos o caso médio ou medida de complexidade Theta(θ), onde obtêm-se a média dos tempos de execução das entradas de tamanho n.

Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = θ(n/2)

Passo 3

1.)Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3

|n |f(n)=3n + 2 |g(n) = 3n²+2n-3 |

|1 |5 |2 |

|2 |8 |13 |

|3 |11 |30 |

2.)Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2

|n |f(n)=n4 |g(n)=2n³ - n² + n + 2 |

|1 |1 |4 |

|2 |16 |16 |

|3 |81 |50 |

3.)Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2

|n |f(n)=n²-n+2 |g(n)=2n²-3n +2 |

|1 |2 |1 |

|2 |4 |4 |

|3 |8 |11 |

Passo 4

Function Verifica_Item (Lista: TipoLista; x: TipoItem) : Integer;

Var

i: integer;

achou : Boolean;

Begin

I : = 1;

achou := false;

While (i (Low(data)) do

begin

data[j+1]:=data[j];

j:=j-1;

end;

if temp >= data[j] then

data[j+1]:=temp

else

begin

data[j+1]:=data[j];

data[j]:=temp;

end;

end;

end;

Selection Sort

...