Técnicas de Design de Algoritmos
Traduzido por
ScribdTranslationsTécnicas de Design de Algoritmos
Traduzido por
ScribdTranslationsCORE – 14: Técnicas de Design de Algoritmos (Unidade – 1)
O que é um Algoritmo? Um conjunto finito de instruções que especifica uma sequência de operações.
é realizado com o objetivo de resolver um problema específico ou uma classe de problemas é chamado de
um Algoritmo.
Características dos Algoritmos
Deve fornecer externamente zero ou mais quantidades.
Resulta em pelo menos uma quantidade.
Definição: Cada instrução deve ser clara e sem ambiguidades.
Finitude: Um algoritmo deve terminar após executar um número finito de
etapas.
Flexibilidade: Deve ser flexível o suficiente para realizar mudanças desejadas sem
esforços.
Eficiente: O termo eficiência é medido em termos de tempo e espaço necessários
por um algoritmo a ser implementado. Assim, um algoritmo deve garantir que ele tome
pouco tempo e menos espaço de memória para execução.
Independente: Um algoritmo deve ser independente de linguagem, o que significa que
deve focar principalmente na entrada e no procedimento necessário para derivar o
saída em vez de depender da língua.
Pseudocódigo: Pseudocódigo refere-se a uma descrição informal de alto nível do
princípio de operação de um programa de computador ou outro algoritmo. Ele usa estrutural
convenções de uma linguagem de programação padrão destinadas à leitura humana
em vez da máquina ler.
Vantagens do Pseudocódigo
Uma vez que é semelhante a uma linguagem de programação, pode ser rapidamente transformado
na linguagem de programação real do que em um fluxograma.
O leigo pode entender isso facilmente.
Facilmente modificável em comparação aos fluxogramas.
Sua implementação é benéfica para elementos estruturados e projetados.
Ele pode detectar facilmente um erro antes de transformá-lo em código.
Desvantagens do Pseudocódigo
Como não incorpora nenhum estilo ou formato padronizado, pode variar de
uma empresa para outra.
Não retrata o design.
Análise de algoritmo: A análise é um processo de estimar a eficiência de
um algoritmo. Existem dois parâmetros fundamentais com base nos quais podemos
analisar o algoritmo:
Complexidade Espacial: A complexidade espacial pode ser entendida como a quantidade
do espaço necessário por um algoritmo para ser executado.
Complexidade de Tempo: A complexidade de tempo é uma função do tamanho da entrada que se refere a
a quantidade de tempo necessária para que um algoritmo seja executado.
M K M ish r a, A sst . P r of . de C iências da Computação, F M A C, Bls. Página1de7
Geralmente, fazemos três tipos de análises, que são as seguintes:
Complexidade de tempo no pior caso: Para um tamanho de entrada 'n', o pior caso de tempo
A complexidade pode ser definida como a quantidade máxima de tempo necessária por um
algoritmo para completar sua execução. Assim, não é nada além de uma função definida
pelo número máximo de etapas realizadas em uma instância tendo uma entrada
tamanho de n.
Complexidade de tempo de caso médio: Para o tamanho de entrada 'n', o tempo de caso médio
a complexidade pode ser definida como a quantidade média de tempo necessária por um
algoritmo para completar sua execução. Assim, não é nada além de uma função definida
pelo número médio de passos realizados em uma instância que possui uma entrada
tamanho de n.
Complexidade de tempo no melhor caso: Para um tamanho de entrada 'n', a complexidade de tempo no melhor caso
pode ser definido como a quantidade mínima de tempo necessária para que um algoritmo
complete sua execução. Assim, não é nada além de uma função definida pela
número mínimo de passos realizados em uma instância com um tamanho de entrada de n.
Notações Assintóticas: Notação Assintótica é uma forma de comparar funções que
ignora fatores constantes e tamanhos de entrada pequenos. Três notações são usadas para calcular
a complexidade de tempo de execução de um algoritmo:
1. Notação Big-oh: Big-oh é o método formal de expressar o limite superior de
o tempo de execução de um algoritmo. Matematicamente, é definido como:
f(n) = O(g(n))[lê-se "f de n é big-oh de g de n"], se existir um positivo
constantes c e n0, de modo que f(n)≤c.g(n)∀ n≥n0
Exemplo: f(n) = 2n²+5 é O(n²)
2. Notação Big-Omega: Big-oh é o método formal de expressar o limite inferior
do tempo de execução de um algoritmo. Matematicamente, é definido como:
f(n) =Ω(g(n))[lido como "f de n é big-omega de g de n"], se existir um
constantes positivas c e n0, de forma que 0≤c.g(n)≤f(n)∀ n≥n0
3. Theta (θ): A notação theta é tanto um limite superior quanto inferior, portanto define
comportamento assintótico exato. Matematicamente é definido como:
f(n) =Θ(g(n))[lido como "f de n é teta de g de n"], se existe um positivo
constantes c1, c2e n0, de modo que 0≤c1.g(n)≤f(n)≤c2.g(n)∀ n≥n0
As três notações assintóticas acima estão representadas pictorialmente abaixo.
M K M ish r a, A sst . P r of. de Com p. Sc., F M A C, Bls. Página2de7
Análise e design do algoritmo de ordenação por inserção:
Exemplo de execução do algoritmo de ordenação por inserção
ALGORITMO: CLASSIFICAÇÃO POR INSERÇÃO (A)
1. Para k←1 até o comprimento [A]
2. Faça key← A[k]
3. i = k-1
4. enquanto (i≥0 e A[i] > chave) Repetir
passos 5 e 6
5. faça A[i+1]← A[i]
6. i = i-1
7. A[i+1]← chave
Análise:
1. Entrada: n elementos são dados.
[Link]ída: o número de comparações necessárias para fazer a ordenação.
3.Lógica: Se temos n elementos na ordenação por inserção, então n-1 passes são necessários para
encontre um array ordenado.
Na passagem 1: nenhuma comparação é necessária
Na passagem 2: 1 comparação é necessária
Na passagem 3: são necessárias 2 comparações
............................................................................
...............................................................................
Na passagem n: são necessárias n-1 comparações
Comparações totais: T (n) = 1+2+3+...........+ n-1
(n-1)n / 2
= O (n2)
Portanto, a complexidade é de ordem n2
Paradigma de Dividir e Conquistar: O algoritmo de Dividir e Conquistar consiste em um
disputa usando os seguintes três passos.
[Link] o problema original em um conjunto de subproblemas de menor tamanho.
[Link]: Resolva cada subproblema individualmente, recursivamente.
3. Combinar: Juntar as soluções dos subproblemas para obter a solução para
todo o problema.
M K M ish r a, A sst . P r of. de C iência da Computação, F M A C, Bls. Página 3 de 7
Problema
Dividir
Subproblema Subproblema
Resolver Resolver
Conquistar
Sub-problema Subproblema
Solução para Solução para
Subproblema Subproblema
Combinar
Solução para
o Problema
Exemplos: Alguns dos algoritmos baseados na abordagem Dividir & Conquistar
incluir:
1. Busca Binária
2. Ordenação (ordenar por mistura, ordenar rápido)
Os princípios da Estratégia de Dividir e Conquistar são:
1. Fórmula Relacional
2. Condição de Parada
Vantagens da Divisão e Conquista
Isso minimiza o esforço de projetar um algoritmo, pois funciona dividindo o
divida o problema principal em dois ou mais subproblemas de menor tamanho e, em seguida, resolva-os
recursivamente.
Ele utiliza a memória cache de forma eficiente sem ocupar muito espaço porque
resolve subproblemas simples dentro da memória cache em vez de acessar o
memória principal mais lenta.
Desvantagens da Divisão e Conquista
Uma pilha explícita pode usar espaço em excesso.
Pode até travar o sistema se a recursão for realizada de forma rigorosamente maior
do que a pilha presente na CPU.
Relação de Recorrência: Uma recorrência é uma equação ou inequação que descreve uma
função em termos de seus valores em entradas menores. Para resolver uma Relação de Recorrência
significa obter uma função definida nos números naturais que satisfaça a
recorrência.
Por exemplo, no Merge Sort, para ordenar um determinado array, nós o dividimos em duas metades e
repita recursivamente o processo para as duas metades. Finalmente, nós juntamos os resultados. Tempo
A complexidade do Merge Sort pode ser escrita como T(n) = 2T(n/2) + cn. Existem principalmente
três métodos para resolver Recorrências:
1. Método da Substituição
2. Método da Árvore de Recursão
3. Método Mestre
M K M ish r a, A sst . P r of. de C iênc. da C omp., F M A C, Bls. Página 4 de 7
1. Método de Substituição: O Método de Substituição consiste em duas etapas principais:
1. Adivinhe a Solução.
2. Use a indução matemática para encontrar a condição de contorno e mostrar que
a suposição está correta.
Por exemplo, considere a recorrência T(n) = 2T(n/2) + n, para n > 1
Nós supomos que a solução é T(n) = O(nLogn). Agora usamos indução para provar nossa
adivinhe.
Precisamos provar que T(n)≤cnLogn para alguma constante positiva c.
Podemos assumir que é verdade para valores menores de n.
T(n) = 2T(n/2) + n
≤2cn/2Log(n/2) + n
= cn ( Logn - Log2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
≤cnLogn
Assim T(n) = O(n logn) para n > 1
Método da Árvore de Recursão: Neste método, desenhamos uma árvore de recorrência e
calcular o tempo gasto por cada nível da árvore. Finalmente, somamos o trabalho realizado em todos
níveis. Para traçar a árvore de recorrência, começamos a partir da recorrência dada e continuamos
desenhando até encontrarmos um padrão entre os níveis. O padrão é tipicamente aritmético ou
séries geométricas. Por exemplo, considere a relação de recorrência
T (n) = 2T(n/2) + n2
Temos que obter o limite assintótico usando o método da árvore de recursão.
Solução: A árvore de recursão para a recorrência acima é
M K M ish r a, A sst . P r of. de C iênc. Comp., F M A C, Bls. Página 5 de 7
Método Master: O Método Master é utilizado para resolver os seguintes tipos de
recorrência
T(n) = aT(n/b) + f(n) para a≥1 e b>1 serem inteiros não negativos & f(n) ser uma função.
Aqui, a importância dos literais é:
n é o tamanho do problema.
a é o número de subproblemas na recursão.
n/b é o tamanho de cada subproblema. (Aqui se presume que todos os subproblemas
são essencialmente do mesmo tamanho.)
f (n) é a soma do trabalho realizado fora das chamadas recursivas, que inclui o
soma de dividir o problema e a soma de combinar as soluções para o
sub-problemas.
Não é sempre possível limitar a função conforme a necessidade, então
fazemos três casos que nos dirão que tipo de limite podemos aplicar no
função.
M K M ish r a, A sst . P r of. de C iênc. Com p., F M A C, Bls. Página 6 de 7
Teorema Mestre: É
possível completar um
limite assintótico apertado em
esses três casos:
Exemplo-1: T(n) = 8T(n/2) + 1000n2. Resolva aplicando o teorema mestre.
Solução: Compare T (n) = 8T (n/2) + 1000n2com T (n) = aT (n/b) + f (n) para a≥1 e b>1
Aqui, a = 8, b = 2, f (n) = 1000 n2, registroba = log28 = 3
Coloque todos os valores em: f (n) =
1000 n2= O (n3-ε)
Se escolhermos ε=1, obtemos: 1000 n2O (n3-1) = O (n2)
Uma vez que essa equação é verdadeira, o primeiro caso do teorema mestre se aplica ao dado.
relação de recorrência, resultando, assim, na conclusão:
T (n) = Θ
Portanto: T (n) = Θ(n3)
Exemplo-2: T (n) = 2T (n/2) + n, Resolva a recorrência usando o método mestre.
Comparar T (n) = 2T (n/2) + n com T (n) = aT(n/b) + f(n) para a ≥ 1 b > 1
Aqui, a = 2, b = 2, f(n) = n, logba = log22 = 1
Vemos que n = Θ = Θ (n) o que é verdade. Portanto, o caso 2 do teorema mestre
mantém. Portanto, T(n) = Θ (n log n)
Exemplo-3: Resolva a relação de recorrência T(n) = 2T(n/2) + n2usando o mestre
método.
Solução: Compare T(n) = 2T(n/2) + n2com T(n) = aT(n/b) + f(n) para a ≥ 1, b > 1
Aqui, a = 2, b = 2, f(n) = n2, logba = log22 = 1
Coloque todos os valores em f (n) = Ω ..... (Eq. 1)
Se inserirmos todos os valores em (Eq.1), obteremos
n2Ω(n1+ε), coloque ε = 1, então a igualdade será mantida.
n2= Ω(n1+1) = Ω(n2)
Agora também vamos verificar a segunda condição:
2(n/2)2≤ cn2
n2/2≤ cn2
Se escolhermos c = 1/2, é verdade que n2/2≤ n2/2∀ n≥1
Assim, segue que T (n) = Θ ((f (n))
Portanto, T (n) = Θ (n2)