Complexidade De Algoritmos
Ensaios: Complexidade De Algoritmos. Pesquise 861.000+ trabalhos acadêmicosPor: FRANKbariri • 15/4/2014 • 687 Palavras (3 Páginas) • 479 Visualizações
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
...