Embed Size (px)
Citation preview
Algoritmos e Estruturas de Dados IProf. Tiago Eugenio de Melo
www.tiagodemelo.info
2/209
Observações
3/209
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 11 do livro “Fundamentals of Python – From First Programs Through Data Structures”.
4/209
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 11 do livro “Fundamentals of Python – From First Programs Through Data Structures”.
● As palavras com a fonte Courier indicam uma palavra-reservada da linguagem de programação.
5/209
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 11 do livro “Fundamentals of Python – From First Programs Through Data Structures”.
● As palavras com a fonte Courier indicam uma palavra-reservada da linguagem de programação.
● Basta clicar na imagem para acessar as fontes das animações e figuras usadas nesse material.
6/209
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 11 do livro “Fundamentals of Python – From First Programs Through Data Structures”.
● As palavras com a fonte Courier indicam uma palavra-reservada da linguagem de programação.
● Basta clicar na imagem para acessar as fontes das animações e figuras usadas nesse material.
● Os slides com o símbolo CO (COLAB) abaixo indicam que o código estará disponível on-line:
7/209
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 11 do livro “Fundamentals of Python – From First Programs Through Data Structures”.
● As palavras com a fonte Courier indicam uma palavra-reservada da linguagem de programação.
● Basta clicar na imagem para acessar as fontes das animações e figuras usadas nesse material.
● Os slides com o símbolo CO (COLAB) abaixo indicam que o código estará disponível on-line:
8/209
Objetivos
9/209
Objetivos
● Após o término dessa aula você deverá ser capaz de:
10/209
Objetivos
● Após o término dessa aula você deverá ser capaz de:– Medir a performance de um algoritmo através do
tempo e do número de instruções executadas com diferentes tamanhos de dados.
11/209
Objetivos
● Após o término dessa aula você deverá ser capaz de:– Medir a performance de um algoritmo através do
tempo e do número de instruções executadas com diferentes tamanhos de dados.
– Analisar a performance de um algoritmo e determinar a sua ordem de complexidade utilizando a notação big-O.
12/209
Objetivos
● Após o término dessa aula você deverá ser capaz de:– Medir a performance de um algoritmo através do
tempo e do número de instruções executadas com diferentes tamanhos de dados.
– Analisar a performance de um algoritmo e determinar a sua ordem de complexidade utilizando a notação big-O.
– Diferenciar as ordens de complexidade de algoritmos.
13/209
Medindo a Eficiência de Algoritmos
14/209
Medindo a Eficiência de Algoritmos
● Na escolha de algoritmos, nós frequentemente temos que optar entre espaço e tempo (tradeoff).
15/209
Medindo a Eficiência de Algoritmos
● Na escolha de algoritmos, nós frequentemente temos que optar entre espaço e tempo (tradeoff).– Um algoritmo pode ser projetado para ter ganhos
de velocidade ao custo de usar espaço extra de memória.
16/209
Medindo a Eficiência de Algoritmos
● Na escolha de algoritmos, nós frequentemente temos que optar entre espaço e tempo (tradeoff).– Um algoritmo pode ser projetado para ter ganhos de
velocidade ao custo de usar espaço extra de memória.
● Memória tem, atualmente, um preço aceitável para computadores, mas isso ainda não é o mesmo para dispositivos menores.
17/209
Medindo a Eficiência de Algoritmos
● Na escolha de algoritmos, nós frequentemente temos que optar entre espaço e tempo (tradeoff).– Um algoritmo pode ser projetado para ter ganhos de
velocidade ao custo de usar espaço extra de memória.● Memória tem, atualmente, um preço aceitável
para computadores, mas isso ainda não é o mesmo para dispositivos menores. – Exemplo: memória de celular.
18/209
Medindo o tempo de execução de um algoritmo
19/209
Medindo o tempo de execução de um algoritmo
● Uma maneira de medir o custo de tempo de um algoritmo é usar o clock do computador para obter o tempo real de execução.
20/209
Medindo o tempo de execução de um algoritmo
● Uma maneira de medir o custo de tempo de um algoritmo é usar o clock do computador para obter o tempo real de execução.– Benchmarking ou profiling.
21/209
Medindo o tempo de execução de um algoritmo
● Uma maneira de medir o custo de tempo de um algoritmo é usar o clock do computador para obter o tempo real de execução.– Benchmarking ou profiling.
● Nós podemos usar a função time( ) do módulo time de Python.
22/209
Medindo o tempo de execução de um algoritmo
● Uma maneira de medir o custo de tempo de um algoritmo é usar o clock do computador para obter o tempo real de execução.– Benchmarking ou profiling.
● Nós podemos usar a função time( ) do módulo time de Python.– Essa função retorna o número de segundos
transcorridos entre a hora do computador e a data de 1o de janeiro de 1970.
24/209
Medindo o tempo de execução de um algoritmo (cont.)
26/209
Medindo o tempo de execução de um algoritmo (cont.)
● Saída do programa anterior:
28/209
Medindo o tempo de execução de um algoritmo (cont.)
● Versão modificada do programa anterior:
29/209
Medindo o tempo de execução de um algoritmo (cont.)
● Resultado:
30/209
Medindo o tempo de execução de um algoritmo (cont.)
● Medição de tempo no Linux
31/209
Medindo o tempo de execução de um algoritmo (cont.)
32/209
Medindo o tempo de execução de um algoritmo (cont.)
● Este método realiza a medição do tempo de execução de muitos algoritmos.
33/209
Medindo o tempo de execução de um algoritmo (cont.)
● Este método realiza a medição do tempo de execução de muitos algoritmos.
● Problemas:
34/209
Medindo o tempo de execução de um algoritmo (cont.)
● Este método realiza a medição do tempo de execução de muitos algoritmos.
● Problemas:– Diferentes plataformas de hardware têm diferentes
velocidades. Portanto, o tempo de execução de um algoritmo pode variar de acordo com a máquina.
35/209
Medindo o tempo de execução de um algoritmo (cont.)
● Este método realiza a medição do tempo de execução de muitos algoritmos.
● Problemas:– Diferentes plataformas de hardware têm diferentes
velocidades. Portanto, o tempo de execução de um algoritmo pode variar de acordo com a máquina.
● O tempo de execução varia também de acordo com o sistema operacional e a linguagem de programação.
36/209
Medindo o tempo de execução de um algoritmo (cont.)
● Este método realiza a medição do tempo de execução de muitos algoritmos.
● Problemas:– Diferentes plataformas de hardware têm diferentes
velocidades. Portanto, o tempo de execução de um algoritmo pode variar de acordo com a máquina.
● O tempo de execução varia também de acordo com o sistema operacional e a linguagem de programação.
– É impraticável determinar o tempo de execução para alguns algoritmos com um conjunto de dados (dataset) muito grande.
37/209
Quantidade de instruções
38/209
Quantidade de instruções
● Outra técnica é contar o número de instruções executadas com diferentes tamanhos de dados.
39/209
Quantidade de instruções
● Outra técnica é contar o número de instruções executadas com diferentes tamanhos de dados.– Nós contamos as instruções em código de alto-
nível em que o algoritmo é escrito. A contagem não é feita das instruções do programa na sua linguagem de máquina executável.
40/209
Quantidade de instruções
● Outra técnica é contar o número de instruções executadas com diferentes tamanhos de dados.– Nós contamos as instruções em código de alto-
nível em que o algoritmo é escrito. A contagem não é feita das instruções do programa na sua linguagem de máquina executável.
● Distinção entre:
41/209
Quantidade de instruções
● Outra técnica é contar o número de instruções executadas com diferentes tamanhos de dados.– Nós contamos as instruções em código de alto-nível
em que o algoritmo é escrito. A contagem não é feita das instruções do programa na sua linguagem de máquina executável.
● Distinção entre:– Instruções que executam o mesmo número de
vezes independentemente do tamanho do problema.
42/209
Quantidade de instruções
● Outra técnica é contar o número de instruções executadas com diferentes tamanhos de dados.– Nós contamos as instruções em código de alto-nível em que
o algoritmo é escrito. A contagem não é feita das instruções do programa na sua linguagem de máquina executável.
● Distinção entre:– Instruções que executam o mesmo número de vezes
independentemente do tamanho do problema.– Instruções cuja quantidade varia de acordo com o tamanho
do problema.
44/209
Quantidade de instruções (cont.)
46/209
Quantidade de instruções (cont.)
● Saída do programa anterior:
48/209
50/209
Quantidade de instruções (cont.)
● Saída do programa anterior:
51/209
Medir a memória usada por um algoritmo
52/209
Medir a memória usada por um algoritmo
● Uma análise completa de recursos usados por um algoritmo inclui a quantidade de memória exigida para execução do algoritmo.
53/209
Medir a memória usada por um algoritmo
● Uma análise completa de recursos usados por um algoritmo inclui a quantidade de memória exigida para execução do algoritmo.
● Nós focamos nas taxas potenciais de crescimento.
54/209
Medir a memória usada por um algoritmo
● Uma análise completa de recursos usados por um algoritmo inclui a quantidade de memória exigida para execução do algoritmo.
● Nós focamos nas taxas potenciais de crescimento.
● Alguns algoritmos requerem a mesma quantidade de memória para resolver qualquer problema.
55/209
Medir a memória usada por um algoritmo
● Uma análise completa de recursos usados por um algoritmo inclui a quantidade de memória exigida para execução do algoritmo.
● Nós focamos nas taxas potenciais de crescimento.● Alguns algoritmos requerem a mesma quantidade
de memória para resolver qualquer problema.● Outros algoritmos requerem mais memória
conforme o crescimento do tamanho do problema.
56/209
Análise de complexidade
57/209
Análise de complexidade
● Análise de complexidade implica ler o algoritmo e usar lápis e papel para manipular algumas análises algébricas.
58/209
Análise de complexidade
● Análise de complexidade implica ler o algoritmo e usar lápis e papel para manipular algumas análises algébricas.
● É usada para determinar a eficiência de algoritmos.
59/209
Análise de complexidade
● Análise de complexidade implica ler o algoritmo e usar lápis e papel para manipular algumas análises algébricas.
● É usada para determinar a eficiência de algoritmos.
● Ela nos permite medir a eficiência dos algoritmos independentemente da plataforma ou da quantidade de instruções.
60/209
Ordens de complexidade
● Considere os dois resultados abaixo:
61/209
Ordens de complexidade (cont.)
62/209
Ordens de complexidade (cont.)
● As performances desses algoritmos variam pelo que costumamos chamar de ordem de complexidade:
63/209
Ordens de complexidade (cont.)
● As performances desses algoritmos variam pelo que costumamos chamar de ordem de complexidade:– O primeiro algoritmo é linear.
64/209
Ordens de complexidade (cont.)
● As performances desses algoritmos variam pelo que costumamos chamar de ordem de complexidade:– O primeiro algoritmo é linear.– O segundo algoritmo é quadrático.
65/209
Ordens de complexidade (cont.)
66/209
Ordens de complexidade (cont.)
● Ordens de complexidade
67/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Constante
68/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Constante
● Requer o mesmo número de operações independentemente do tamanho do problema.
69/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Constante
● Requer o mesmo número de operações independentemente do tamanho do problema.
● É o caso, por exemplo, do acesso direto a um elemento de uma matriz.
70/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Constante
● Requer o mesmo número de operações independentemente do tamanho do problema.
● É o caso, por exemplo, do acesso direto a um elemento de uma matriz.
● Representamos: O (1)
71/209
Ordens de complexidade (cont.)
72/209
Ordens de complexidade (cont.)
● Ordens de complexidade
73/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
74/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● O volume de operações cresce na proporção ao log n do tamanho do problema.
75/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● O volume de operações cresce na proporção ao log n do tamanho do problema.
● O crescimento do número de operações é menor do que o do número de itens.
76/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● O volume de operações cresce na proporção ao log n do tamanho do problema.
● O crescimento do número de operações é menor do que o do número de itens.
● É o caso, por exemplo, de algoritmos de busca em árvores binárias ordenadas (Binary Search Trees).
77/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● O volume de operações cresce na proporção ao log n do tamanho do problema.
● O crescimento do número de operações é menor do que o do número de itens.
● É o caso, por exemplo, de algoritmos de busca em árvores binárias ordenadas (Binary Search Trees).
● Representamos: O (log n)
78/209
Ordens de complexidade (cont.)
79/209
Ordens de complexidade (cont.)
● Ordens de complexidade
80/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
81/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● Árvores binárias ordenadas (Binary Search Trees).
82/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Logaritmo
● Árvores binárias ordenadas (Binary Search Trees).
83/209
Ordens de complexidade (cont.)
84/209
Ordens de complexidade (cont.)
● Ordens de complexidade
85/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Linear
86/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Linear
● O crescimento do número de operações cresce na proporção direta do crescimento do tamanho do problema.
87/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Linear
● O crescimento do número de operações cresce na proporção direta do crescimento do tamanho do problema.
● É o caso de algoritmos de busca em um vetor não ordenado.
88/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Linear
● O crescimento do número de operações cresce na proporção direta do crescimento do tamanho do problema.
● É o caso de algoritmos de busca em um vetor não ordenado.
● Representamos: O (n)
89/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Linear
● O crescimento do número de operações cresce na proporção direta do crescimento do tamanho do problema.
● É o caso de algoritmos de busca em um vetor não ordenado.
● Representamos: O (n)
90/209
Ordens de complexidade (cont.)
91/209
Ordens de complexidade (cont.)
● Ordens de complexidade
92/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Sub-quadrático (ou super-linear)
93/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Sub-quadrático (ou super-linear)
● É o caso, por exemplo, do algoritmo de ordenação Quicksort. Ele tem essa complexidade no caso médio.
94/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Sub-quadrático (ou super-linear)
● É o caso, por exemplo, do algoritmo de ordenação Quicksort. Ele tem essa complexidade no caso médio.
● Representamos: O (n log n)
95/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Sub-quadrático (ou super-linear)
● É o caso, por exemplo, do algoritmo de ordenação Quicksort. Ele tem essa complexidade no caso médio.
● Representamos: O (n log n)
96/209
Ordens de complexidade (cont.)
97/209
Ordens de complexidade (cont.)
● Ordens de complexidade
98/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
99/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
● O tempo de execução do algoritmo cresce a uma taxa de nk, onde k é uma constante maior do que 1. Exemplos: n², n³ etc.
100/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
● O tempo de execução do algoritmo cresce a uma taxa de nk, onde k é uma constante maior do que 1. Exemplos: n², n³ etc.
● n² e n³ são pertencem à mesma ordem de complexidade.
101/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
● O tempo de execução do algoritmo cresce a uma taxa de nk, onde k é uma constante maior do que 1. Exemplos: n², n³ etc.
● n² e n³ são pertencem à mesma ordem de complexidade.● São algoritmos factíveis, mas tendem a se tornar muito
ruins quando a quantidade de dados é suficientemente grande.
102/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
● O tempo de execução do algoritmo cresce a uma taxa de nk, onde k é uma constante maior do que 1. Exemplos: n², n³ etc.
● n² e n³ são pertencem à mesma ordem de complexidade.● São algoritmos factíveis, mas tendem a se tornar muito
ruins quando a quantidade de dados é suficientemente grande.
● É o caso de algoritmos que têm dois laços encadeados. Exemplo: processamento de uma matriz bidimensional.
103/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Polinomial
● O tempo de execução do algoritmo cresce a uma taxa de nk, onde k é uma constante maior do que 1. Exemplos: n², n³ etc.
● n² e n³ são pertencem à mesma ordem de complexidade.● São algoritmos factíveis, mas tendem a se tornar muito
ruins quando a quantidade de dados é suficientemente grande.
● É o caso de algoritmos que têm dois laços encadeados. Exemplo: processamento de uma matriz bidimensional.
● Representamos: O (nk)
104/209
Ordens de complexidade (cont.)
105/209
Ordens de complexidade (cont.)
● Ordens de complexidade
106/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Exponencial
107/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Exponencial
● É o tipo de algoritmo que não consegue executar problemas grandes.
108/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Exponencial
● É o tipo de algoritmo que não consegue executar problemas grandes.
● É o caso de algoritmos que fazem busca em árvores binárias não ordenadas.
109/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Exponencial
● É o tipo de algoritmo que não consegue executar problemas grandes.
● É o caso de algoritmos que fazem busca em árvores binárias não ordenadas.
● Representamos: O (2n)
110/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Exponencial
● É o tipo de algoritmo que não consegue executar problemas grandes.
● É o caso de algoritmos que fazem busca em árvores binárias não ordenadas.
● Representamos: O (2n)
111/209
Ordens de complexidade (cont.)
112/209
Ordens de complexidade (cont.)
● Ordens de complexidade
113/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Fatorial
114/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Fatorial
● O número de instruções executadas cresce muito rapidamente para um pequeno número de itens processados.
115/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Fatorial
● O número de instruções executadas cresce muito rapidamente para um pequeno número de itens processados.
● Exemplo: problema do caixeiro viajante.
116/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Fatorial
● O número de instruções executadas cresce muito rapidamente para um pequeno número de itens processados.
● Exemplo: problema do caixeiro viajante.
117/209
Ordens de complexidade (cont.)
● Ordens de complexidade– Fatorial
● O número de instruções executadas cresce muito rapidamente para um pequeno número de itens processados.
● Exemplo: problema do caixeiro viajante.● Representamos: O (n!)
118/209
Ordens de complexidade (cont.)
119/209
Ordens de complexidade (cont.)
120/209
Ordens de complexidade (cont.)
121/209
Notação Big-O
122/209
Notação Big-O
● A quantidade de trabalho (“work”, “job”) em um algoritmo tipicamente é a soma de vários termos em um polinômio.
123/209
Notação Big-O
● A quantidade de trabalho (“work”, “job”) em um algoritmo tipicamente é a soma de vários termos em um polinômio.– Nós focamos o termo chamado de dominante.
124/209
Notação Big-O
● A quantidade de trabalho (“work”, “job”) em um algoritmo tipicamente é a soma de vários termos em um polinômio.– Nós focamos o termo chamado de dominante.
● Como n se torna grande, o termo dominante se torna tão grande que a quantidade de trabalho representada pelos demais termos pode ser ignorada.
125/209
Notação Big-O
● A quantidade de trabalho (“work”, “job”) em um algoritmo tipicamente é a soma de vários termos em um polinômio.– Nós focamos o termo chamado de dominante.
● Como n se torna grande, o termo dominante se torna tão grande que a quantidade de trabalho representada pelos demais termos pode ser ignorada.– Chamamos isso de análise assintótica.
126/209
Notação Big-O
● A quantidade de trabalho (“work”, “job”) em um algoritmo tipicamente é a soma de vários termos em um polinômio.– Nós focamos o termo chamado de dominante.
● Como n se torna grande, o termo dominante se torna tão grande que a quantidade de trabalho representada pelos demais termos pode ser ignorada.– Chamamos isso de análise assintótica.
● Notação Big-O: utilizada para expressar a eficiência ou complexidade computacional de um algoritmo.
127/209
O papel da constante de proporcionalidade
128/209
O papel da constante de proporcionalidade
● A constante de proporcionalidade envolve os termos e coeficientes que são geralmente ignorados durante a análise de complexidade (Big-O).
129/209
O papel da constante de proporcionalidade
● A constante de proporcionalidade envolve os termos e coeficientes que são geralmente ignorados durante a análise de complexidade (Big-O).– Porém, quando esses itens são grandes, eles
podem ter um impacto no algoritmo, especialmente quando lidamos com conjunto de dados de tamanho pequeno ou médio.
130/209
Algoritmos de Busca
131/209
Algoritmos de Busca
● Nós agora apresentamos alguns algoritmos que podem ser usados para busca e ordenação de listas (ou vetores).
132/209
Algoritmos de Busca
● Nós agora apresentamos alguns algoritmos que podem ser usados para busca e ordenação de listas (ou vetores).– Nós iniciaremos com a discussão sobre projeto de
um algoritmo.
133/209
Algoritmos de Busca
● Nós agora apresentamos alguns algoritmos que podem ser usados para busca e ordenação de listas (ou vetores).– Nós iniciaremos com a discussão sobre projeto de
um algoritmo.– Então nós mostraremos a sua implementação
como uma função de Python.
134/209
Algoritmos de Busca
● Nós agora apresentamos alguns algoritmos que podem ser usados para busca e ordenação de listas (ou vetores).– Nós iniciaremos com a discussão sobre projeto de
um algoritmo.– Então nós mostraremos a sua implementação
como uma função de Python.– Finalmente, nós faremos uma análise da
complexidade computacional dos algoritmos.
135/209
Algoritmos de Busca
● Nós agora apresentamos alguns algoritmos que podem ser usados para busca e ordenação de listas (ou vetores).– Nós iniciaremos com a discussão sobre projeto de um
algoritmo.– Então nós mostraremos a sua implementação como uma
função de Python.– Finalmente, nós faremos uma análise da complexidade
computacional dos algoritmos.● Por questão de organização da aula, cada função
processará uma lista de inteiros.
139/209
Busca pelo Mínimo
140/209
Busca pelo Mínimo
● A função min() de Python retorna a posição do menor item de uma lista.
141/209
Busca pelo Mínimo
● A função min() de Python retorna a posição do menor item de uma lista.
142/209
Busca pelo Mínimo
● A função min() de Python retorna a posição do menor item de uma lista.
143/209
Busca pelo Mínimo
● A função min() de Python retorna a posição do menor item de uma lista.
● n - 1 comparações para uma lista de tamanho n
144/209
Busca pelo Mínimo
● A função min() de Python retorna a posição do menor item de uma lista.
● n - 1 comparações para uma lista de tamanho n● O (n)
145/209
Melhor caso, pior caso e caso médio
146/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:
147/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
148/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.
149/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
150/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
– Melhor caso.
151/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
– Melhor caso. ● O item é o primeiro da lista.
152/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
– Melhor caso. ● O item é o primeiro da lista.● O(1)
153/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
– Melhor caso. ● O item é o primeiro da lista.● O(1)
– Caso médio.
154/209
Melhor caso, pior caso e caso médio
● A busca sequencial (linear) considera três casos:– Pior caso.
● O item está no final da lista ou não está na lista.● O(n)
– Melhor caso. ● O item é o primeiro da lista.● O(1)
– Caso médio. ● O(n)
155/209
Busca binária em uma lista
156/209
Busca binária em uma lista
● Uma busca linear (sequencial) é necessária se os dados não estão ordenados.
157/209
Busca binária em uma lista
● Uma busca linear (sequencial) é necessária se os dados não estão ordenados.
● Quando os dados já estão ordenados, podemos usar a busca binária.
158/209
Busca binária em uma lista
● Uma busca linear (sequencial) é necessária se os dados não estão ordenados.
● Quando os dados já estão ordenados, podemos usar a busca binária.
159/209
Busca binária em uma lista (cont.)
160/209
Busca binária em uma lista (cont.)
● Mais eficiente do que a busca linear.– Custo adicional para manter a lista ordenada.
161/209
Busca binária em uma lista (cont.)
● Mais eficiente do que a busca linear.– Custo adicional para manter a lista ordenada.
162/209
Algoritmos de Ordenação
163/209
Algoritmos de Ordenação
● A função de ordenação que desenvolvemos aqui opera sobre uma lista de inteiros e utiliza uma função swap para trocar as posições de dois elementos da lista.
164/209
Algoritmos de Ordenação
● A função de ordenação que desenvolvemos aqui opera sobre uma lista de inteiros e utiliza uma função swap para trocar as posições de dois elementos da lista.
165/209
Algoritmo de Seleção (ordenação)
166/209
Algoritmo de Seleção (ordenação)
● Talvez a mais simples estratégia é pesquisar na lista pela posição do menor item.– Se a posição não for igual à primeira posição, o
algoritmo troca (swap) os itens nessas posições.
167/209
Algoritmo de Seleção (ordenação)
● Talvez a mais simples estratégia é pesquisar na lista pela posição do menor item.– Se a posição não for igual à primeira posição, o
algoritmo troca (swap) os itens nessas posições.
168/209
Algoritmo de Seleção (cont.)
169/209
Algoritmo de Seleção (cont.)
● O algoritmo de seleção é O(n²) em todos os casos.
170/209
Algoritmo de Seleção (cont.)
● O algoritmo de seleção é O(n²) em todos os casos.
● Para grandes conjuntos de dados, o custo de trocar os elementos pode também ser significativo.
171/209
Algoritmo de Seleção (cont.)
● O algoritmo de seleção é O(n²) em todos os casos.
● Para grandes conjuntos de dados, o custo de trocar os elementos pode também ser significativo.
172/209
Algoritmo da Bolha
173/209
Algoritmo da Bolha
● Começa no início da lista e compara pares de itens conforme percorre a lista.
174/209
Algoritmo da Bolha
● Começa no início da lista e compara pares de itens conforme percorre a lista.– Quando pares de itens estão fora de ordem, ele faz
a troca dos itens.
175/209
Algoritmo da Bolha
● Começa no início da lista e compara pares de itens conforme percorre a lista.– Quando pares de itens estão fora de ordem, ele faz
a troca dos itens.
176/209
Algoritmo da Bolha (cont.)
177/209
Algoritmo da Bolha (cont.)
● Algoritmo como uma função:
178/209
Algoritmo da Bolha (cont.)
● Algoritmo como uma função:
179/209
Algoritmo da Bolha (cont.)
180/209
Algoritmo da Bolha (cont.)
● Algoritmo da Bolha é O(n²).
181/209
Algoritmo da Bolha (cont.)
● Algoritmo da Bolha é O(n²).● Ele não fará trocas se a lista já estiver
ordenada.
182/209
Algoritmo da Bolha (cont.)
● Algoritmo da Bolha é O(n²).● Ele não fará trocas se a lista já estiver
ordenada.● O comportamento para o pior caso para as
trocas (swap) é muito maior que linear.
183/209
Algoritmo da Bolha (cont.)
● Algoritmo da Bolha é O(n²).● Ele não fará trocas se a lista já estiver
ordenada.● O comportamento para o pior caso para as
trocas (swap) é muito maior que linear.● Pode ser melhorado, mas o caso médio ainda
será O(n²).
184/209
Algoritmo de Inserção
● O pior caso do algoritmo é O(n²).
185/209
Algoritmo de Inserção (cont.)
186/209
Algoritmo de Inserção (cont.)
187/209
Algoritmo de Inserção (cont.)
● Quanto mais ordenada estiver a lista de entrada, mais eficiente será o algoritmo.
188/209
Algoritmo de Inserção (cont.)
● Quanto mais ordenada estiver a lista de entrada, mais eficiente será o algoritmo.
● No melhor caso, quando a lista está ordenada, o algoritmo de ordenação tem complexidade linear.
189/209
Algoritmo de Inserção (cont.)
● Quanto mais ordenada estiver a lista de entrada, mais eficiente será o algoritmo.
● No melhor caso, quando a lista está ordenada, o algoritmo de ordenação tem complexidade linear.
● No caso médio, o algoritmo de inserção ainda é quadrático.
190/209
Melhor caso, pior caso e caso médio
191/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:
192/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:– Melhor caso.
193/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:– Melhor caso.– Pior caso.
194/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:– Melhor caso.– Pior caso.– Caso médio.
195/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:– Melhor caso.– Pior caso.– Caso médio.
● Existem algoritmos cuja performace do melhor caso e do caso médio sejam similares, mas a eficiência pode cair significativamente no pior caso.
196/209
Melhor caso, pior caso e caso médio
● Através da análise de complexidade de um algoritmo, o seu comportamento pode ser analisado como:– Melhor caso.– Pior caso.– Caso médio.
● Existem algoritmos cuja performace do melhor caso e do caso médio sejam similares, mas a eficiência pode cair significativamente no pior caso.
● Quando nós desenvolvemos algoritmos, é importante estarmos cientes dessas distinções.
197/209
Fibonacci Recursivo: um algoritmo exponencial
198/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
199/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
● Algoritmos exponenciais são geralmente impraticáveis de serem usados, mesmo com pequeno conjunto de dados de entrada.
200/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
● Algoritmos exponenciais são geralmente impraticáveis de serem usados, mesmo com pequeno conjunto de dados de entrada.
● Funções recursivas que são chamadas repetidamente com os mesmos argumentos podem ser mais eficientemente utilizadas através de uma técnica chamada de memoization.
201/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
202/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
● Técnica de memoization:
203/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
● Técnica de memoization:– O programa mantém uma tabela de valores para
cada argumento usado com a função.
204/209
Fibonacci Recursivo: um algoritmo exponencial (cont.)
● Técnica de memoization:– O programa mantém uma tabela de valores para
cada argumento usado com a função.– Antes da função recursivamente processar um
valor para um dado argumento, ele checa a tabela para ver se o argumento já tem um valor.
205/209
Convertendo o Fibonnaci para um algoritmo linear
Pseudocode:Set sum to 1
Set first to 1
Set second to 1
Set count to 3
While count <= N
Set sum to first + second
Set first to second
Set second to sum
Increment count
206/209
Convertendo o Fibonnaci para um algoritmo linear (cont.)
207/209
Notação Omega (Ω))
● A notação Omega (Ω)) descreve o limite inferior dos algoritmos.
● Essa notação é empregada para medir o melhor caso do algoritmo.
208/209
Notação Theta (Θ))
● É frequentemente o caso onde os limites superior e inferior de uma dada função são iguais.
209/209
Resumo
210/209
Resumo
● Diferentes algoritmos podem ser ranqueados de acordo com os recursos de tempo e memória que eles exigem para rodar.
211/209
Resumo
● Diferentes algoritmos podem ser ranqueados de acordo com os recursos de tempo e memória que eles exigem para rodar.
● Tempo de execução de um algoritmo pode ser medido empiricamente utilizando o clock do computador.
212/209
Resumo
● Diferentes algoritmos podem ser ranqueados de acordo com os recursos de tempo e memória que eles exigem para rodar.
● Tempo de execução de um algoritmo pode ser medido empiricamente utilizando o clock do computador.
● A contagem das instruções de um algoritmo fornece uma medida da quantidade de trabalho que o algoritmo faz.
213/209
Resumo
● Diferentes algoritmos podem ser ranqueados de acordo com os recursos de tempo e memória que eles exigem para rodar.
● Tempo de execução de um algoritmo pode ser medido empiricamente utilizando o clock do computador.
● A contagem das instruções de um algoritmo fornece uma medida da quantidade de trabalho que o algoritmo faz.
● A taxa de crescimento de trabalho de um algoritmo pode ser representada como uma função do tamanho das instâncias do problema (tamanho da entrada).
214/209
Resumo
● Diferentes algoritmos podem ser ranqueados de acordo com os recursos de tempo e memória que eles exigem para rodar.
● Tempo de execução de um algoritmo pode ser medido empiricamente utilizando o clock do computador.
● A contagem das instruções de um algoritmo fornece uma medida da quantidade de trabalho que o algoritmo faz.
● A taxa de crescimento de trabalho de um algoritmo pode ser representada como uma função do tamanho das instâncias do problema (tamanho da entrada).
● A notação Big-O é uma forma comum de expressar um comportamento do tempo de execução de um algoritmo.
215/209
Resumo (cont.)
216/209
Resumo (cont.)
● Classes comuns do tempo de execução de algoritmos são: O(log2n), O(n), O(n2), and O(kn).
217/209
Resumo (cont.)
● Classes comuns do tempo de execução de algoritmos são: O(log2n), O(n), O(n2), and O(kn).
● Um algoritmo pode ter diferenças de eficiência no melhor, pior e caso médio.
218/209
Resumo (cont.)
● Classes comuns do tempo de execução de algoritmos são: O(log2n), O(n), O(n2), and O(kn).
● Um algoritmo pode ter diferenças de eficiência no melhor, pior e caso médio.
● A busca binária é muito mais rápida do que a busca linear. Porém, os dados devem estar ordenados.
219/209
Resumo (cont.)
● Classes comuns do tempo de execução de algoritmos são: O(log2n), O(n), O(n2), and O(kn).
● Um algoritmo pode ter diferenças de eficiência no melhor, pior e caso médio.
● A busca binária é muito mais rápida do que a busca linear. Porém, os dados devem estar ordenados.
● Algoritmos exponenciais são impraticáveis de serem usados para grandes conjuntos de dados.
