Analise complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1446 palavras )
  • Download(s) : 0
  • Publicado : 25 de maio de 2012
Ler documento completo
Amostra do texto
ETAPA 1
Passo 2
Omega: Defini-se em medir o menor tempo de execução de um algoritmo para uma entrada de tamanho n , sendo pouco usado . A analise assume que o numero procurado seria o primeiro da lista .
Theta: Defini-se por 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 em média será necessáriovisitar n/2 elementos do vetor até encontrar o elemento procurado, sendo mais difícil de se determinar .
Omicron: Defini-se em obter o maior tempo de execução sobre todas as entradas de tamanho n , sendo considerado o método mais fácil de se obter , no pior dos casos será necessário visitar todos os n elementos do vetor até encontrar o elemento procurado, sendo o piro caso.
Passo 3
1- Acomparação da função linear com a função quadrática pode ser representada pelo grafico a seguir :

Como podemos ver no gráfico , na função quadrática referente a tempo de processamento em função de números de entradas ele gasta muito mais tempo que uma função linear , que no qual leva o mesmo tempo que o numero de entradas (n).
Um exemplo seria que se na função linear se n varia de 0 a 10, f(n)varia de 0 a 10 , já na quadrática se n varia de 0 a 10 , f(n) varia de 0 a 200.
Para provar que o f(n) é omicron podemos definir que f(n) tem limite assintótico superior O(g(x)) ou seja , existe uma constante positiva c1 e n2 tais que 0< f(x) ≤ f(x) ≤ c1 g(x) para n ≥ n0
Resumindo a função de f(n) é sempre menor do que a função g(x) multiplicada por uma constante.
2- A diferença entre oexponencial e a cúbica é que a cúbica representado por O(n³), são uteis apenas para resolver pequenos problemas sendo que quando n é 100 o numero de operações é da ordem de 1 milhão.
O exponencial por sua vez representado por O(2n), não são uteis sob o ponto de vista prático , sendo que quando n é 20 o tempo de execução é cerca de 1 milhão.

Passo 4:
O nosso algoritmo tem a funcionalidadede receber um array , e verificar qual é o maior numero desse array :
Inicio
{
Int array1[5], maior ;
for(int i = 0; i<=5; i++ )
{
Escreva(“Digite um numero”)
Leia(array1[i]);
}
for(int i = 0; i<=5; i++ )
{
If(array1[i]>array[i+1])
{
maior = array[i];
}
Else
{
maior = array[i+1];
}
}
Escreva(“Maior numero é ”+ maior);
} fim

ETAPA 2Passo 1

Ordenação por seleção
Vantagens: É um dos algoritmos mais simples de se aplicar, tem um custo linear no tamanho da entrada para o número de movimentos de registros , é vantajoso para arquivos com registros muito grandes .
Desvantagens: Tanto no melhor caso e no pior caso o custo do tempo será mesmo, outra desvantagem é que o algoritmo não é estável, ou seja os registros com chavesiguais nem sempre irão manter a mesma posição relativa de antes do inicio da ordenação.
Funcionamento: Simplesmente o algoritmo seleciona o menor numero e passa para a primeira posição , sendo o segundo maior para a segunda posição e assim sucessivamente.
O
R
D
E
N
A
1
2
3
4
5
6
Chaves Iniciais:
i=1:
A
R
D
E
N
O
A
D
R
E
N
O
A
D
E
R
N
O
A
D
E
N
R
O
AD
E
N
O
R
i=2:
i=3:
i=4:
i=5:

Ordenação por inserção
Vantagens: Realiza menor número de comparações entre algoritmos de ordenação O(n), quando o vetor está ordenado, e no seu pior caso , ou seja quando todos os itens estão originalmente em ordem reversa ocorre o O(n²).
Desvantagens: Quando se tem um item sendo inserido, todos cabem a todos os elementos maiores serem movidos.Funcionamento: O algoritmo percorre o vetor , da esquerda para direita e consequentemente vai deixando ordenado, Os elementos são divididos em uma seqüência de destino a1, ..., ai-1 e em uma seqüência fonte ai, ..., an.

A
O
O
R
E
N
A
D
O
R
E
N
i = 4
A
O
R
D
E
N
i = 3
A
O
R
D
E
N
A
D
E
O
R
N
i = 5
A
D
E
N
O
R
i = 6
R
A
D
E
N
O
Res.:
Chaves Iniciais...
tracking img