ALGORITMOS AVANÇADO 2

Prévia do material em texto

ALGORITMOS AVANÇADOS
Prof. Alessandro Larangeiras
CONTEÚDO
1. ANÁLISE DE ALGORITMO: NOTAÇÃO O
1.1 Algoritmo
1.2 Estrutura de dados
1.2.1 Revisão de programas em C++ com vetores, matrizes, ponteiros,
registros (struct) e funções
1.3 O que é analise de algoritmos
1.4 Sobre o elemento da análise assintótica: notação O
1.4.1 Notação O
1.4.2 Sobre sua função
1.4.3 Operações com a notação O
2. RECURSIVIDADE
2.1 Definições recursivas
2.2 Como implementar recursividade
2.3 Quando não usar recursividade
2.4 Desenvolvendo algoritmos com recursividade
2 / 59
CONTEÚDO (cont.)
3. ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
(MERGESORT )
3.1 Definição
3.2 Dividir para conquistar
3.3 Problema da intercalação
3.4 O algoritmo de ordenação por intercalação mergesort
3.5 Análise da complexidade do algoritmo mergesort
4. ALGORITMO DE ORDENAÇÃO RÁPIDA (QUICKSORT )
4.1 Definição
4.2 Ordenação rápida
4.3 O algoritmo de ordenação rápida quicksort
4.4 Análise da complexidade do algoritmo quicksort
3 / 59
CONTEÚDO (cont.)
5. ESTRUTURAS DE DADOS DOS TIPOS ÁRVORE BINÁRIA E
ÁRVORE AVL
5.1 Árvores, árvores binárias e árvores binárias de busca
5.2 Implementando as árvores binárias
5.3 Percorrendo uma árvore binária de busca
5.4 Percurso em árvore
5.5 Inserção
5.6 Remoção
5.7 Balanceando uma árvore
5.7.1 O algoritmo DSW (Colin Day, Quentin Stout e Bette Warren)
5.7.2 Árvores AVL (Georgy Adelson-Velsky e Evgenii Landis)
6. ALGORITMOS EM GRAFOS
6.1 Conceitos de grafos
6.2 Representação de grafo
6.3 Algoritmos de busca
6.4 Algoritmo do caminho mínimo
6.4.1 Encontrar o melhor caminho do vértice origem ao vértice destino
4 / 59
BIBLIOGRAFIA PRINCIPAL
ASCENCIO, Ana Fernanda G.; ARAÚJO, Graziela S.
Estruturas de Dados: Algoritmos, Análise da
Complexidade e Implementações em Java e C/C++. São
Paulo: Pearson, 2013.
MANZANO, José Augusto N. G.; OLIVEIRA, Jayr F.
Algoritmos: Lógica para Desenvolvimento de
Programação de Computadores. 28ed. São Paulo: Érica,
2016.
5 / 59
CONTEÚDO
1. ANÁLISE DE ALGORITMO: NOTAÇÃO O
1.1 Algoritmo
1.2 Estrutura de dados
1.2.1 Revisão de programas em C++ com vetores, matrizes, ponteiros,
registros (struct) e funções
1.3 O que é analise de algoritmos
1.4 Sobre o elemento da análise assintótica: notação O
1.4.1 Notação O
1.4.2 Sobre sua função
1.4.3 Operações com a notação O
6 / 59
CONCEITOS
7 / 59
ALGORITMO
«Algoritmo é a especificação da
seqüência ordenada de passos
que deve ser seguida para a
solução de um problema ou
para a realização de uma tarefa,
garantindo a sua repetibilida-
de.» (MALAQUIAS, 2011, slide 3).
8 / 59
ALGORITMO (cont.)
«Um algoritmo (por exemplo, um
programa) é um procedimento,
consistindo em um conjunto de
regras não ambíguas, as quais
especificam, para cada entrada,
uma sequência finita de opera-
ções, terminando com uma saída
correspondente.» (TOSCANI;
VELOSO, 2012, p. 2).
9 / 59
ALGORITMO (cont.)
Algoritmo Euclidiano...
X em linguagem natural:
Calcule o máximo divisor comum de dois inteiros não-negativos P
e Q do seguinte modo: se Q for 0, a resposta é P, se não, divida P
por Q e obtenha o resto R; a resposta será o máximo divisor
comum de Q e R.
X em linguagem de programação Java:
1 public static int gcd(int p, int q) {
2 if(q == 0)
3 return p;
4 int r = p % q;
5 return gcd(q, r);
6 }
(SEDGEWICK; WAYNE, 2011, p. 4).
10 / 59
ESTRUTURA DE DADOS
«Os tipos de dados manipulados por um algoritmo podem ser
classificados em dois grupos: atômicos e [...] compostos [...].»
(LAUREANO, 2008, p. 2, grifo nosso).
Tipo de dados atômico.
Tipo de dados composto.
11 / 59
ESTRUTURA DE DADOS (cont.)
«Se um tipo de dado pode ser decomposto, então [...] é dito
estruturado [...].» (LAUREANO, 2008, p. 2, grifo nosso).
Também conhecido por ESTRUTURA DE DADOS.
12 / 59
ESTRUTURA DE DADOS (cont.)
Estruturas de dados HOMOGÊNEAS
(contêm elementos de um único tipo de
dados).
Estruturas de dados HETEROGÊNEAS
(contêm elementos de diferentes tipos
de dados).
13 / 59
ESTRUTURA DE DADOS (cont.)
Estruturas de dados homogêneas unidimensionais: VETORES.
(LAUREANO, 2008, p. 3).
14 / 59
ESTRUTURA DE DADOS (cont.)
1 // Vetor NOTAS.
2 #include <iostream >
3
4 using namespace std;
5
6 int main(int argc, char* argv[]) {
7 double notas[5];
8 notas[0] = 7.6;
9 notas[1] = 8.0;
10 notas[2] = 5.5;
11 notas[3] = 7.0;
12 notas[4] = 1.0;
13
14 for(int i = 0; i < 5; i++) {
15 cout << "Nota do aluno n." << (i+1) << ": ";
16 cout << notas[i] << endl;
17 }
18 }
15 / 59
ESTRUTURA DE DADOS (cont.)
1 // Vetor PESOS.
2 #include <iostream >
3
4 using namespace std;
5
6 int main(int argc, char* argv[]) {
7 // double pesos[] = { 75,85.2,21.5,90.5,55.3 };
8 double pesos[5] = { 75,85.2,21.5,90.5,55.3 };
9
10 for(int i = 0; i < 5; i++) {
11 cout<< "Peso do paciente "<< (i+1)<< ": ";
12 cout<< pesos[i] << endl;
13 }
14 }
16 / 59
ESTRUTURA DE DADOS (cont.)
1 // Vetor IDADES.
2 #include <iostream >
3
4 using namespace std;
5
6 int main(int argc, char* argv[]) {
7 int idades[3];
8 for(int i = 0; i < 3; i++) {
9 cout << "Digite o valor da idade n."
10 << (i+1) << ": ";
11 cin >> idades[i];
12 }
13
14 for(int i = 0; i < 3; i++)
15 cout << "Idade n." << (i+1) << ": "
16 << idades[i] << endl;
17 }
17 / 59
ESTRUTURA DE DADOS (cont.)
1 // Vetor LETRAS.
2 #include <iostream >
3 using namespace std;
4
5 int main(int argc, char* argv[]) {
6 const int TAM_MAX_NOME = 3;
7 char letras[TAM_MAX_NOME];
8
9 for(int i = 0; i < TAM_MAX_NOME; i++) {
10 cout << "Digite a letra n." << (i+1) << ": ";
11 cin >> letras[i];
12 }
13
14 for(int i = 0; i < TAM_MAX_NOME; i++)
15 cout << "Letra n." << (i+1) << ": "
16 << letras[i] << endl;
17 }
18 / 59
ESTRUTURA DE DADOS (cont.)
Estruturas de dados homogêneas multidimensionais: MATRIZES.
(LAUREANO, 2008, p. 7).
19 / 59
ESTRUTURA DE DADOS (cont.)
1 // Matriz A.
2 int main(int argc, char* argv[]) {
3 int matrizA[1][4];
4 matrizA[0][0] = 3;
5 matrizA[0][1] = 2;
6 matrizA[0][2] = 1;
7 matrizA[0][3] = 5;
8
9 for(int l = 0; l < 1; l++) {
10 for(int c = 0; c < 4; c++) {
11 cout << "Matriz A["
12 << (l+1) << "," << (c+1)
13 << "]= " << matrizA[l][c] << endl;
14 }
15 }
16 }
20 / 59
ESTRUTURA DE DADOS (cont.)
1 // Matriz B.
2 int main(int argc, char* argv[]) {
3 int matrizB[2][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}};
4 for(int l = 0; l < 2; l++) {
5 for(int c = 0; c < 4; c++) {
6 cout << "Matriz B["
7 << (l+1) << "," << (c+1)
8 << "]= " << matrizB[l][c] << endl;
9 }
10 }
11 }
21 / 59
ESTRUTURA DE DADOS (cont.)
1 // Matriz C.
2 int main(int argc, char* argv[]) {
3 int matrizC[2][4];
4 for(int l = 0; l < 2; l++)
5 for(int c = 0; c < 4; c++) {
6 cout << "Digite o elemento ["
7 << (l+1) << "," << (c+1)
8 << "] da matriz C: ";
9 cin >> matrizC[l][c];
10 }
11
12 for(int l = 0; l < 2; l++)
13 for(int c = 0; c < 4; c++) {
14 cout << "Matriz C["
15 << (l+1) << "," << (c+1)
16 << "]= " << matrizC[l][c] << endl;
17 }
18 }
22 / 59
ESTRUTURA DE DADOS (cont.)
Estruturas de dados heterogêneas: REGISTROS.
(LAUREANO, 2008, p. 17).
23 / 59
ESTRUTURA DE DADOS (cont.)
1 // Registro RECTANGLE.
2 struct Rectangle {
3 int left;
4 int top;
5 int width;
6 int height;
7 };
8
9 int main(int argc, char* argv[]) {
10 Rectangle pool = { 30, 40, 70, 80 };
11 Rectangle yard;
12 yard.left = 0;
13 yard.top = 0;
14 yard.width = 100;
15 yard.height = 120;
16 cout << "Yard width = " << yard.width << endl;
17 cout << "Pool width = " << pool.width << endl;
18 }
24 / 59
REVISÃO DE OUTROS RECURSOS DO C++
1 // Ponteiros.
2 int main(int argc, char* argv[]) {
3 int numero
4 int valor;
5
6 int* p; // "DataType*"= ponteiro para DataType
7 //int *p;
8
9 numero = 55;
10 p = &numero; // "&VarName"= Address-Of operator
11 cout<< "p = " << p << "; " << "&numero = "
12 << &numero <<endl;
13 cout<< "*p = " << *p << "; " << "numero = "
14 << numero <<endl;
15
16 valor = *p; // "*VarName"= Indirection operator
17 cout << "valor = " << valor << endl;
18 }
25 / 59
REVISÃO DE OUTROS RECURSOS DO C++ (cont.)
1 // Funcoes: passagem de argumento por valor.2 void troca(int a, int b) {
3 int temp = a;
4 a = b;
5 b = temp;
6 }
7
8 int main(int argc, char* argv[]) {
9 int a = 2;
10 int b = 3;
11 cout<< "Antes da troca: A = " << a
12 << ", B = " << b << endl;
13
14 troca(a, b);
15
16 cout<< "Depois da troca: A = " << a
17 << ", B = " << b << endl;
18 }
26 / 59
REVISÃO DE OUTROS RECURSOS DO C++ (cont.)
1 // Funcoes: passagem de argumento por referencia.
2 void troca(int& a, int& b) {
3 int temp = a;
4 a = b;
5 b = temp;
6 }
7 int main(int argc, char* argv[]) {
8 int a = 2;
9 int b = 3;
10 cout << "Antes da troca: A = " << a
11 << ", B = " << b << endl;
12
13 troca(a, b);
14
15 cout<< "Depois da troca: A = " << a
16 << ", B = " << b << endl;
17 }
27 / 59
ATIVIDADE
1. Desenvolva um programa em C++ que:
a) receba a quantidade de alunos matriculados em um curso de
extensão da Estácio, informada pelo usuário;
b) receba a nota de cada aluno, informada pelo usuário;
c) calcule e exiba a média aritmética das notas dos alunos;
d) calcule e exiba quantas notas são maiores ou iguais e quantas
são inferiores a esta média.
2. Desenvolva um programa em C++ que leia uma matriz 3x3 e
mostre os elementos desta mesma matriz multiplicados pelo
maior número carregado nesta matriz.
28 / 59
ANÁLISE DA COMPLEXIDADE DE ALGORITMOS
29 / 59
ANÁLISE DE ALGORITMOS
«Ciência da Computação não cuida só de programação [...]. Entre
as muitas coisas que os cientistas da computação fazem está a
análise. Algoritmos podem ser analisados [...].» (TOAL, 2018, tradução
nossa).
«Um algoritmo resolve um problema quando, para qualquer
entrada, produz uma resposta correta, se forem concedidos tempo
e memória suficientes para sua execução. O fato de um algoritmo
resolver (teoricamente) um problema não significa que seja
aceitável na prática. Os recursos de espaço e tempo requeridos
têm grande importância em casos práticos. Às vezes, o algoritmo
mais imediato está longe de ser razoável em termos de eficiência
[...].» (TOSCANI; VELOSO, 2012, p. 2).
30 / 59
ANÁLISE DE ALGORITMOS (cont.)
«A complexidade de um algoritmo reflete o esforço
computacional requerido para executá-lo. Esse esforço
computacional mede a quantidade de trabalho, em termos de
tempo de execução ou da quantidade de memória requerida. As
principais medidas de complexidade são TEMPO e ESPAÇO,
relacionadas à velocidade e à quantidade de memória,
respectivamente, para a execução de um algoritmo.» (TOSCANI;
VELOSO, 2012, p. 14, grifo nosso).
31 / 59
ANÁLISE DE ALGORITMOS (cont.)
«Análise de algoritmos é a ciência de se determinar a
quantidade de tempo e espaço requeridos por computadores
[(complexidade computacional)] para executar vários
procedimentos.» (VRAJITORU; KNIGHT, 2014, p. 1, tradução e grifo nossos).
A análise de algoritmos é o estudo da complexidade
computacional de algoritmos, visando aprimorar sua eficiência.
«Por exemplo, pode-se estudar um algoritmo em um dispositivo
móvel para determinar seu efeito sobre o tempo de carga da
bateria [...].» (SEDGEWICK; FLAJOLET, 2013, p. 4, tradução nossa).
32 / 59
ANÁLISE DE ALGORITMOS (cont.)
«É importante ser capaz de medir ou, no mínimo, fazer afirmações
educadas sobre a complexidade de espaço e tempo de um
algoritmo. Isto possibilitará comparar os méritos de duas
abordagens alternativas para a solução de um problema e
determinar também se uma solução proposta atenderá às
restrições de recursos requeridas antes de se investir dinheiro e
tempo na codificação.» (TOAL, 2018, tradução nossa).
«[...] [Uma maneira de se determinar a complexidade de um
algoritmo] é a da medida EMPÍRICA [(baseada na experiência)].
Podemos pensar em medir experimentalmente a quantidade de
trabalho (tempo ou memória) requerida por um algoritmo executa-
do em um computador específico. Entretanto, uma medida empíri-
ca é fortemente dependente, tanto do programa quanto da máqui-
na usada para implementar o algoritmo. [...] Apesar de a compara-
ção de programas reais, rodando em computadores reais, ser...
33 / 59
ANÁLISE DE ALGORITMOS (cont.)
... uma fonte de informação importante, os resultados são
inevitavelmente afetados pela programação e pelas características
das máquinas. Uma alternativa útil vem de se fazer uma análise
MATEMÁTICA do algoritmo de maneira geral. Essa análise, além
de ser independente da implementação, permite, muitas vezes,
antecipar o cálculo da complexidade para a fase de projeto do
algoritmo [e] [...] é útil para avaliar as dificuldades intrínsecas da
resolução computacional de um problema.» (TOSCANI; VELOSO, 2012, p.
14, grifo nosso).
«A análise é feita ANTES da codificação. A perfilação (também
chamada de benchmarking [análise comparativa]) é feita DEPOIS
de o código estar escrito.» (TOAL, 2018, tradução e grifo nossos).
34 / 59
ANÁLISE MATEMÁTICA
«[...] O desempenho de um algoritmo dá o esforço computacional
de execução para uma entrada [(input)] [...]. Por outro lado, a
complexidade de um algoritmo reflete o esforço [computacional]
para executá-lo sobre um conjunto de entradas (digamos, de um
dado "tamanho"). A complexidade pessimista dá o pior valor: o
máximo esforço. Já a complexidade média (ou esperada) dá o
valor esperado: a média dos esforços, levando em conta a
probabilidade de ocorrência de cada entrada.» (TOSCANI; VELOSO,
2012, p. 15, grifo nosso).
35 / 59
ANÁLISE MATEMÁTICA: COMPLEXIDADE DE TEMPO
«[...] Uma das medidas de desempenho mais importante [...] é o
tempo de execução. Neste caso temos complexidade de tempo.»
(TOSCANI; VELOSO, 2012, p. 15).
«O crescente avanço tecnológico, permitindo a criação de máqui-
nas cada vez mais rápidas, pode, ingenuamente, parecer ofuscar
a importância da complexidade de tempo de um algoritmo. Entre-
tanto, acontece exatamente o inverso. As máquinas, tornando-se
mais rápidas, passam a poder resolver problemas maiores, e é a
complexidade do algoritmo que determina o novo tamanho máxi-
mo de problema que pode ser resolvido. Para um algoritmo rápido,
qualquer melhoria na velocidade de execução das operações é
sentida, e o conjunto de problemas que podem ser resolvidos por
ele aumenta sensivelmente. Esse impacto é menor no caso de
algoritmos menos eficientes.» (TOSCANI; VELOSO, 2012, p. 2).
36 / 59
ANÁLISE MATEMÁTICA: COMPLEXIDADE DE ESPAÇO
«A complexidade de espaço usa como medida de desempenho a
quantidade de memória necessária para a execução do algoritmo.
[Apesar de] a memória usada por um programa [...] [depender da
sua] implementação [...], algumas conclusões sobre espaço utili-
zado podem ser tiradas, examinando-se o algoritmo. Um progra-
ma requer uma área para guardar suas instruções, suas constan-
tes, suas variáveis e os dados. Pode também utilizar uma área de
trabalho para manipular os dados e guardar informações [sobre]
[...] a computação. Os dados podem ser representados de várias
formas, as quais requerem uma área maior ou menor. Se os da-
dos têm uma representação natural, por exemplo, como uma ma-
triz, são considerados para análise [...] somente o espaço extra,
além do [...] utilizado para guardar as instruções [...] e os dados.
Porém, se os dados podem ser representados de várias formas,
como um grafo, o espaço requerido para guardá-los também deve
ser levado em conta.» (TOSCANI; VELOSO, 2012, p. 15).
37 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO
Na análise matemática, são contadas as instruções do algoritmo.
Instrução simples é toda aquela executada diretamente pela CPU,
ou similar, tal como:
X atribuição de valor a variável;
X acesso ao valor de determinado elemento de um arranjo;
X comparação entre dois valores;
X incremento de um valor;
X operações aritméticas (adição, multiplicação etc.).
Na contagem, considera-se que:
X as instruções possuem o mesmo custo;
X comandos condicionais possuem custo zero.
38 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR: busca o maior valor em um arranjo A,
com N elementos, e armazena-o em M.
1 int m = a[0];
2 for(int i = 1; i < n; i++) {3 if(a[i] >= m) {
4 m = a[i];
5 }
6 }
39 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
40 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
41 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
Custo de execução do loop for = 2n instruções.
42 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
Custo de execução parcial = 3 + 2n instruções.
43 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
Função matemática do custo de execução deste algoritmo,
considerando o arranjo de input e o loop vazio:
f(n) = 2n + 3
44 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR.
PROBLEMA: o if sempre será executado, MAS nem sempre o
valor de m será alterado.
45 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
ANTES (loop for vazio), bastava saber o tamanho do arranjo (n)
para definir a função de custo: f(n) = 2n + 3.
AGORA (atribuição de m, conforme o if), deve-se considerar
também o conteúdo do arranjo.
46 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Por exemplo, considere dois arranjos de mesmo tamanho:
1 int a1[] = { 1, 2, 3, 4 };
2 int a2[] = { 4, 3, 2, 1 };
3
4 int m = a[0];
5 for(int i = 1; i < n; i++) {
6 if(a[i] >= m) {
7 m = a[i];
8 }
9 }
Conclusão:
X Para o arranjo a1: mais instruções executadas
(if SEMPRE VERDADEIRO).
X Para o arranjo a2: atribuição nunca executada
(if SEMPRE FALSO).
47 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
CUSTO DOMINANTE, ou PIOR CASO, de um algoritmo =
maior número de instruções executadas.
48 / 59
ANÁLISE MATEMÁTICA: CONTAGEM DE
INSTRUÇÕES DE UM ALGORITMO (cont.)
Algoritmo MAIOR VALOR: pior caso (arranjo com valores em
ordem crescente).
Função matemática do custo de execução deste algoritmo (com-
plexidade de tempo), considerando o arranjo de input no pior caso:
f(n) = 3 + 2n + 2n = 4n + 3
49 / 59
ANÁLISE ASSINTÓTICA
50 / 59
51 / 59
RECURSIVIDADE
52 / 59
DEFINIÇÕES RECURSIVAS
«Recursão é o processo de definir algo em termos de si mesmo e
é, algumas vezes, chamado de definição circular. Assim, pode-se
dizer que o conceito de algo recursivo está dentro de si, que por
sua vez está dentro de si e assim sucessivamente, infinitamente.»
(LAUREANO, 2008, p. 60, grifo nosso).
«A sequência de Fibonacci [é um exemplo de recursão e] consiste
em uma série de números, tais que, definindo seus dois primeiros
números como sendo 0 e 1, os números seguintes são obtidos
através da soma dos seus dois antecessores.» (MIRANDA, 2017).
53 / 59
DEFINIÇÕES RECURSIVAS (cont.)
«Exemplo da sequência [de Fibonacci]: 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233... A ocorrência da sucessão de Fibonacci na
natureza é tão frequente que é difícil acreditar que seja acidental
(ex: flores, conchas, mão humana).» (MIRANDA, 2017).
54 / 59
DEFINIÇÕES RECURSIVAS (cont.)
«Uma função é dita recursiva quando dentro dela é feita uma ou
mais chamadas a ela mesma. A ideia é dividir um problema origi-
nal em subproblemas menores de mesma natureza (divisão) e de-
pois combinar as soluções obtidas para gerar a solução do proble-
ma original de tamanho maior (conquista). Os subproblemas são
resolvidos recursivamente do mesmo modo em função de instân-
cias menores, até se tornarem problemas triviais que são resolvi-
dos de forma direta, interrompendo a recursão.» (MIRANDA, 2017).
«Na computação o conceito de recursividade é amplamente utili-
zado, mas [apresenta obrigatoriamente] [...] uma condição que
provoca o fim do ciclo recursivo [...], pois, devido às limitações
técnicas que o computador apresenta, [a recursão deve ser] [...]
impedida de continuar eternamente.» (LAUREANO, 2008, p. 60, grifo nosso).
Possuem suporte a recursividade as linguagens C, C++, Java,
Delphi, Visual Basic e muitas outras.
55 / 59
56 / 59
57 / 59
"Treine enquanto eles dormem,
estude enquanto eles se divertem,
persista enquanto eles descansam
e então viva o que eles sonham."
– Muhammad Ali.
REFERÊNCIAS
LAUREANO, Marcos. Estrutura de Dados com Algoritmos
e C. Rio de Janeiro: Brasport, 2008.
MALAQUIAS, José R. Algoritmos: Conceito e
Representação. 2011. 30 slides: color. Disponível em:
<http://www.decom.ufop.br/romildo/cea030.2011-1/slides/
02-algoritmos>. Acesso em: 22 jul. 2020.
MIRANDA, Paulo A. V. Funções Recursivas. 2017.
Notas da Aula 01, disciplina Introdução à Computação
para Engenharia (MAC2166 - 1s2017). Disponível em:
<http://www.vision.ime.usp.br/~pmiranda/mac2166_1s17/aulas/
P3/aulas_P3.html>. Acesso em: 28 ago. 2020.
SEDGEWICK, Robert; FLAJOLET, Philippe. An
Introduction to The Analysis of Algorithms. 2th. ed. Boston:
Addison-Wesley, 2013.
58 / 59
http://www.decom.ufop.br/romildo/cea030.2011-1/slides/02-algoritmos
http://www.decom.ufop.br/romildo/cea030.2011-1/slides/02-algoritmos
http://www.vision.ime.usp.br/~pmiranda/mac2166_1s17/aulas/P3/aulas_P3.html
http://www.vision.ime.usp.br/~pmiranda/mac2166_1s17/aulas/P3/aulas_P3.html
REFERÊNCIAS (cont.)
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4th. ed.
Boston: Addison-Wesley, 2011.
TOAL, Ray. Algorithm Analysis. 2018. Notes. Disponível
em: <http://cs.lmu.edu/~ray/notes/alganalysis/>. Acesso em:
15 ago. 2018.
TOSCANI, Laira V.; VELOSO, Paulo A. S. Complexidade de
Algoritmos: Análise, Projeto e Métodos. 3. ed. Porto Alegre:
Bookman, 2012.
VRAJITORU, Dana; KNIGHT, William. Practical Analysis of
Algorithms. [S.l.]: Springer, 2014.
59 / 59
http://cs.lmu.edu/~ray/notes/alganalysis/
	ANÁLISE DE ALGORITMO: NOTAÇÃO O
	Algoritmo
	Estrutura de dados
	O que é analise de algoritmos
	Sobre o elemento da análise assintótica: notação O
	RECURSIVIDADE
	Definições recursivas
	Como implementar recursividade
	Quando não usar recursividade
	Desenvolvendo algoritmos com recursividade
	ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO (MERGESORT)
	Definição
	Dividir para conquistar
	Problema da intercalação
	O algoritmo de ordenação por intercalação mergesort
	Análise da complexidade do algoritmo mergesort
	ALGORITMO DE ORDENAÇÃO RÁPIDA (QUICKSORT)
	Definição
	Ordenação rápida
	O algoritmo de ordenação rápida quicksort
	Análise da complexidade do algoritmo quicksort
	ESTRUTURAS DE DADOS DOS TIPOS ÁRVORE BINÁRIA E ÁRVORE AVL
	Árvores, árvores binárias e árvores binárias de busca
	Implementando as árvores binárias
	Percorrendo uma árvore binária de busca
	Percurso em árvore
	Inserção
	Remoção
	Balanceando uma árvore
	ALGORITMOS EM GRAFOS
	Conceitos de grafos
	Representação de grafo
	Algoritmos de busca
	Algoritmo do caminho mínimo