ATPS Etapa 1 E 2 Analise E Complesidade De Algoritmos
Dissertações: ATPS Etapa 1 E 2 Analise E Complesidade De Algoritmos. Pesquise 861.000+ trabalhos acadêmicosPor: silvio.luizz • 25/5/2013 • 1.690 Palavras (7 Páginas) • 838 Visualizações
Etapa 1
Passo 2
Definir de acordo com o texto lido no passo 1, as medidas de complexidade
Ômicron ( O ), Ômega ( Ω ) e Theta ( Ɵ ).
Melhor Caso
Definido pela letra grega Ω (Ômega).
Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n.
Ex: f(n)=Ω(1)
Pior Caso
Representado pela letra grega 0 (Ômicron).
Baseia-se no maio tempo de execução sobre todas as entradas de tamanho n.
É o método mas fácil de se obter.
Ex: f(n)=0(1)
Caso Médio
Definida pela letra grega Ɵ(Theta)
Deve- se 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.
Ex: f(n)=Ɵ(n/2)
Passo 3
1. Comparar uma função Linear f(n) com uma função Quadrática g(n) e mostre que f(n) é Ômicron (g(n)), determinando constantes n0 natural e c real positivo;
Função Linear f(n) = 5n +2
Função Quadrática g(n) = 2n²
f(n)= 5n+2
g(n)=2n²
f(n) é o(g(n))?
Para n ≥ 3 é o(g(n)).
2. Comparar uma função exponencial f(n) com uma função cúbica g(n) e mostre que f(n) é Ômega (g(n)), determinando constantes n0 natural e d real positivo;
Função exponencial f(n) = 2n n
Função cúbica g(n) = n³+2n
f(n)=2n n
g(n)= n³+2n
f(n)Ω(g(n))?
Para n ≥ 5 é Ω(g(n).
3. Comparar duas funções quadráticas f(n) e g(n) e mostre que f(n) é Theta (g(n)), determinando constantes c, d reais positivos e n0 natural.
Função quadrática f(n) = n²+4+3n
Função quadrática g(n) = 5n²+3²
o ≤ c1 f(n) ≤ g(n)
o ≤ g(n) ≤ c2 f(n)
Passo 4
Criar um algoritmo que tenha pelo menos dois elementos que sejam comuns a maioria dos algoritmos como, por exemplo, atribuições simples, declarações, laços, laços aninhados, If-Then-Else.
Procedure Verifica_Item_Lista
(Lista: TipoLista; x: TipoItem; pos: integer);
Var i: integer;
Begin
I: = 1;
achou := false;
While (i <= Lista.Tamanho) and not achou do begin
inc(i);
if Lista.Intem[i] = then
achou := true;
end;
if achou then
pos := i
else
pos := -1;
Etapa 2
Passo1
Citar as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. Explicar o funcionamento de cada um deles
Ordenação por Seleção (SECTION SORT)
É um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles.
Funcionamento
O processo repete-se até que todos os elementos do array estejam ordenados
Ordenação por Inserção (INSERTION SORT)
É um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os elementos mais a esquerda ordenados.
...