.. -*- coding: utf-8 -*- .. |Python| replace:: ``Python`` .. |IPython| replace:: ``IPython`` .. |PythonAnywhere| replace:: `PythonAnywhere `__ .. |RST| replace:: `reST `__ .. |Sphinx| replace:: `Sphinx `__ .. |HTML| replace:: ``HTML`` .. |Trinket| replace:: `Trinket `__ .. |Colab| replace:: `Google Colab `__ .. |Replit| replace:: `Replit `__ .. |Runestone| replace:: `Runestone `__ .. |cscircles| replace:: ``cscircles`` .. |fazsentido| replace:: Faz sentido? ``¯\_(ツ)_/¯`` .. |SURPRESO| replace:: ``(☉_☉)`` .. |TRISTE| replace:: ``(⊙︿⊙)`` .. |HEIN| replace:: ``¯\_(ツ)_/¯`` .. |HELP| replace:: ``(҂◡_◡)`` .. |VALEU| replace:: ``\(•◡•)/`` .. |CONFUSO| replace:: ``ఠ_ఠ`` .. |LOUCO| replace:: ``(⊙_◎)`` .. |TRISTE| replace:: ``(ಥ﹏ಥ)`` .. |ENTER| replace:: ``ENTER`` .. |Return| replace:: ``Return`` .. |Forward| replace:: ``Forward >`` .. |Last| replace:: ``Last >>`` .. |First| replace:: ``<< First`` .. |Back| replace:: ``< Back`` .. |Run| replace:: ``Run`` Algoritmos no divã =================== No nosso estudo continuaremos a ter dicionários e suas aplicações como pano de fundo para explorarmos o universo dos algoritmos. Estruturas de dados, como dicionários, são diariamente aplicadas para o armazenamento de informação que posteriormente são consultadas. É de interesse que as consultas sejam respondidas rapidamente. Cada mecanismo de armazenamento e busca tem suas vantagens e desvantagem. Dependendo da aplicação, os dados são mantidos respeitando alguma ordem e essa ordenação pode ser explorada durante as consultas. Nesse capítulo nos aprofundaremos em métodos para estimativa dos recursos computacionais utilizados por funções e algoritmos. Traremos, por assim dizer, os algoritmos para o divã para analisá-los com mais cuidado. Esse tópico e comumente chamado de `análise de algoritmos `_. .. image:: ./imgs/cs161logo.* :width: 542 :height: 535 :scale: 60 :alt: CS 161 - Design and Analysis of Algorithms :align: center :target: http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms Destino ------- Entraremos agora nos domínios da análise de algoritmos. |:nerd:| Praticaremos a análise experimental de algoritmos e as técnicas cotidianamente utilizadas para estimar o tempo gasto e espaço consumido por programas, especialmente o tempo gasto. Essas análises nos farão compreender os pontos fortes, fracos e os limites dos nossos programas. .. index:: pior caso .. index:: melhor caso .. index:: caso médio É comum examinarmos as situações que em que um algoritmo ou função requer mais tempo |:timer_clock:| ou espaço de armazenamento ou de memória |:memo:|. Chamamos essas situações de **pior caso** |:pensive:|. Quando investigamos a situação em que um algoritmo ou função requer poucos recursos, seja em termos de tempo ou espaço consumido, estaremos falando do desempenho de **melhor caso** |:smile:|. Muitas vezes também é de interesse saber o desempenho médio do algoritmo ou função que podem estar mais próximos da prática do dia a dia. Essa é a chamada análise de **caso médio** |:confused:|. .. image:: ./imgs/casos.* :width: 947 :height: 622 :scale: 50 :alt: pior caso, caso médio e melhor caso :align: center Do ponto de vista de ideias, é importante compreender que decisões de projeto frequentemente tem seus pontos positivos e negativos. Tentem praticar o senso crítico considerando as vantagens e desvantagens da `busca sequencial `_, da `busca em listas ordenadas `_ e da `busca binária `_. Revisitaremos os algoritmos o problema do máximo divisor comum vistos na seção :ref:`my_Euclides`. Procurem habituar-se a linguagem usada por manuais para expressar o consumo de tempo de funções e métodos através da `notação assintótica `_, como na wiki `TimeComplexity `_. Busquem nos experimentos evidências para comprovar ou contestar as nossas expectativas, as nossas estimativas analíticas, teóricas. Todos os algoritmos que estudaremos, entre eles a `ordenação por inserção `_, serão um imenso laboratório de ideias. .. _my_BuscasEmListas: Buscas em listas ---------------- Para aquecer os nossos motores ... **Problema (busca)**: Dado um objeto ``x`` e uma lista ``v[0:n]``, encontrar um índice ``i`` tal que ``v[i] = x``. .. image:: ./imgs/busca_exemplo.* :width: 847 :height: 243 :scale: 50 :alt: Exemplo de instância para a busca :align: center Nos exemplos a seguir, uma lista é formada por objetos ``int``, no entanto poderiam ser objetos de qualquer classe. O importante é que todos os elementos de ``v`` sejam comparáveis entre si. Uma maneira de resolvermos esse problema é através de uma **busca sequencial**: percorremos a lista examinando seus elementos um a um, do início até o fim |:fast_forward:| ou do fim até o início |:back:|. .. code-block:: python def sequencial(v, x): ''' (list, obj) -> int or None RECEBE uma lista v e um objeto x. RETORNA o menor índice i tal que v[i] == x. Se o x não está na lista a função retorna None. ''' 0 n = len(v) 1 for i in range(n): #1# 2 if x == v[i]: return i 3 return None A numeração das linhas não faz parte dos código e só está ai para efeito de referência. .. index:: invariantes .. index:: relações invariantes Passamos agora a verificação de que a função ``sequencial()`` está correta. Estar correta significa que a função funciona, faz o que promete. A correção de algoritmos iterativos é comumente baseada na verificação da validade de **invariantes**. Estes invariantes são afirmações ou **relações** envolvendo os objetos mantidos pela função. Em ``#1#`` no início de cada iteração vale que ``val != x`` para todo ``val`` em ``v[0:i]``. No início da última iteração vale que ou ``x == v[i]`` e a função retorna o índice ``i``, ou que percorremos todos os elementos de ``v`` e a função retorna ``None`` pois ``x`` não está na lista. Logo, a função retorna uma resposta correta. |:thinking:| Relações invariantes, com a que apresentada acima envonvendo os objetos ``val``, ``x`` e ``v[0:i]``, além de serem uma ferramente útil para demonstrarmos a correção de algoritmos iterativos, elas nos ajudam a compreender o funcionamento do algoritmo. De certa forma, no fundo no fundo, as relações invariantes espelham a maneira que entendemos e concebemos o algoritmo. Bem , passemos a tratar do consumo de tempo |:timer_clock:| de ``sequencial()``. Para estimarmos o consumo de tempo da função suporemos que o consumo de tempo de cada execução de uma linha é constante, digamos, 1 unidade de tempo. A tabela abaixo resumo o consumo de tempo máximo |:clock10:| de cada linha. .. math:: \begin{array}{cl} \text{linha} & \text{consumo de tempo total das execuções da linha}\\ \hline 0 &= \mathtt{1} \\ 1 &\leq \mathtt{n+1 \approx n} \\ 2 &\leq \mathtt{n} \\ 3 &\leq \mathtt{1} \\ \hline \rule[0ex]{0ex}{3ex}% \text{total} &\mathtt{\leq 2\;n+3 = \textup{O}(n)} \end{array} .. index:: pior caso .. index:: melhor caso .. index:: consumo de tempo constante Essa análise é de **pior caso** pois estamos estimando o maior número possível de linhas que podem ser executadas. **Conclusão**. O consumo de tempo da função ``busca_sequecial()`` é no **pior caso** proporcional ao número de elementos ``n`` da lista ``v``. No **melhor caso**, quando a função trabalha pouco, ``x`` é um elemento logo no início da lista e o tempo gasto passa a independer do número ``n`` de elementos. Nesse caso dizemos que o **consumo de tempo é constante** já que **independe** do volume de dados. Realizando experimentos vemos que, à medida que o tamanho da lista dada dobra, o consumo de tempo aproximadamente dobra. Esse é o comportamento esperado por uma função que possui consumo de tempo linearmente proporcional a :math:`\mathtt{n}`. Os tempos na tabela abaixo e os testes foram feitos com buscas **bem-sucedidas**, onde o elemento procurado estava na lista. Esse elemento foi sorteado dentre os elementos da lista. :: Testes apenas para buscas BEM-SUCEDIDAS: x está em v n busca_sequencial 1024 0.00 2048 0.00 4096 0.00 8192 0.00 16384 0.00 32768 0.00 65536 0.00 131072 0.01 262144 0.01 524288 0.03 1048576 0.05 2097152 0.10 4194304 0.20 8388608 0.40 16777216 0.83 33554432 1.61 Buscas em listas ordenadas -------------------------- Dizemos que uma lista :math:`\mathtt{v[0:n]}` é **crescente** se .. math:: \mathtt{v[0] \leq v[1] \leq v[2] \leq \cdots \leq v[n{-}1].} Passemos a pensar sobre o seguinte problema de busca. **Problema (busca em lista ordenada)**: Dado um objeto ``x`` e um lista *crescente* ``v[0:n]`` encontrar um índice ``i`` tal que ``v[i] = x``. Nos exemplos a seguir, uma lista é formada de objetos ``int``, no entanto poderiam ser objetos de qualquer classe. O importante é que os elementos de ``v`` sejam comparáveis entre si (ou seja, dois a dois) .. image:: ./imgs/busca_ordenada_exemplo1.* :width: 834 :height: 242 :scale: 50 :alt: Exemplo de instância para a busca ordenada :align: center .. image:: ./imgs/busca_ordenada_exemplo2.* :width: 824 :height: 251 :scale: 50 :alt: Outro exemplo de instância para a busca ordenada :align: center Podemos adaptar a **busca sequencial** para tirar proveito da ordenação dos elementos da lista. Na função a seguir, os números indicando a linha não fazem parte do código e servem de rótulos para que possamos referi-las. .. code:: python def buscaA(v, x): ''' (list, obj) -> int or None RECEBE uma lista v e um objeto x. RETORNA o menor índice i tal que v[i] == x. Se o x não está na lista a função retorna None. PRÉ-CONDIÇÃO: supõe que a lista é crescente. ''' 0 n = len(v) 1 i = 0 2 while i < n and x > v[i]: #1# 3 i += 1 4 if i < n and v[i] == x: 5 return i 6 return None Abaixo está uma simulação da função ``busca_sequencial()`` .. image:: ./imgs/busca_seq1.* :width: 857 :height: 650 :scale: 50 :alt: Simulação busca sequencial em lista ordenada :align: center .. image:: ./imgs/busca_seq2.* :width: 846 :height: 532 :scale: 50 :alt: Fim da simulação em lista ordenada :align: center O funcionamento da função se baseia no fato de que, em ``#1#`` vale que ``v[i-1] < x``. Como a lista é crescente, então ``val < x`` para todo ``val in v[0:i]``. No início da última iteração temos que ou ``i >= n`` ou ``v[i] >= x``. Assim, na linha 6, se a função retorna um índice ``i``, então ``v[i] == x``. Por outro, se ``i == n`` ou ``v[i] > x``, a função acertadamente retorna ``None`` na linha 7 e já que nesse ponto do código temos provas cabais de que ``x`` não tem a menor chance de estar na lista. Para analisarmos o consumo de tempo da função ``buscaA()`` suporemos que a execução de cada linha consome uma quantidade de tempo limitada por uma constante, como 1 microsegundo, :math:`1 \mu` s. Equivalentemente, podemos supor que a execução de cada linha consome 1 unidade de tempo. Dessa forma o tempo total é mostrado na tabela a seguir. .. math:: \begin{array}{cl} \text{linha} & \text{todas as execuções da linha}\\ \hline 0{-}1 &= \mathtt{1} \\ 2 &\leq \mathtt{n+1} \hfill { \approx n} \\ 3 &\leq \mathtt{n} \\ 4 &= \mathtt{1} \\ 5 &\leq \mathtt{1} \\ 6 &\leq \mathtt{1} \\ \hline \rule[0ex]{0ex}{3ex}% { \text{total}} &\leq \mathtt{2\;n+5} {\mathtt{= \textup{O}(n)}} \end{array} Na tabela, não se preocupe com a parte do :math:`\mathtt{= \textup{O}(n)}`, que ficará mais clara mais adiante. **Conclusão**. O consumo de tempo da função ``buscaA()`` é no **pior caso** proporcional ao número de elementos ``n`` da lista ``v``. Examinando o código da função ``buscaA()`` percebemos que para buscas **malsucedidas**, quando o objeto ``x`` não está na lista, ``buscaA()`` pode consumir mais tempo que uma busca sequencial ordinária. Considere a situação em que ``x`` não está na lista ``v`` e ``x`` é maior que todo elemento em ``v``. Nesse cenário ``buscaA()`` faz o mesmo número de passos que a busca sequencial e, em cada passo, faz uma comparação a mais. Realizando alguns experimentos de buscas **bem-sucedidas**, ou seja, o objeto ``x`` sendo procurado estava na lista, obtivemos a seguinte tabela de tempos. Para valores suficientemente grandes é possível ver que, quando ``n`` dobra, o tempo consumido também aproximadamente dobra. Esse é um sintoma típico de funções que tem seu consumo de tempo proporcional a ``n``: se ``n`` dobra então o consumo de tempo aproximadamente dobra. A tabela a seguir mostra resultados de experimentos feitos com a função ``buscaA()``. :: Testes apenas para buscas BEM-SUCEDIDAS: x está em v n buscaA 1024 0.00 2048 0.00 4096 0.00 8192 0.00 16384 0.00 32768 0.00 65536 0.00 131072 0.01 262144 0.01 524288 0.03 1048576 0.05 2097152 0.10 4194304 0.20 8388608 0.41 16777216 0.83 33554432 1.66 Busca binária ------------- Quando fazemos busca em listas ordenadas o método de escolha é a busca binária. Essa busca se apoia em um princípio bem simples. Se ``v[e:d]`` é uma lista crescente e ``v[i] < x`` para algum ``i`` em ``range(e,d)``, então não precisamos nos preocupar com ``x`` em ``v[i+1:d]``. De maneira semelhante, ``v[i] > x``, então não precisamos nos preocupar com ``x`` em ``v[e:i]``. .. code:: python def busca_bin(v, x): ''' (list, obj) -> int ou None RECEBE uma lista v e um objeto x. RETORNA um índice i tal que v[i] == x. Se o x não está na lista a função retorna None. PRÉ-CONDIÇÃO: supõe que a lista é crescente. ''' 0 n = len(v) 1 e = 0 2 d = n 3 while e < d: #1# 4 m = (e + d) // 2 5 if v[m] == x: return m 6 if v[m] < x: e = m + 1 7 else: d = m 8 return None A seguir está uma simulação que mostra a busca binária em ação. .. image:: ./imgs/busca_bin1.* :width: 868 :height: 646 :scale: 50 :alt: Simulação da busca binária :align: center .. image:: ./imgs/busca_bin2.* :width: 825 :height: 449 :scale: 50 :alt: Segunda parte da simulação da busca binária :align: center .. image:: ./imgs/busca_bin3.* :width: 841 :height: 368 :scale: 50 :alt: Epílogo da simulação da busca binária :align: center A correção da função ``busca_bin()`` se apoia na seguinte relação invariante chave: em ``#1#`` vale que: * ``val < x`` para todo valor ``val`` em ``v[0:e]`` e * ``x < val`` para todo valor ``val`` em ``v[d:n]``. Essa relação vale na primeira iteração se concordarmos em interpretar ``val`` na lista vazia ``v[0:0]`` como sendo :math:`-\infty` e ``val`` na lista vazia ``v[n:n]`` como sendo :math:`+\infty`. Se ``x`` não está em ``v``, então no início da última iteração das linhas 3 a 7 teremos que ``e == d``. Portanto, da relação invariante, ``x`` será um valor maior que todo elemento em ``v[0:e]`` e menor que todo elemento em ``v[e:n]``. Isso mostra que ``x`` não está em ``v`` e a função acertadamente retorna ``None`` na linha 8. No que diz respeito ao consumo de tempo da função ``busca_bin()``, vemos que ele é proporcional ao número :math:`\mathtt{k}` de iterações das linhas 3 a 7. No início da primeira iteração tem-se que ``d-e = n``. Sejam .. math:: \mathtt{(e_0,d_0), (e_1,d_1), \ldots, (e_{k},d_{k})}, os valores das variáveis ``e`` e ``d`` no início de cada uma das iterações. No **pior caso**, quando a função faz mais trabalho, ``x`` não está em ``v`` e, portanto, a busca é mal sucedida. Assim, :math:`\mathtt{d_{k-1} - e_{k-1} > 0}` e :math:`\mathtt{d_{k} - e_{k} \leq 0}`. Estimaremos o valor de :math:`\mathtt{k}` em função de :math:`\mathtt{d-e}`. Note que :math:`\mathtt{d_{i+1} - e_{i+1} \leq (d_{i}-e_{i}) / 2}` para :math:`\mathtt{i=1,2,\ldots,k-1}`. Desta forma temos que .. math:: \begin{array}{ccccccccccc} \mathtt{d_0-e_0} & = & \mathtt{n} &\leq& \mathtt{n} \\ \mathtt{d_1-e_1} &\leq& \mathtt{ (d_0 -e_0)/2} & \leq & \mathtt{n/2} \\ \mathtt{d_2-e_2 } &\leq& \mathtt{(d_1 -e_1)/2} & \leq & \mathtt{(n/2)/2} &=& \mathtt{n/{ 2^2}} \\ \mathtt{d_3-e_3 } &\leq& \mathtt{(d_2 -e_2)/2} & \leq & \mathtt{(n/2^2)/2} &=& \mathtt{n/{ 2^3}} \\ \mathtt{d_4-e_4 } &\leq& \mathtt{(d_3 -e_3)/2} & \leq & \mathtt{(n/2^3)/2} &=& \mathtt{n/{ 2^4}} \\ \mathtt{\vdots} & &\mathtt{\vdots} & & \mathtt{\vdots} & & \mathtt{\vdots} \\ \end{array} Observe que depois de cada iteração o valor de :math:`\mathtt{d-e}` é reduzido pela metade. Seja :math:`\mathtt{t}` o número inteiro tal que :math:`\mathtt{2^{t} \leq n < 2^{t+1}}`. Da primeira desigualdade temos que :math:`\mathtt{t \leq \lg n}`, em que :math:`\mathtt{\lg n}` é o logaritmo de :math:`\mathtt{n}` na base 2. Da desigualdade estrita, concluímos que .. math:: \begin{align*} \mathtt{0 < d_{k-1} - e_{k-1} \leq \underline{n}/2^{k-1} < \underline{2^{t+1}}/2^{k-1}}. \end{align*} Assim, em particular temos que .. math:: \begin{align*} 1 & \mathtt{\leq 2^{t+1}/2^{k-1}} \end{align*} ou, em outras palavras .. math:: \begin{align*} \mathtt{k} & \mathtt{\leq t+2}. \end{align*} Portanto , o número :math:`\mathtt{k}` de iterações é não superior a .. math:: \begin{align*} \mathtt{t + 2} & \mathtt{\leq \lg n + 2}. \end{align*} Chegamos portanto ao seguinte desfecho. **Conclusão**. O consumo de tempo da função ``busca_bin()`` é, **no pior caso**, proporcional a :math:`\mathtt{\lg n}`. A tabela a seguir mostra o possível número de iterações no **pior caso** das funções ``buscaA()``, que faz uma busca sequencial, e da ``busca_bin()``, que realiza uma busca binária. .. math:: \begin{array}{|c|c|} \hline \text{busca sequencial} & \text{busca binária} \\ \hline n & \lg n \\ \hline 256 & 8 \\ \hline 512 & 9 \\ \hline 1024 & 10 \\ \hline 2048 & 11 \\ \hline 4096 & 12 \\ \hline 8192 & 13 \\ \hline 16384 & 14 \\ \hline 32768 & 15 \\ \hline 65536 & 16 \\ \hline 131072 & 17 \\ \hline 262144 & 18 \\ \hline 524288 & 19 \\ \hline 1048576 & 20 \\ \hline \vdots & \vdots \\ \hline 4294967296 & 32 \\ \hline \end{array} Admiremos agora alguns resultados experimentais sobre listas de diferente tamanhos comparando os consumos de tempo de ``buscaA()`` e de ``busca_bin()``. :: Testes apenas para buscas BEM-SUCEDIDAS: x está em v n buscaA busca_bin 1024 0.00 0.00 2048 0.00 0.00 4096 0.00 0.00 8192 0.00 0.00 16384 0.00 0.00 32768 0.00 0.00 65536 0.00 0.00 131072 0.01 0.00 262144 0.01 0.00 524288 0.02 0.00 1048576 0.01 0.00 2097152 0.10 0.00 4194304 0.21 0.00 8388608 0.47 0.00 16777216 0.91 0.00 33554432 2.69 0.00 67108864 4.85 0.00 Como podemos observar o tempo gasto pela função ``busca_bin()`` é menor que o nosso padrão de medida com duas casas decimais e por isso todos são mostrado como :math:`\mathtt{0.00}`. Apesar da função ``busca_bin()`` não ser recursiva, a busca binária é *visceralmente* recursiva. A seguir está uma implementação recursiva da busca binária. Nesta versão ``busca_bin()`` é uma envoltória da função recursiva ``busca_binariaR()`` que faz todo o serviço. Essa envoltória faz o mesmo papel que vimos sendo desempenhado pelas funções ``fibonacciRM()`` e ``binomialRM()``, de *esconder* alguns parâmetros usados na recursão. .. code:: python def busca_bin(v, x): ''' (list, obj) -> int ou None RECEBE uma lista v e um objeto x. RETORNA um índice i tal que v[i] == x. Se o x não está na lista a função retorna None. PRÉ-CONDIÇÃO: supõe que a lista é crescente. ''' n = len(v) return busca_binariaR(v, x, 0, n) def busca_binariaR(v, x, e, d): ''' (lst, obj, e, d) -> int ou None RECEBE uma lista crescente v[e:d] e um objeto x. Retorna um índice m , e <= m < d tal que v[m] == x . Se tal m não existe, retorna None. PRÉ-CONDIÇÃO: supõe que v[e:d] é crescente. ''' if d <= e: return None m = (e + d) // 2 if v[m] == x: return m if v[m] < x: return busca_binariaR(v, x, m+1, d) return busca_binariaR(v, x, e, m) Ordenação por inserção ---------------------- Dizemos que uma lista :math:`\mathtt{v[0:n]}` é **crescente** se .. math:: \mathtt{v[0] \leq v[1] \leq v[2] \leq \cdots \leq v[n{-}1].} O problema que trataremos aqui será o de ordenar uma lista de elementos. **Problema (ordenação)**: Rearranjar os elementos de uma lista ``v[0:n]`` de modo que ela fique crescente. Nos exemplos as listas são de objetos ``int``, mas elas poderiam ser de ``str`` ou de quaisquer objetos que possam ser comparados com operadores relacionais como ``<``, ``<=``, ``>`` ou ``>=``. .. image:: ./imgs/ordenacao.* :width: 810 :height: 384 :scale: 50 :alt: Instância de ordenação :align: center O algoritmo que veremos aqui é **dinâmico** no sentido que ele é ideal para manter uma lista ordenada a medida que novos elemento são inseridos. A ideia chave do algoritmo é supor que temos uma lista `v` que já é crescente e desejamos **inserir** um novo elemento na lista mantendo-a crescente. O algoritmo é iterativo. No início de cada iteração um prefixo ``v[0:i]`` da lista ``v`` é crescente. A missão da iteração é rearranjar os elemento de ``v[0:i+1]`` para que esse prefixo seja crescente. O elemento da lista que terá um papel fundamental na iteração é ``x = v[i]``. Esse valor ``x`` é chamado de o **pivô da iteração**. Cada iteração será claramente dividida em duas fases: * na primeira fase o algoritmo procura um índice ``j`` em ``range(i)`` tal que ``v[j] <= x`` e ``x < v[j+1]`` * na segunda fase o pivô ``x`` é inserido na posição ``v[j+1]`` A seguir está a ilustração da simulação de uma iteração. .. image:: ./imgs/iteracao_insercao.* :width: 791 :height: 665 :scale: 50 :alt: insercão :align: center Na ilustração o prefixo crescente é ``v[0:6]`` e o pivô é ``x = 38`` que esta na posição ``v[6]``. Ao final da iteração o prefixo ``v[0:7]`` é crescente. A inserção na segunda fase é o que dá nome ao algoritmo de **ordenação por inserção**. Para inserir ``x`` na posição ``v[j+1]``, vários elementos devem ser **deslocados**. Algumas vezes esse deslocamento é feito durante a procura pelo índice ``j`` através de uma busca sequencial. .. code:: python # pivô x = v[i] # encontre a posição j através de busca sequencial j = i - 1 while j >= 0 and v[j] > x: v[j+1] = v[j] j -= 1 # insira x na posição que faz v[0:i+1] crescente v[j+1] = x Em outras ocasiões o deslocamento é feito depois que o índice ``j`` é encontrado. Essa é a política adotada quando usamos busca binária para encontrar o índice ``j``. Como ``v[0:i]`` é crescente podemos explorar a eficiência da busca binária para encontrar o índice ``j``. .. code:: python # pivô x = v[i] # encontre j através com busca binária j = busca_binaria(v, x, e=0, d=i) # desloque os elementos abrindo espaço para x for k in range(i, j+1, -1): v[k] = v[k-1] # insira x na posição que faz v[0:i+1] crescente v[j+1] = x A função completa é fornecida a seguir. .. code:: python def insercao(v): '''(list) -> None RECEBE uma lista v. REARRANJA os elementos de v para que fiquem em ordem crescente. NOTA. A função é mutadora. ''' 0 n = len(v) 1 for i in range(1, n): #1# # pivô 2 x = v[i] # encontre a posição j através de busca sequencial 3 j = i - 1 4 while j >= 0 and v[j] > x: 5 v[j+1] = v[j] 6 j -= 1 # insira x na posição que faz v[0:i+1] crescente 7 v[j+1] = x A relação invariante chave dessa função é a de que em ``#1#`` vale que ``v[0:i]`` é crescente. Isso vale na primeira iteração já que ``i = 1`` e ``v[0:1]`` é uma lista de apenas um elemento e, portanto, evidentemente crescente. A animação abaixo mostra a ordenação por inserção trabalhando. As alturas das barras indicam os valores dos elementos de ``v``, quanto maior a barra, maior o valor. As barras em cinza no início indicam o prefixo ``v[0:i]`` crescente. .. image:: ./imgs/ordenacao_por_insercao_aleatoria.* :width: 779 :height: 659 :scale: 50 :alt: Ordenação por inserção em sequencia aleatória :align: center Vamos estimar o consumo de tempo da função ``insercao()`` no **pior caso**. Para isso vamos supor que cada linha consome 1 unidade de tempo para estimar o número de linhas executadas. .. math:: \begin{array}{ll} \text{linha} & \text{todas as execuções da linha}\\ \hline 0 & = \mathtt{1} \\ 1 & = \mathtt{n} \\ 2 & = \mathtt{n-1} \\ 3 & = \mathtt{n-1} \\ 4 & \leq \mathtt{2+3+\cdots+n \ = \ (n-1)(n+2)/2} \\ 5 & \leq \mathtt{1+2+\cdots+(n{-}1) \ = \ n(n-1)/2}\\ 6 & \leq \mathtt{1+2+\cdots+(n{-}1) \ = \ n(n-1)/2}\\ 7 & = \mathtt{n-1}\\[2mm] \hline \rule[0ex]{0ex}{3ex}% {\text{total}} & \leq \mathtt{(3/2){ n^2} + (7/2)n - 5 = \textup{O}(n^2)} \end{array} O pior caso ocorre quando a função recebe uma lista ``v`` decrescente. **Conclusão**. O consumo de tempo da função ``insercao()`` é, no **pior caso**, proporcional a :math:`\mathtt{n}^2`, em que :math:`\mathtt{n}` é o número de elementos na lista ``v``. .. math:: \begin{array}{ll} \mbox{linha} & \text{todas as execuções da linha}\\ \hline 0 & = \mathtt{1}\\ 1 & = \mathtt{n} \\ 2 & = \mathtt{n-1} \\ 3 & = \mathtt{n-1} \\ 3 & = \mathtt{n-1} \\ 5 & = \mathtt{0}\\ 6 & = \mathtt{0}\\ 7 & = \mathtt{n-1}\\[2mm] \hline \rule[0ex]{0ex}{3ex}% {\text{total}} & = \mathtt{5n - 3 = \textup{O}(n)} \end{array} O melhor caso ocorre quando a função recebe uma lista ``v`` já ordenada, em ordem crescente, ou quando os elementos não estão muito distantes de suas posições na lista crescente. **Conclusão**. O consumo de tempo da função ``insercao()`` é, no **melhor caso**, proporcional a :math:`\mathtt{n}`, em que :math:`\mathtt{n}` é o número de elementos na lista ``v``. Vejamos alguns resultados experimentais envolvendo listas aleatórias, crescentes e decrescentes. Todos os tempos estão em segundos. .. math:: \begin{array}{|r|c|c|c|} \hline \mathtt{n}& \text{crescente} & \text{aleatória} & \text{decrescente}\\ \hline 256 & 0.00 & 0.00 & 0.01 \\ \hline 512 & 0.00 & 0.02 & 0.02 \\ \hline 1024 & 0.00 & 0.07 & 0.10 \\ \hline 2048 & 0.00 & 0.22 & 0.37 \\ \hline 4096 & 0.00 & 1.02 & 1.53 \\ \hline 8192 & 0.00 & 3.88 & 6.08 \\ \hline 16384 & 0.01 & 16.23 & 24.66 \\ \hline 32768 & 0.02 & 66.23 & 100.80 \\ \hline 65536 & 0.03 & 275.32 & 411.79 \\ \hline 131072 & 0.06 & 1158.06 & 1688.95 \\ \hline 262144 & 0.13 & 5119.28 & ? \\ \hline \end{array} A coluna com os consumos de tempo para ordenar listas crescentes mostra que os tempos dobram a medida que o número de elementos ``n`` da lista dobra. Esse é um sintoma de algoritmo que consomem tempo proporcional a :math:`\mathtt{n}`. A coluna com os consumos de tempo para ordenar lista aleatórias mostram que os tempos aproximadamente quadruplicam a medida que o número :math:`\mathtt{n}` de elementos da lista dobra. Essa é a características de algoritmo que consomem tempo proporcional a :math:`\mathtt{n^2}`. As animações abaixo mostram a ordenação por inserção trabalhando com listas crescentes e decrescentes. .. image:: ./imgs/ordenacao_por_insercao_crescente.* :width: 770 :height: 659 :scale: 50 :alt: Ordenação por inserção em sequencias crescentes :align: center .. image:: ./imgs/ordenacao_por_insercao_decrescente.* :width: 770 :height: 659 :scale: 50 :alt: Ordenação por inserção em sequencias decrescentes :align: center Revisita ao MDC --------------- Depois do que andamos vendo sobre análise de algoritmos vamos revisitar o problema pelo qual já passamos algumas vezes neste tesnto sendo que a última foi na seção :ref:`my_Euclides`: **Problema (máximo divisor comum)**: Dados dois números inteiros não-negativos ``a`` e ``b``, encontrar o máximo divisor comum de ``a`` e ``b``. .. index:: máximo divisor comum O **máximo divisor comum** de :math:`\mathtt{a}` e :math:`\mathtt{b}`, denotado por :math:`\mathtt{mdc(a,b)}`, é o maior inteiro positivo que é divisor comum de :math:`\mathtt{a}` e :math:`\mathtt{b}`. Por exemplo, o maior divisor comum de ``12`` e ``20`` é ``4`` pois ``4`` divide ``12`` e divide ``20`` e não há número inteiro maior que ``4`` que divida ambos, ``12`` e ``20``. Vamos investigar a eficiência de três funções que resolvem o problema do máximo divisor comum. |:detective_tone4:| Uma função que estará sob nossa lente de aumento |:mag_right:| será a ``euclideR()`` da seção :ref:`my_Euclides`. .. code-block:: python def euclidesR(a, b): """(int, int) -> int RECEBE dois inteiros a e b. RETORNA mdc(a, b); se a = 0 = b retorna 0 para indicar erro. PRÉ-CONDIÇÃO: a >= 0, b >=0 """ if b == 0: return a return euclidesR(b, a % b) A segunda será a ``math.gcd()`` da biblioteca ``math`` do |Python|. .. code-block:: python In [1]: import math In [2]: math.gcd(12, 20) Out[2]: 4 In [3]: math.gcd(539439, 2728) Out[3]: 1 In [4]: math.gcd(3447882627912, 17436306624) Out[4]: 6391608 Finalmente a terceira será a seguinte função ``mdc_tt()`` .. code-block:: python def mdc_tt(a, b) """(int, int) -> int RECEBE dois inteiros a e b. RETORNA o mdc de a e b. PRÉ-CONDIÇÃO: a > 0 e b > 0. """ 0 d = min(a, b) 1 while a % d != 0 or b % d != 0: 2 d -= 1 3 return d Os números nas linhas não fazem parte do código se só servem para fazermos referência às linhas. Suponha :math:`\mathtt{d = min(a,b)}`. A função ``mdc_tt()`` simplemente percorre os inteiros :math:`\mathtt{d}, \mathtt{d-1}, \mathtt{d-2}, \ldots` a procura do :math:`\mathtt{mdc(a,b)}`. Devido a esse caráter de busca sequência pelo :math:`\mathtt{mdc(a,b)}` é que a função tem o sufixo ``tt`` de *testa tudo*. Verifiquemos que a função ``mdc_tt()`` de fato faz o que promete. |:face_with_raised_eyebrow:| Eis algumas das relações invariantes da função ``mdc_tt()``. No início da linha 1 vale que: * (i0) :math:`\mathtt{1 \leq d \leq \min(a, b)}`, e * (i1) :math:`\mathtt{a \% t \neq 0}` **ou** :math:`\mathtt{b \% t \neq 0}` para todo :math:`\mathtt{t > d}`. A invariante (i2) a seguir garante que (i0) e (i1) valem no início da próxima iteração com ``d-1`` no papel de ``d``. No início da linha 2 vale que: * (i2) :math:`\mathtt{a \% d \neq 0}` **ou** :math:`\mathtt{b \% d \neq 0}`. Devido a relação (i2) é evidente, está na cara |:person_tone5_red_hair:|, que no início da linha 3, antes do ``return d`` vale que: * (i3) :math:`\mathtt{a \% d = 0}` **e** :math:`\mathtt{b \% d = 0}`. Como (i1) vale na linha 1, então também vale na linha 3. Assim, nenhum número inteiro maior que o valor ``d`` a ser retornado divide ``a`` e ``b``. Portanto, o valor retornado pela função é de fato o maior dos divisores de :math:`\mathtt{a}` e :math:`\mathtt{b}`, é o legítimo :math:`\mathtt{mdc(a,b)}`. Invariantes são assim mesmo. |:+1_tone4:| A validade inicial de umas, junto com trabalho feito pelo código, servem para confirmar a validade das relações em cada iteração. |CONFUSO| A correção da função ou algoritmo é muitas vezes consequência evidente da validade das relações. Bem, passemos ao consumo de tempo de ``mdc_tt()``. Quanto mais iterações do ``while..`` são executdas, maior deve ser o consumo de tempo da função. Faz sentido?! |HEIN| Portanto é natural nos perguntarmos Quantas iterações do ``while...`` faz a função ``mdc()``? Essa pergunta é essencialmente a mesma que a questão Quantas vezes o comando ``d -= 1`` é executado? .. index:: tempo constante A resposta a essa pergunta depende claramente dos valores de :math:`\mathtt{a}` e :math:`\mathtt{b}`. |:thinking:| Se o :math:`\mathtt{mdc(a, b)}` é :math:`\mathtt{\min(a,b)}`, valor inicial de ``d`` na linha 0, então o consumo de tempo é **constante**, independe de quão grandes são os valores de :math:`\mathtt{a}` ou de :math:`\mathtt{b}`. Esse é o **melhor caso** para ``mdc()``. É quando a função trabalha menos. |:smile:| |:face_with_raised_eyebrow:| .. index:: números coprimos .. index:: números relativamente primos Já o pior caso ocorre quando :math:`\mathtt{a}` e :math:`\mathtt{b}` são **relativamente primos** ou **coprimos**. Nesse caso o :math:`\mathtt{mdc(a, b)}` é 1 e a linha 2 com o seu ``d -= 1`` será executada com ``d`` tendo os valores ``min(a,b)``, ``min(a,b)-1``, ``min(a,b)-2``,..., ``3``, e ``2``. Por exemplo, :math:`317811` e :math:`514229` são relativamente primos e a ``mdc_tt(317811, 514229)`` executará :math:`317811-1` iterações do ``while...``, pois :math:`\mathtt{mdc(317811, 514229) = 1}`. .. index:: notação O-grande Neste caso, costumamos dizer que o consumo de tempo do algoritmo, no **pior caso**, é proporcional a :math:`\mathtt{\min(a, b)}`, ou ainda, que o consumo de tempo do algoritmo é da **ordem de** :math:`\mathtt{\min(a, b)}`. A abreviatura de *ordem blá* é :math:`{\textup{O}(\mbox{blá})}`. Daqui a pouco conversaremos sobre essa tal de ordem de uma maneira um pouco mais precisa. **Conclusão:** No *pior caso*, o consumo de tempo da função ``mdc_tt()`` é proporcional a :math:`\mathtt{\min(a, b)}`. Na pratica isso significa que se o valor de :math:`\mathtt{\min(a, b)}` dobrar, então o tempo gasto pela função ``mdc_tt()`` pode, no pior caso, se formos azarados, dobrar. |HELP| Vamos fazer um teste de resistência com a função ``mdc_tt()`` testando-a para valores de :math:`\mathtt{a}` e :math:`\mathtt{b}` que são relativamente primos. Esses valores fazem com que ``mdc_tt()`` trabalhe muito. Aproveitamos, para exibir resultados com os tempos gastos de outras duas funções além de ``mdc_tt()``: * ``math.gcd()`` da biblioteca ``math`` do Python; e * ``euclidesR()`` nosso algoritmo de Euclides caseiro. Na tabela os tempos estão todos em segundos. Nem precisava dizer, mas na tabela os valores :math:`\mathtt{0.00}` não são zeros de verdade. Algum tempo a função deve ter gastado para fazer o seu serviço. Esses :math:`\mathtt{0.00}` indicam apenas que o tempo gasto foi muito pequeno. No caso, muito pequeno é qualquer coisa menor que :math:`\mathtt{0.005}`. .. math:: \begin{array}{|r|c|c|c|c|} \hline \mathtt{a}& \mathtt{b} & \mathtt{math.gcd()} & \mathtt{euclidesR()} & \mathtt{mdc\_tt()} \\ \hline 75025& 46368& 0.00& 0.00& 0.00\\ \hline 121393& 75025& 0.00& 0.00& 0.01\\ \hline 196418& 121393& 0.00& 0.00& 0.01\\ \hline 317811& 196418& 0.00& 0.00& 0.02\\ \hline 514229& 317811& 0.00& 0.00& 0.02\\ \hline 832040& 514229& 0.00& 0.00& 0.04\\ \hline 1346269& 832040& 0.00& 0.00& 0.06\\ \hline 2178309& 1346269& 0.00& 0.00& 0.10\\ \hline 3524578& 2178309& 0.00& 0.00& 0.16\\ \hline 5702887& 3524578& 0.00& 0.00& 0.26\\ \hline 9227465& 5702887& 0.00& 0.00& 0.43\\ \hline 14930352& 9227465& 0.00& 0.00& 0.69\\ \hline 24157817& 14930352& 0.00& 0.00& 1.12\\ \hline 39088169& 24157817& 0.00& 0.00& 1.81\\ \hline 63245986& 39088169& 0.00& 0.00& 2.92\\ \hline 102334155& 63245986& 0.00& 0.00& 5.34\\ \hline 165580141& 102334155& 0.00& 0.00& 7.78\\ \hline 267914296& 165580141& 0.00& 0.00& 12.49\\ \hline 433494437& 267914296& 0.00& 0.00& 20.17\\ \hline 701408733& 433494437& 0.00& 0.00& 33.12\\ \hline \end{array} Examinemos um pouco a tabela. |:face_with_monocle:| Vemos que quando o valor de :math:`\mathtt{min(a,b)}` foi de :math:`14930352` para :math:`24157817` o tempo gasto passou de :math:`1.12` para :math:`1.81`. Assim, quando o valor do :math:`\mathtt{min(a,b)}` cresceu de aproximademente :math:`1.61` vezes (:math:`14930352 \times 1.61 \approx 24037866`), o tempo gasto também cresceu de aproximadamente :math:`1.61` vezes, foi de :math:`1.12` para :math:`1.81` (:math:`1.12 \times 1.61 \approx 1.80`). Para outras outros pares de linhas vemos que um fenômeno semelhante se verifica! Vejamos que quando :math:`\mathtt{min(a,b)}` foi de :math:`3524578` para :math:`102334155`, uma aumento de aproximadamente :math:`29` vezes (:math:`3524578 \times 29 = 102212762`), o tempo gasto saltou de :math:`0.26` para :math:`7.78` (:math:`0.26 \times 29 = 7.54`). Faz sentido, não?! |HEIN| É esse o efeito do consumo de tempo ser proporcional a :math:`\mathtt{min(a,b)}`. |:+1_tone5:| Agora, a pergunta que não quer calar é **Pergunta:** Por que o tempo gasto por ``euclideR()`` é tão menor que o de ``mdc_tt()``? |:confused:| Na próxima seção iremos dissecar a função ``euclideR()`` para respondermos a essa questão e entendermos o que está acontecendo. |:smile:| .. admonition:: |:warning:| Se trata da ideia, não se trata do computador. A rigor deveríamos dizer qual o computador, com quantos núcleos, qual a versão do |Python|,..., utilizamos para obter esses tempos. Para nós essa informação é irrelevante pois não estamos interessados no tempo gasto, poderíamos estar. |:hushed:| Estamos interessados em determinar a velocidade que o tempo gasto cresce a medida que o trabalho que a função faz cresce. Assim, no seu computador você pode e **deve** obter valores diferentes para os tempos gastos. No entanto, a velocidade de crescimento do tempo em função do trabalho realizado pela função será aproximadamente o mesmo. Essa velocidade depende do algoritmo, da ideia que a função implementa, e não do computador. |:roll_eyes:| Brinque com o cronômetro abaixo no |Trinket| ou baixe tudo para o seu computador. .. raw:: html Esforço de Euclides ------------------- Nesta seção vamos desvendar a mágica |:magic_wand:| do Euclides para seu algoritmo ser tão mais rápido que ``mdc_tt()``, como constatamos nos experimentos no final da última seção. .. index:: recorrência de Euclides Consideremos a função recursiva ``euclidesR()`` que implementa a ideia do Euclides. Como discutimos na seção :ref:`my_Euclides`, o coração da ideia do Euclides e relação de recorrência: .. math:: \mathtt{mdc(a, b)} = \begin{cases} \mathtt{a} & \mbox{se } \mathtt{b = 0} \nonumber \\ \mathtt{mdc(b, a \% b)} & \mbox{para } \mathtt{b > 0}. \nonumber \end{cases} O efeito dessa relação de recorrência pode ser visto no rastro de ``euclidesR(372, 162)`` que retorna :math:`\mathtt{6 = mdc(372, 162)}`. :: euclidesR(372,162) euclidesR(162,48) euclidesR(48,18) euclidesR(18,12) euclidesR(12,6) euclidesR(6,0) = 6 euclidesR(12,6) = 6 euclidesR(18,12) = 6 euclidesR(48,18) = 6 euclidesR(162,48) = 6 euclidesR(372,162) = 6 Simulando com papel e lápis o trabalho feito por ``euclidesR()` chegamos a tabela .. math:: \begin{array}{ c|c|c|c|c|c|c } & 2 & 3 & 2 & 1 & 2 & \\ \hline 372 & 162 & 48 & 16 & 12 & 6 & 0 \\ \hline 48 & 18 & 12 & 6 & 0 & & \end{array} Na linha inferior os valores :math:`\mathtt{48, 18, 12, 6, 0}` são os restos das divisões. Na linha superior os valores :math:`\mathtt{2, 3, 2, 1, 2}` são os quocientes das divisões. Por exemplo, logo no ínicio da tabela vemos :math:`\mathtt{18}` que é :math:`\mathtt{372\%162}` é vemos :math:`\mathtt{2}` que é :math:`\mathtt{372 // 162}`. A bem da verdade, para ``euclidesR()``, os vamos dos quocientes são irrelevantes, não são usados. Vamos examinar a função ``euclidesR()`` a fim de estimarmos o seu consumo de tempo. Suponha que ``euclidesR()`` faz :math:`\mathtt{k}` chamadas recursivas para determinar :math:`\mathtt{mdc(a, b)}`. Nosso objetivo é determinar o valor de :math:`\mathtt{k}` em termos de :math:`\mathtt{a}` e :math:`\mathtt{b}`. Isso é semelhante ao que fizemos quando investigamos a função ``mdc_tt()`` para limitarmos o número de execuções de ``d -= 1`` em termos de :math:`\mathtt{a}` e :math:`\mathtt{b}`. Por conveniência suponha que :math:`\mathtt{a \geq b > 0}`. Podemos visualizar essa chamadas recursivas com papel e lápis escrevendo: .. math:: \begin{array}{ c|c|c|c|c|c|c|c|c|c } & \mathtt{q_1} & \mathtt{q_2} & \mathtt{q_3} & \cdots & \mathtt{q_{k-1}} & \mathtt{q_{k}} & \mathtt{q_{k+1}} & \\ \hline \mathtt{a} & \mathtt{b} & \mathtt{r_1} & \mathtt{r_2} & \mathtt{r_3} & \cdots & \mathtt{r_{k-2}} & \mathtt{r_{k-1}} & \mathtt{r_k} & \mathtt{r_{k+1} = 0} \\ \hline \mathtt{r_1} & \mathtt{r_2} & \mathtt{r_3} & \mathtt{r_4} & \cdots & \mathtt{r_{k-1}} & \mathtt{r_{k}} & \mathtt{0} & \end{array} Em que os :math:`\mathtt{q_i}` s e os :math:`mathtt{r_i}` s são os quocientes e restos das divisões, respectivamente. Dessa forma .. math:: \mathtt{a \geq b > r_1 > r_2 > r_3 > \cdots > r_{k-1} > r_{k} > r_{k+1} = 0} são os valores dos argumentos no início de cada uma das chamadas da função ``euclideR()``. Por exemplo, para :math:`\mathtt{a=514229}` e :math:`\mathtt{b=317811}` temos que .. math:: \begin{align*} \mathtt{a} & = \mathtt{514229} \\ \mathtt{b} & =\mathtt{ 317811}, \\ \mathtt{r_1} & = \mathtt{196418}, \\ \mathtt{r_2} & = \mathtt{121393}, \\ \ldots & = \ldots \\ \mathtt{r_{26}} & = \mathtt{1}, \\ \mathtt{r_{27}} & = \mathtt{0}. \end{align*} :: euclidesR(317811,514229) euclidesR(514229,317811) euclidesR(317811,196418) euclidesR(196418,121393) euclidesR(121393,75025) euclidesR(75025,46368) euclidesR(46368,28657) euclidesR(28657,17711) euclidesR(17711,10946) euclidesR(10946,6765) euclidesR(6765,4181) euclidesR(4181,2584) euclidesR(2584,1597) euclidesR(1597,987) euclidesR(987,610) euclidesR(610,377) euclidesR(377,233) euclidesR(233,144) euclidesR(144,89) euclidesR(89,55) euclidesR(55,34) euclidesR(34,21) euclidesR(21,13) euclidesR(13,8) euclidesR(8,5) euclidesR(5,3) euclidesR(3,2) euclidesR(2,1) euclidesR(1,0) = 1 [...] euclidesR(317811,514229) = 1 Notemos ainda que para inteiros :math:`\mathtt{m}` e :math:`\mathtt{n}` com :math:`\mathtt{m \geq n >0}` vale que .. math:: \mathtt{m \% n < \frac{m}{2}} \quad \mbox{(verifique!)}. Desta forma temos que .. math:: \begin{array}{lcccccccccc} \mathtt{r_1} &=& \mathtt{a} \% \mathtt{b} &<& \mathtt{a/2} &=& \mathtt{a}/\mathtt{2^1} \\ \mathtt{r_3} &=& \mathtt{r_1} \% \mathtt{r_2} &<& \mathtt{r_1/2} &<& \mathtt{a/4} &=& \mathtt{a}/\mathtt{2^2} \\ \mathtt{r_5} &=& \mathtt{r_3} \% \mathtt{r_4} &<& \mathtt{r_3/2} &<& \mathtt{a/8} &=& \mathtt{a}/\mathtt{2^3} \\ \mathtt{r_7} &=& \mathtt{r_5} \% \mathtt{r_6} &<& \mathtt{r_5/2} &<& \mathtt{a/16} &=& \mathtt{a}/\mathtt{2^4} \\ \mathtt{r_9} &=& \mathtt{r_7} \% \mathtt{r_8} &<& \mathtt{r_7/2} &<& \mathtt{a/32} &=& \mathtt{a}/\mathtt{2^5} \\ & \cdots \\ & \cdots \\ & \cdots \end{array} Com isso vemos que depois de **2 aplicações sucessivas** de duas chamadas recursivas, o valor do primeiro argumento, o :math:`\mathtt{a}`, é reduzido a **menos da metade**. Suponhamos que :math:`\mathtt{t}` é o número inteiro tal que .. math:: \begin{align*} \mathtt{2^t} & \leq \mathtt{a} < \mathtt{2^{t+1}} \end{align*} Da primeira desigualdade temos que .. math:: \begin{align*} \mathtt{t} & \leq \lg \mathtt{a}, \end{align*} em que :math:`\mathtt{\lg a}` é o logaritmo de :math:`\mathtt{a}` na base 2. Da desigualde estrita, concluímos que .. math:: \begin{align*} \mathtt{k} & \leq \mathtt{2 (t+1) - 1} = \mathtt{2 t+1} . \end{align*} Logo, o número :math:`\mathtt{k}` de divisões, chamadas recursivas, é não superior a .. math:: \begin{align} \mathtt{2t + 1} & \leq \mathtt{2\lg n + 1}. \end{align} Para o exemplo acima, em que :math:`\mathtt{a=514229}` e :math:`\mathtt{b= 317811}`, temos que .. math:: \begin{align*} \mathtt{2 \lg a + 1} & = \mathtt{2 \lg 514229 + 1 < 2 \times 18{,}98 + 1 < 38{,}96} \end{align*} e o número de chamadas recursivas feitas por ``euclidesR(514229,317811)`` é 27. Resumindo, a quantidade de tempo consumida pelo algoritmo de Euclides é, no pior caso, **proporcional** a :math:`\mathtt{\lg a}`. Notemos que se :math:`\mathtt{a < b}` então a chamada ``euclides(a, b)`` faz apenas uma chamada recursiva a mais que a chamada ``euclides(a, b)``. Portanto chegamos a nossa **Conclusão:** *No pior caso*, o consumo de tempo de ``euclideR(a, b)`` é proporcional a :math:`\mathtt{\lg d}`, em que :math:`\mathtt{d = \min(a,b)}`. Este desempenho é **significativamente melhor** que o desempenho do algoritmo *café com leite* implementada na função ``mdc_tt()`` já que a função :math:``f(d) = \lg d`` cresce **muito mais lentamente** que a função :math:`\mathtt{g(d) = d}`. .. math:: \begin{array}{l|c} \mathtt{d} & \mathtt{\lfloor \lg d \rfloor} \\ \hline 4 & 2 \\ 5 & 2 \\ 6 & 2 \\ 10 & 3 \\ 64 & 6 \\ 100 & 6 \\ 128 & 7 \\ 1000 & 9 \\ 1024 & 10 \\ 1000000 & 19 \\ 1000000000 & 29 \\ \end{array} O consumo de tempo :math:`\mathtt{\lg d}` significa se a função ``euclidesR(a, b)`` gasta :math:`\mathtt{t}` unidades de tempo, então para que a chamada ``euclidesR(m, n)`` gaste :math:`\mathtt{2t}` unidades de tempo é necessário, mas não suficiente |:warning:|, que :math:`\mathtt{\min(m,n)}` seja cerca de :math:`\mathtt{d^2}`, em que :math:`\mathtt{d = \min(a,b)}`. |:open_mouth:| Podemos verificar que o tempo gasto pela versão recursiva ``euclidesR()`` do algoritmo de Euclides gasta aproximadamente o mesmo tempo que a sua versão iterativa ``euclidesI()``. Com tudo que vimos, desvendamos o mistério da eficiência absurda da ideia do Euclides. |:smile:| Oh -- Para expressar o consumo de tempo ou de espaço de funções, métodos, programas e algoritmos é comum utilizarmos a **notação assintótica**. Ela expressa os recursos utilizados *no limite*, a medida que a quantidade de dados cresce. A quantidade de dados é chamada **tamanho do problema**. Em algoritmos de busca e de ordenação é de se esperar que o consumo de tempo dependa do número :math:`\mathtt{n}` de elementos na lista sob consideração. Veja, na página `TimeComplexity `_, como são registrados os **tempos médios** e os **tempos no pior caso** gastos por métodos de várias classes nativas do Python. Observando a tabela abaixo de :math:`\mathtt{(3/2)n^2 + (7/2)n -4}` versus :math:`\mathtt{(3/2)n^2}` vemos que a medida que :math:`\mathtt{n}` cresce os termos de menor ordem colaboram poucou para o valor final. No final das contas :math:`\mathtt{(3/2)n^2}` domina amplamente todos os demais termos. :math:`\mathtt{(3/2)n^2}` é :math:`\mathtt{\textup{O}(n^2)}` .. math:: \begin{array}{rrr} \mathtt{n} & \mathtt{ (3/2)n^2 + (7/2)n -4}& \mathtt{ (3/2)n^2}\\[0.5ex]\hline 64 & { 6364} & { 6144 }\\[0mm] 128 & { 25020} & { 24576 }\\[0mm] 256 & { 99196} & { 98304 }\\[0mm] 512 & { 395004} & { 393216 }\\[0mm] 1024 & { 1576444} & { 1572864 }\\[0mm] 2048 & { 6298620} & { 6291456 }\\[0mm] 4096 & { 25180156} & { 25165824 }\\[0mm] 8192 & { 100691964} & { 100663296 }\\[0mm] 16384 & { 402710524} & { 402653184 }\\[0mm] 32768 & { 1610727420} & { 1610612736 }\\[-4mm]\hline \end{array} Para sentir como o número de operações impacta no consumo de tempo de um algoritmo, veja a tabela a seguir que foi copiada do livro *Projeto de Algoritmos* de Michael T. Goodrich e Roberto Tamassia, Bookman. A tabela supõe que cada operação consome :math:`1` microsegundo, ou seja, :math:`1\mu` s. .. math:: \begin{array}{|r|r|r|r|}\hline \text{tempo}(\mu s) & \text{1 segundo} & \text{1 minuto} & \text{1 hora}\\[2mm] \hline 400n & { 2500} & { 150000} & { 9000000}\\[1mm] 20\,n\,\lceil\lg n\rceil & { 4096} & { 166666} & {7826087}\\[1mm] 2n^2 & { 707} & { 5477} & { 42426}\\[1mm] n^4 & { 31} & { 88} & { 244}\\[1mm] 2^n & { 19} & { 25} & { 31}\\[1mm] \hline \end{array} A tabela mostra que um algoritmo que gasta cerca de :math:`400n \; \mu` segundos resolve em 1 segundo um problema de tamanho até :math:`\mathtt{n=2500}`, em 1 minuto resolve um problema de tamanho :math:`\mathtt{n=150}` mil e em 1 hora de tamanho :math:`\mathtt{n=9}` milhões. Olhando as outras linhas vemos que, no final das contas, para analisar o desempenho para um problema grande o que mais importa é o termo que cresce mais rapidamente e que acaba dominando os demais. A notação assintótica :math:`\textup{O}`-grande procura capturar essas ideias. Sejam :math:`\mathtt{T(n)}` e :math:`\mathtt{f(n)}` funções dos inteiros nos reais. Dizemos que :math:`\mathtt{T(n)}` é :math:`\mathtt{\textup{O}(f(n))}` se existem constantes positivas :math:`\mathtt{c}` e :math:`\mathtt{n_0}` tais que .. math:: \begin{align*} \mathtt{T(n)} & \mathtt{\leq c\, f(n), \quad \mbox{ para todo } n \geq n_0.} \end{align*} .. image:: ./imgs/notacao_assintotica.* :width: 811 :height: 587 :scale: 50 :alt: Notação assintótica :align: center De uma maneira mais intuitiva, :math:`\mathtt{T(n)}` é :math:`\mathtt{\textup{O}(f(n))}` se existe :math:`\mathtt{c}>0` tal que .. math:: \begin{align*} \mathtt{T(n)} & \mathtt{\leq c\, f(n), \quad \text{ para todo } n} \text{ suficientemente GRANDE. } \end{align*} Vejam o crescimento de algumas funções conhecidas. .. math:: \begin{array}{|r|rrrrrr|}\hline \mathtt{n} & \mathtt{\lg n} & \mathtt{\sqrt{n}} & \mathtt{ n \lg n} & \mathtt{n^2} & \mathtt{ n^3} & \mathtt{2^n}\\[2mm] \hline 2 & 1 & 1{,}4 & 2 & 4 & 8 & 4\\[1mm] 4 & 2 & 2 & 8 & 16 & 64 & 16 \\[1mm] 8 & 3 & 2{,}8 & 24 & 64 & 512 & 256\\[1mm] 16 & 4 & 4 & 64 & 256 & 4096 & 65536\\[1mm] 32 & 5 & 5{,}7 & 160 & 1024 & 32768 & 4294967296\\[1mm] 64 & 6 & 8 & 384 & 4096 & 262144 & 1{,}8 10^{19}\\[1mm] 128 & 7 & 11 & 896 & 16384 & 2097152 & 3{,}4 10^{38}\\[1mm] 256 & 8 & 16 & 1048 & 65536 & 16777216 & 1{,}1 10^{77}\\[1mm] 512 & 9 & 23 & 4608 & 262144 & 134217728 & 1{,}3 10^{154}\\[1mm] 1024& 10 & 32 & 10240 & 1048576 & 1{,}1 10^9 & 1{,}7 10^{308}\\\hline \end{array} Algumas classes :math:`\textup{O}` mais comuns, mais famosas, recebem nomes. .. math:: \begin{array}{|l|l|}\hline \text{ classe} & \text{ nome}\\[1mm] \hline \mathtt{\textup{O}(1)} & \text{constante}\\[1mm] \mathtt{\textup{O}(\lg n)} & \text{logarítmica} \\[1mm] \mathtt{\textup{O}(n)} & \text{linear} \\[1mm] \mathtt{\textup{O}(n \lg n)} & n \log n \\[1mm] \mathtt{\textup{O}(n^2)} & \text{quadrática} \\[1mm] \mathtt{\textup{O}(n^3)} & \text{cúbica} \\[1mm] \mathtt{\textup{O}(n^{k})} \text{ com } k\geq 1 & \text{polinomial}\\[1mm] \mathtt{\textup{O}(2^{n})} & \text{exponencial}\\[1mm] \mathtt{\textup{O}(a^{n}) \text{ com } a>1} & \text{exponencial}\\ \hline \end{array} Temos, portanto, que o consumo de tempo da função: * ``hanoi()`` é :math:`\mathtt{\textup{O}(2^n)}`, exponencial, em que :math:`\mathtt{n}` é o número de discos do quebra-cabeça; * ``sequencial()`` que implementa a busca sequencial é :math:`\mathtt{\textup{O}(n)}`, linear, desta vez :math:`\mathtt{n}` é o tamanho da lista que será percorrida; * ``busca_bin()`` que faz busca binária é :math:`\mathtt{\textup{O}(\lg n)}`, logarítmico, mais uma vez :math:`\mathtt{n}` é o tamanho da lista que será percorrida; * ``insercao()`` que faz ordenação por inserção é :math:`\mathtt{\textup{O}(n^2)}`, quadrático, aqui :math:`\mathtt{n}` é o número de elementos na lista a ser ordenada ; * ``mdc_tt()`` para determinar o maior divisor comum de um par de números inteiros :math:`\mathtt{a}` e :math:`\mathtt{b}` é :math:`\mathtt{\textup{O}(d)}`, linear; em que :math:`mathtt{d = \min(a,b)}`; * ``eunclideR()`` para encontra o maior divisor comum de um par de números inteiros :math:`\mathtt{a}` e :math:`\mathtt{b}` é :math:`\mathtt{\textup{O}(\lg d)}`, logarítmico; novamente :math:`mathtt{d = \min(a,b)}`. A análise de consumo de tempo não são apenas um bando de contas seguidas de símbolos! Os valores obtidos têm impacto inegável, estão nas estranhas, do tempo gasto pelas funções que implementam os algoritmos. |:open_mouth:| Dicionários ordenados --------------------- Como exercício faremos uma classe ``DicioB`` implementando um dicionário em que as chaves são mantidas em ordem crescente. Esse é um trabalho para a parceria entre **busca binária** e **ordenação por inserção**. Para que as chaves de um objeto da classe ``DicioB`` sejam mantidas em ordem, diferentemente do que ocorreu com a classe ``Dicio``, as chaves **não** podem ser de tipos quaisquer. Se ``dB`` é um objeto ``DicioB`` e ``chave1`` e ``chave2`` são duas das chaves em ``dB``, então deve ser possível fazermos comparações como: ``classe1 < classe2``, ``classe1 <= classe2``, ``classe1 > classe2``, ``classe1 >= classe2``. Por exemplo, as chaves de ``dB`` podem ser da classe nativa ``str`` ou da classe nativa ``int``, mas **não de ambas**, já que comparações como ``5 < 'xx'`` resultam em erro Aparte a ordenação das chaves, um dicionário da classe ``DicioB`` é semelhante a um dicionário da classe ``Dicio``. Ao ser **criado**, um objeto ``DicioB`` representa um dicionário vazio. .. code:: python In [2]: dB = DicioB() In [3]: print(dB) # note a linha vazia a seguir In [4]: Como sempre, a string utilizada quando escrevemos ``print(dB)`` é aquela retornada pelo método mágico ``__str__()`` que **retorna** uma string que representa ``dB``. Um item, ou seja, par ``(chave, valor)`` pode ser **inserido** em um dicionário de duas formas diferentes. Uma delas é usando o método ``put()``: .. code:: python In [4]: dB.put('fracassei', 3) In [5]: dB.put('em', 1) In [6]: dB.put('tudo', 1) In [7]: print(dB) em: 1 fracassei: 3 tudo: 1 Note que as chaves estão em **ordem crescente**: `` 'em' < 'fracassei' < 'tudo' `` A outra maneira é semelhante a mudarmos o valor de um elemento de uma lista. Esse comportamento é de responsabilidade do (já visto) método mágico ``__setitem__()``. .. code:: python In [8]: dB['o'] = 2 In [9]: dB['que'] = 3 In [10]: dB['tentei'] = 4 In [11]: print(dB) em: 1 fracassei: 3 o: 2 que: 3 tentei: 4 tudo: 1 Note que as chaves estão em **ordem crescente**: `` 'em' < 'fracassei' < 'o' < 'que' < 'tentei' < 'tudo' `` Podemos **atualizar** o valor associado a uma chave procedendo da mesma forma que inserimos um item no dicionário. .. code:: python In [12]: dB.put('o', 2) In [13]: dB['que'] = 1 In [14]: dB['tentei'] = 5 In [15]: print(dB) em: 1 fracassei: 3 o: 2 que: 1 tentei: 5 tudo: 1 Para obtermos, ou, como dizem, **buscar** o valor associado a uma chave usamos o método ``get()``. .. code:: python In [16]: dB.get('fracassei') Out[16]: 3 In [17]: dB.get('em') Out[17]: 1 In [18]: dB.get('tudo') Out[18]: 1 Podemos ainda manipular dicionários como listas. Essa característica é de responsabilidade do conhecido método mágico ``__getitem__()``. .. code:: python In [19]: dB['o'] Out[19]: 2 In [20]: dB['que'] Out[20]: 1 In [21]: dB['tentei'] Out[21]: 5 Esse métodos **retornam** ``None`` se a chave não estiver no dicionário: .. code:: python In [27]: print(dB.get('vida')) None In [28]: print(dB['vida']) None Tenha em mente que as chaves de dicionários ordenados **devem ser comparáveis**. Para sabermos se uma chave **pertence** a um dicionário podemos utilizar o operador ``in``, de maneira semelhante ao que fazemos com objetos da classe ``list``. Essa é uma característica patrocinada pelo método mágico ``__contains__()``: .. code:: python In [29]: 'tentei' in dB Out[29]: True In [30]: '1' in dB Out[30]: False In [31]: 1 in dB Out[31]: True In [32]: 5 in dB Out[32]: False No que diz respeito a **comandos de repetição**, com o patrocínio do método mágico ``__iter__()``, podemos proceder da seguinte maneira: .. code:: python In [36]: for chave in dB: print(f"{chave}: {dB[chave]}") em: 1 fracassei: 3 o: 2 que: 1 tentei: 5 tudo: 1 Note que as chaves estão em **ordem crescente**. Objetos da classe ``DicioB`` têm ainda três outros métodos que podem ser bem úteis, inclusive para testarmos nossas implementações. Esses métodos são: * ``keys()`` que **retorna a lista de chaves** do dicionário; * ``values()`` que **retorna a lista de valores** do dicionário; e * ``items()`` que **retorna a lista dos itens** do dicionário. .. code:: python In [22]: dB.keys() Out[22]: ['em', 'fracassei', 'o', 'que', 'tentei', 'tudo'] In [23]: dB.values() Out[23]: [1, 3, 2, 1, 5, 1] In [24]: dB.items() Out[24]: [('em', 1), ('fracassei', 3), ('o', 2), ('que', 1), ('tentei', 5), ('tudo', 1)] Note que as chaves estão em **ordem crescente**. Implementação ------------- Passaremos agora a implementação da classe ``DicioB``. Você deverá implementar métodos que fazem parte do **motor** da classe ``DicioB``: o *método administrativo* ``indice()`` e os métodos ``put()`` e ``get()`` que podem se apoiar em ``indice()`` para fazerem os seus serviços. O arquivo ``main.py`` tem uma função ``main()`` no final que é uma *unidade de teste* para sua classe. .. raw:: html Testes ------ Para testar a sua implementação da classe ``DicioB`` você pode utilizar a função ``main()`` a seguir. A saída esperada produzida pela função ``main()`` está mais adiante. .. code:: python def main(): ''' Unidade de teste para a classe DicioB ''' print("Testes para a classe DicioB") print("--------------------------\n") # __init__() e __str__() print("crie um dicionário vazio") dB = DicioB() print(f"dB:\n{dB}") pause() # aprecie a paisagem # put() print("\nteste put()") dB.put('fracassei', 3) dB.put('em', 1) dB.put('tudo', 1) print(f"dB:\n{dB}") pause() # aprecie a paisagem # __setitem__() print("\nteste __setitem__()") dB['o'] = 2 dB['que'] = 3 dB['tentei'] = 4 print(f"dB:\n{dB}") pause() # aprecie a paisagem # put() e __setitem__() print("\nteste put() e __setitem__()") dB.put('o', 2) dB['que'] = 1 dB['tentei'] = 5 print(f"dB:\n{dB}") pause() # aprecie a paisagem # get() print("\nteste get()") print(f"dB.get('fracassei')={dB.get('fracassei')}") print(f"dB.get('em')={dB.get('em')}") print(f"dB.get('tudo')={dB.get('tudo')}\n") pause() # aprecie a paisagem # __getitem__() print("\nteste __getitem__()") print(f"dB['o']={dB['o']}") print(f"dB['que']={dB['que']}") print(f"dB['tentei']={dB['tentei']}") print(f"dB.get('vida')={dB.get('vida')}") print(f"dB['vida']={dB['vida']}\n") pause() # aprecie a paisagem # mais __setitem__() print("\nmais teste __setitem__(): chaves devem ser comparáveis por <, <=,...") dB['na'] = 1 dB['vida'] = 1 print(f"dB:\n{dB}") pause() # aprecie a paisagem # teste __contains__() print("\nteste __contains__()") print(f"'tentei' in dB={'tentei' in dB}") print(f"'1' in dB={'1' in dB}") print(f"1 in d={1 in dB}") print(f"5 in d={5 in dB}\n") pause() # aprecie a paisagem # teste __iter__() print("\nteste __iter__(): usado para clonar d") clone = DicioB() for chave in dB: clone[chave] = dB[chave] print(f"clone:\n{clone}") pause() # aprecie a paisagem # teste __len__() print("\nteste __len__()") print(f"len(dB)={len(dB)}") print(f"len(clone)={len(clone)}") dicio_vazio = DicioB() print(f"len(dicio_vazio)={len(dicio_vazio)}\n") pause() # aprecie a paisagem # teste keys(), values() e items() print("\nteste keys(), values() e items()") print(f"clone.keys()={clone.keys()}") print(f"clone.values()={clone.values()}") print(f"clone.items()={clone.items()}\n") pause() # aprecie a paisagem print("FIM") :: crie um dicionário vazio dB: Tecle ENTER para continuar: teste put() dB: em: 1 fracassei: 3 tudo: 1 Tecle ENTER para continuar: teste __setitem__() dB: em: 1 fracassei: 3 o: 2 que: 3 tentei: 4 tudo: 1 Tecle ENTER para continuar: teste put() e __setitem__() dB: em: 1 fracassei: 3 o: 2 que: 1 tentei: 5 tudo: 1 Tecle ENTER para continuar: teste get() dB.get('fracassei')=3 dB.get('em')=1 dB.get('tudo')=1 Tecle ENTER para continuar: teste __getitem__() dB['o']=2 dB['que']=1 dB['tentei']=5 dB.get('vida')=None dB['vida']=None Tecle ENTER para continuar: mais teste __setitem__(): chaves devem ser comparáveis por <, <=,... dB: em: 1 fracassei: 3 na: 1 o: 2 que: 1 tentei: 5 tudo: 1 vida: 1 Tecle ENTER para continuar: teste __contains__() 'tentei' in dB=True '1' in dB=False 1 in d=False 5 in d=False Tecle ENTER para continuar: teste __iter__(): usado para clonar d clone: em: 1 fracassei: 3 na: 1 o: 2 que: 1 tentei: 5 tudo: 1 vida: 1 Tecle ENTER para continuar: teste __len__() len(dB)=8 len(clone)=8 len(dicio_vazio)=0 Tecle ENTER para continuar: teste keys(), values() e items() clone.keys()=['em', 'fracassei', 'na', 'o', 'que', 'tentei', 'tudo', 'vida'] clone.values()=[1, 3, 1, 2, 1, 5, 1, 1] clone.items()=[('em', 1), ('fracassei', 3), ('na', 1), ('o', 2), ('que', 1), ('tentei', 5), ('tudo', 1), ('vida', 1)] Tecle ENTER para continuar: FIM Paisagens vistas ---------------- Exercícios ---------- #. Escreva uma função ``busca_binaria(v, x, e, d)`` que **recebe** uma lista crescente ``v[e:d]`` e um objeto ``x`` e **retorna** um índice ``j`` em ``range(e,d)`` tal que, após a inserção de ``x`` na posição ``v[j+1]``, a lista ``v[e:d+1]`` será crescente. A sua função deverá ser uma adaptação da função ``busca_bin()``. Uma função com a especificação da dessa ``busca_binaria()`` é um dos motores de uma versão do algoritmo por inserção. #. A versão da busca binária a seguir tem alguns problemas. Quais são? Como podemos repará-los? .. code:: python def busca_binariaR(v, x): n = len(v) if n == 0: return None m = n // 2 if v[m] == x: return m if v[m] < x: return busca_binariaR(v[m+1:],x) return busca_binariaR(v[:m], x) O que é ... ----------- Aqui vai o resumo do significado de alguns termos usados neste capítulo. |:nerd:| .. glossary:: Consumo de tempo constante Dizemos que uma função, um programa, ou um trecho de código consome tempo constante quando o tempo gasto para executá-lo independe dos dados sendo manipulados. Análise de pior caso A análise de pior caso considere o maior tempo ou espaço gasto por uma função, um programa, ou um trecho de código em função do a entrada Tamanho de um objeto Tipicamente é o número de bytes para representá-lo. Esse número depende da escolha da representação. Tamanho de um inteiro Tipicamente é o número de dígitos usados para representá-lo. O tamanho do inteiro ``1234`` é ``4``. Esse número depende da escolha da representação. Na base 2 escrevemos o número decimal ``1234`` como ``11010010`` que usa ``8`` dígitos binários. Tamanho de uma lista Utilizamos o número de componentes da lista como sendo seu tamanho. O tamanho da lista ``[1, 2, 3]`` é ``len([1,2,3]) = 3`` e da lista ``[[1],[1,2],[1,2,3]]`` é ``len([1]) + len([1,2]) + len([1,2,3]) = 6``. Tamanho de um objeto Número de símbolos usados para representar o objeto. Essa medida depende do conjunto de símbolos. Se consideramos os símbolos que aparecem no teclado do computador |:keyboard:|, o tamanho do inteiro ``1234`` é ``4``, da string ``"mac0122"`` é 7. O tamanho de um objeto complexo é a soma dos tamanhos de seu componentes. Para saber mais --------------- * `Busca em vetor ordenado `_ de `Projeto de Algoritmos `_ de Paulo Feofiloff. * `Ordenação: algoritmos elementares `_ de `Projeto de Algoritmos `_ de Paulo Feofiloff. * `A Busca Binária `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `A Ordenação Por Inserção `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `Notação O `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `Dicionários `_ de `Como Pensar Como um Cientista da Computação `_ de Brad Miller e David Ranum. * `Analysis of Algorithms `_ de `Introduction to Programming in Python `_. de Robert Sedgewick, Kevin Wayne e Robert Dondero.