-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
289 lines (281 loc) · 21.1 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>resumo</title>
<link rel="stylesheet" href="https://stackedit.io/style.css" />
<link rel="stylesheet" href="index.css">
<script src="script.js"></script>
</head>
<body class="stackedit">
<div class="stackedit__left">
<div class="stackedit__toc">
<ul>
<li><a href="#pesquisa-binária">Pesquisa Binária</a>
<li><a href="#ordenação-por-seleção">Ordenação por Seleção</a>
<li><a href="#recursão">Recursão</a>
<li><a href="#quicksort">Quicksort</a>
<li><a href="#tabelas-hash">Tabelas Hash</a>
<li><a href="#pesquisa-em-largura">Pesquisa em Largura</a>
<li><a href="#dijkstra">Dijkstra</a>
</ul>
</div>
</div>
<div class="stackedit__right">
<li><button class="dark-mode-toggle" onclick="darkMode()">
<img id="image-btn" src="to-dark.png">
</button></li>
<div class="stackedit__html">
<h1 id="pesquisa-binária">Pesquisa Binária</h1>
<ol>
<li>A pesquisa binária é muito mais rápida do que a pesquisa simples.</li>
<li><strong>O(log n)</strong> é mais rápido do que <strong>O(n)</strong>, e <strong>O(log n)</strong> fica ainda mais rápido conforme os elementos da lista aumentam.</li>
<li>A rapidez de um Algoritmo <strong>não</strong> é medida em <strong>segundos</strong>.</li>
<li>O tempo de execução de um algoritmo é medido por meio de seu <strong>crescimento</strong>.</li>
<li>O tempo de execução dos algoritmos é expresso na notação <strong>Big O</strong>.</li>
</ol>
<blockquote>
<h3 id="pensamentos">Pensamentos</h3>
<p>Todo algoritmo, por mais simples que seja, possui um tempo de execução, e esse tempo é medido pela notação <a href="https://pt.wikipedia.org/wiki/Grande-O">Big O</a>. Imagine quanto tempo levaria para procurar um elemento em uma lista de apenas 10 elementos; provavelmente seria muito rápido, talvez até menos de 1 milissegundo. No entanto, imagine agora que a lista tenha 4 bilhões de elementos; nesse caso, a busca pode levar consideravelmente mais tempo.<br>
No método convencional, leríamos a lista procurando nosso elemento um por um. Isso não é um problema quando a lista é pequena, mas quando ela se torna gigantesca, a abordagem se torna impraticável. É aí que a pesquisa binária entra em cena, pois, em vez de percorrer a lista elemento por elemento, você inicia a busca no meio da lista, com base em critérios específicos relacionados à ordenação, e, a partir daí, reduz as possibilidades pela metade. A pesquisa binária é especialmente eficiente para listas ordenadas, pois utiliza uma estratégia de divisão e conquista, dividindo repetidamente o espaço de busca pela metade até encontrar o elemento desejado.</p>
</blockquote>
<h3 id="exemplo-de-código">Exemplo de Código</h3>
<p class="paragraph" ><img src="https://i.ibb.co/dfPQqrp/Captura-de-tela-de-2023-09-21-08-09-17.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/pesquisa_binaria.py">Copiar</a></p>
<h1 id="ordenação-por-seleção">Ordenação por Seleção</h1>
<ol>
<li>A memória do seu computador é como um conjunto <strong>gigante</strong> de <strong>gavetas</strong>.</li>
<li>Quando se quer armazenar múltiplos elementos, usa-se um <code>array</code> ou uma <code>lista</code>.</li>
<li>No <code>array</code>, todos os elementos são <strong>armazenados</strong> um ao lado do outro <strong>(na memória)</strong>.</li>
<li>Na <code>lista</code> os elementos estão <strong>espalhados</strong>, e um elemento armazena o endereço do próximo elemento.</li>
<li><code>Arrays</code> permitem <strong>leituras rápidas</strong>.</li>
<li><code>Listas</code> encadeadas permitem <strong>rápidas inserções</strong> e <strong>eliminações</strong>.</li>
<li>Todos os <strong>elementos</strong> de um <code>array</code> devem ser do mesmo <strong>tipo</strong> (<code>ints</code>, <code>doubles</code>, e assim por diante).</li>
</ol>
<blockquote>
<h3 id="pensamentos-1">Pensamentos</h3>
<p>Antes de aprender sobre a Ordenação por Seleção, é importante compreender as diferenças entre <a href="https://pt.wikipedia.org/wiki/Lista_ligada">Listas Encadeadas</a> e <a href="https://pt.wikipedia.org/wiki/Arranjo_(computa%C3%A7%C3%A3o),">Arrays</a> pois ambos estão diretamente relacionados à memória da máquina. Como funcionam? Bem, listas e arrays possuem índices, e esses índices ocupam um espaço na memória, cada um de uma forma específica. Em listas encadeadas, os índices podem estar dispersos na memória, como este exemplo:</p>
<table>
<thead>
<tr>
<th><code>vazio</code></th>
<th>Café da Manhã</th>
<th><code>vazio</code></th>
<th><code>vazio</code></th>
<th><code>vazio</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><strong><code>vazio</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
<td><strong><code>vazio</code></strong></td>
<td><strong>Jogar Bocha</strong></td>
<td><strong><code>vazio</code></strong></td>
</tr>
<tr>
<td><strong><code>ocupado</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
<td><strong>Chá</strong></td>
<td><strong><code>vazio</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
</tr>
</tbody>
</table><p>Cada célula desta tabela representa um espaço na memória. Observe que os elementos na lista não estão contíguos. Em uma lista encadeada, cada item armazena o endereço do próximo item, mantendo assim a conexão entre os elementos. Portanto, adicionar novos elementos é uma tarefa simples, pois requer apenas um espaço livre na memória. O mesmo se aplica à remoção de elementos.<br>
No entanto, em um array, as coisas funcionam de maneira um pouco diferente:</p>
<table>
<thead>
<tr>
<th>Café da Manhã</th>
<th><strong>Jogar Bocha</strong></th>
<th><strong>Chá</strong></th>
<th><code>ocupado</code></th>
<th><code>vazio</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><strong><code>vazio</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
<td><strong><code>vazio</code></strong></td>
<td></td>
<td><strong><code>vazio</code></strong></td>
</tr>
<tr>
<td><strong><code>ocupado</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
<td></td>
<td><strong><code>vazio</code></strong></td>
<td><strong><code>ocupado</code></strong></td>
</tr>
</tbody>
</table><p>Em um array, todos os elementos devem estar contíguos na memória. Portanto, ao criar um array, você primeiro precisa encontrar um espaço na memória que seja grande o suficiente para acomodar o array. Se você deseja adicionar um novo elemento e o próximo espaço de memória estiver ocupado, será necessário mover todo o array para um novo local na memória. A remoção de elementos também é mais complicada, pois a eliminação de um elemento, como “Jogar Bocha”, requer que todo o restante do array seja movido para manter a continuidade, tornando-o lento para inserções e exclusões, mas eficiente para leituras.</p>
<table>
<thead>
<tr>
<th align="center"></th>
<th align="center">Arrays</th>
<th align="center">Listas</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">Leitura</td>
<td align="center">O(1)</td>
<td align="center">O(n)</td>
</tr>
<tr>
<td align="center">Inserção</td>
<td align="center">O(n)</td>
<td align="center">O(1)</td>
</tr>
<tr>
<td align="center">Eliminação</td>
<td align="center">O(n)</td>
<td align="center">O(1)</td>
</tr>
</tbody>
</table><p>Agora que compreendemos essas diferenças, podemos prosseguir para o nosso algoritmo de ordenação mais simples, a Ordenação por Seleção. Este algoritmo envolve a busca do menor/maior valor em uma lista desordenada e colocando-o como o primeiro elemento em uma nova lista. Repetimos esse processo em um loop até esvaziarmos a lista desordenada, resultando em uma lista ordenada.</p>
</blockquote>
<h3 id="exemplo-de-código-1">Exemplo de Código</h3>
<p><img class="paragraph" src="https://i.ibb.co/2tQKWkF/Captura-de-tela-de-2023-09-21-09-12-33.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/ordenacao_selecao.py">Copiar</a></p>
<h1 id="recursão">Recursão</h1>
<ol>
<li><strong>Recursão</strong> é quando uma <code>função</code> <strong>chama a si mesma</strong>.</li>
<li>Toda <code>função</code> recursiva tem dois casos: o <strong>caso-base</strong> e o caso <strong>recursivo</strong>.</li>
<li>Uma <strong>pilha</strong> tem duas operações: <code>push</code> e <code>pop</code>.</li>
<li>Todas as <strong>chamadas</strong> de <code>função</code> vão para a <strong>pilha de chamada</strong>(<code>call stack</code>).</li>
<li>A <strong>pilha de chamada</strong> pode ficar muito grande e ocupar muita memória.</li>
</ol>
<blockquote>
<h3 id="pensamentos-2">Pensamentos</h3>
<p>A recursão é um conceito fundamental na programação em que uma função chama a si mesma. Em geral, chamamos funções de fora do seu “escopo” quando achamos que é hora de executar o seu trabalho. No entanto, ao chamar uma função dentro dela mesma, criamos um processo recursivo. Isso pode resultar em um loop infinito, a menos que estabeleçamos uma condição de parada, o que é uma prática comum.<br>
As recursões têm uma função semelhante aos loops “for” e “while”. Todos eles são mecanismos de repetição que desempenham um papel importante em diferentes situações. As recursões são conhecidas por terem um tempo de execução geralmente mais eficiente do que os loops convencionais. No entanto, cada chamada recursiva gera uma estrutura de dados chamada “<a href="https://pt.wikipedia.org/wiki/Pilha_de_chamada">Pilha de Chamadas</a>”, que é empilhada uma sobre a outra na memória. Portanto, é importante gerenciar o tamanho dessas pilhas para evitar o estouro de memória.<br>
Aqui está um exemplo de código que utiliza recursão para calcular o fatorial de um número. A cada chamada recursiva, a pilha armazena o valor de ‘X’ e o multiplica pelo próximo número menor, até que a condição base seja atingida, quando ‘X’ é menor ou igual a 1. Nesse momento, a recursão termina e o valor do fatorial é retornado.</p>
</blockquote>
<h3 id="exemplo-de-código-2">Exemplo de Código</h3>
<p><img class="paragraph" src="https://i.ibb.co/LJYrr72/Captura-de-tela-de-2023-09-21-09-20-03.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/fatorial.py">Copiar</a></p>
<h1 id="quicksort">Quicksort</h1>
<ol>
<li>A estratégia <strong>DC</strong>(<em>Dividir para Conquistar</em>) funciona por meio da <strong>divisão do problema</strong> em <strong>problemas menores</strong>.</li>
<li>Se você estiver utilizando <strong>DC</strong> em uma lista, o <strong>caso-base</strong> provavelmente será um <code>array</code> vazio ou com apenas um elemento.</li>
<li>Se você estiver implementando o <strong>quicksort</strong>, escolha um elemento aleatório como o <strong>pivô</strong>.</li>
<li>O tempo de execução médio do <strong>quicksort</strong> é <strong>O(n log n)!</strong></li>
<li>A constante, na notação <strong>Big O</strong>, pode ser relevante em alguns casos. Está é a razão pela qual o <strong>quicksort</strong> é mais rápido do que o <strong>mergesort</strong>.</li>
<li>A constante dificilmente, será relevante na comparação entre <strong>pesquisa simples</strong> e <strong>pesquisa binária</strong>, pois <strong>O(log n)</strong> é muito mais rápido do que <strong>O(n)</strong> quando sua lista é grande.</li>
</ol>
<blockquote>
<h3 id="pensamentos-3">Pensamentos</h3>
<p>O algoritmo Quicksort, conhecido por sua estratégia <a href="https://pt.wikipedia.org/wiki/Dividir_para_conquistar">“Dividir para Conquistar”</a>, é um método de ordenação para listas que geralmente é mais rápido e eficiente em comparação com outros métodos. Para entender como funciona, primeiro precisamos estabelecer um “caso-base” para evitar problemas. No Quicksort, o caso-base ocorre quando a lista tem apenas um elemento, nesse caso, “um único elemento não precisa ser ordenado”.<br>
A essência do Quicksort é a escolha de um elemento especial chamado de “pivô”. Embora seja possível escolher o pivô aleatoriamente, geralmente escolhemos um valor que faça sentido para o nosso contexto. Em seguida, dividimos a lista em duas partes: uma para elementos menores que o pivô e outra para elementos maiores. Isso é feito usando um loop que percorre a lista e direciona cada elemento para a lista de menores ou maiores, dependendo de sua relação com o pivô.<br>
Este código divide a lista em partes menores e maiores em relação ao pivô e, em seguida, chama a função Quicksort recursivamente para ordenar essas partes. O pivô é inserido entre as partes ordenadas, criando uma lista ordenada completa.</p>
</blockquote>
<h3 id="exemplo-de-código-3">Exemplo de Código:</h3>
<p><img class="paragraph" src="https://i.ibb.co/MVb2PjB/Captura-de-tela-de-2023-09-21-09-20-15.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/quicksort.py">Copiar</a></p>
<h1 id="tabelas-hash">Tabelas Hash</h1>
<ol>
<li>Você pode fazer uma tabela <code>hash</code> ao combinar uma função <code>hash</code> com um <code>array</code>.</li>
<li><strong>Colisões</strong> são <strong>problemas</strong>. É necessário haver uma <code>função</code> <code>hash</code> que minimize colisões.</li>
<li>As tabelas <code>hash</code> são boas para modelar relações entre dois itens.</li>
<li>Se o seu fator de carga for <strong>maior que 0.7</strong>, será necessário redimensionar a sua tabela <code>hash</code>.</li>
<li>As tabelas <code>hash</code> são utilizadas como cache de dados (como em um servidor da web, por exemplo).</li>
<li>Tabelas <code>hash</code> são ótimas para <strong>localizar duplicatas</strong>.</li>
</ol>
<blockquote>
<h3 id="pensamentos-4">Pensamentos</h3>
<p>As tabelas hash são estruturas de dados que se assemelham a listas e arrays, mas possuem propriedades distintas que as tornam especialmente úteis em diversas aplicações. Elas têm a capacidade de mapear chaves para valores, permitindo a recuperação eficiente de um valor com base em sua chave correspondente. No entanto, é importante destacar que colisões podem ocorrer em tabelas hash, diferentemente de listas e arrays convencionais. Isso acontece quando duas chaves diferentes são mapeadas para a mesma posição na tabela.<br>
A prevenção e tratamento de colisões em tabelas hash são aspectos cruciais de seu uso. Para evitar colisões, é essencial empregar uma função de hash eficaz, que distribua as chaves uniformemente ao longo da tabela. No caso de colisões, existem várias técnicas de resolução disponíveis, como encadeamento separado (onde cada posição da tabela contém uma lista ligada de valores) e resolução linear (tentativa de acomodar o valor em uma posição livre adjacente).<br>
As tabelas hash têm uma ampla gama de aplicações. Elas podem ser utilizadas como bancos de dados, caches de memória, ferramentas de verificação de integridade de dados e componentes essenciais em algoritmos de criptografia. Para que elas desempenhem seu papel com eficiência, é necessário escolher um tamanho adequado para a tabela, visando evitar colisões frequentes e garantir um funcionamento otimizado.</p>
</blockquote>
<h3 id="exemplo-de-código-4">Exemplo de Código</h3>
<p><img class="paragraph" src="https://i.ibb.co/yY8jcwh/Captura-de-tela-de-2023-09-21-09-22-42.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/hash.py">Copiar</a></p>
<h1 id="pesquisa-em-largura">Pesquisa em Largura</h1>
<ol>
<li>A pesquisa em largura lhe diz se há um caminho de <strong>A</strong> para <strong>B</strong>.</li>
<li>Se esse caminho <strong>existir</strong>, a pesquisa em largura lhe dará o <strong>caminho mínimo</strong>.</li>
<li>Se você tem um problema do tipo, “<strong>encontre o menor X</strong>”, tente modelar o seu problema utilizando <code>grafos</code> e use a pesquisa em largura para resolve-lo.</li>
<li>Um dígrafo contém setas e as relações seguem a direção das setas(<strong>Rama</strong> -> <strong>Adit</strong> significa “<strong>Rama</strong> deve dinheiro a <strong>Adit</strong>”).</li>
<li><code>Grafos</code> não direcionados não contêm setas, e a relação acontece nos dois sentidos (<strong>Ross</strong> - <strong>Rachel</strong> significa “<strong>Ross</strong> namorou <strong>Rachel</strong> e <strong>Rachel</strong> namorou <strong>Ross</strong>”).</li>
<li>Filas são <strong>FIFO</strong> (primeiro a entrar, primeiro a sair).</li>
<li>Pilhas <strong>LIFO</strong> (ultimo a entrar, primeiro a sair).</li>
<li>Você precisa verificar as pessoas na <strong>ordem</strong> em que elas <strong>foram adicionadas</strong> à lista de pesquisa. Portanto a lista de pesquisa deve ser uma fila; caso contrário, você não obterá o caminho mínimo.</li>
<li>Cada vez que você precisar verificar alguém, procure <strong>não</strong> verifica-lo novamente. Caso contrário, poderá acabar em um <em>loop infinito</em>.</li>
</ol>
<blockquote>
<h3 id="pensamentos-5">Pensamentos</h3>
<p>A pesquisa em largura é uma técnica relativamente simples, mas poderosa, amplamente utilizada para encontrar o caminho mais curto entre dois pontos em um grafo. Se esse caminho existir, a pesquisa em largura retornará o percurso que leva menos “tempo” ou etapas para ser concluído. Essa abordagem é frequentemente empregada em problemas modelados como grafos, como ilustrado no exemplo a seguir.</p>
<h3 id="grafo-em-forma-de-tabela">Grafo "<em>em forma de tabela"</em></h3>
<table>
<thead>
<tr>
<th>Pessoa</th>
<th>Amigos</th>
</tr>
</thead>
<tbody>
<tr>
<td>voce</td>
<td>alice, bob, claire</td>
</tr>
<tr>
<td>bob</td>
<td>anuj, peggy</td>
</tr>
<tr>
<td>alice</td>
<td>peggy</td>
</tr>
<tr>
<td>claire</td>
<td>thom, jhonny</td>
</tr>
<tr>
<td>anuj</td>
<td></td>
</tr>
<tr>
<td>peggy</td>
<td></td>
</tr>
<tr>
<td>thom</td>
<td></td>
</tr>
<tr>
<td>jhonny</td>
<td></td>
</tr>
</tbody>
</table><p>Neste exemplo, suponhamos que desejamos encontrar o vendedor de manga mais próximo a partir de “você”. Para fazer isso, podemos adotar uma abordagem de pesquisa em largura. Começamos a análise a partir de “você” e, em seguida, exploramos sistematicamente cada elemento, indo do mais próximo ao mais distante.<br>
Primeiro, examinamos os amigos diretos de “você” (Alice, Bob e Claire). Em seguida, investigamos os amigos dos amigos (Anuj e Peggy) e continuamos expandindo nossa busca até identificarmos o vendedor de manga.<br>
Essa técnica é eficaz na descoberta de rotas curtas em uma ampla variedade de contextos, desde redes sociais até sistemas de mapeamento de rotas. Ela oferece uma abordagem sistemática para explorar conexões e encontrar soluções de maneira eficiente.</p>
</blockquote>
<h3 id="exemplo-de-código-5">Exemplo de Código</h3>
<p><img src="https://i.ibb.co/Tmb4V3w/Captura-de-tela-de-2023-09-21-09-35-08.png" alt=""><br>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/pesquisa_em_largura.py">Copiar</a></p>
<h1 id="dijkstra">Dijkstra</h1>
<ol>
<li>A <code>pesquisa em largura</code> é usada para calcular o caminho <strong>mínimo</strong> para um grafo <strong>não</strong> ponderado.</li>
<li>O <code>algoritmo de Dijkstra</code> é usado para calcular o caminho <strong>mínimo</strong> para um <code>grafo ponderado</code>.</li>
<li>O <code>algoritmo de Dijkstra</code> <strong>funciona</strong> quando todos os pesos <strong>são positivos</strong>.</li>
<li>Se o seu <code>grafo</code> tiver pesos negativos, use o algoritmo de <a href="https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/">Bellman-Ford</a>,</li>
</ol>
<blockquote>
<h3 id="pensamentos-6">Pensamentos</h3>
<p> Algoritmo de Dijkstra é uma técnica usada para encontrar o caminho mais curto entre um ponto de partida e todos os outros pontos em um grafo ponderado. Ele é amplamente utilizado em problemas de roteamento, otimização e sistemas de navegação.<br>
A principal ideia por trás do algoritmo é a busca por caminhos mais curtos, começando pelo ponto de partida e gradualmente explorando os nós vizinhos. O algoritmo mantém um conjunto de nodos não processados e seus custos associados. Inicialmente, todos os custos são definidos como infinito, exceto o custo do nó de partida, que é definido como zero.<br>
Em cada iteração, o algoritmo seleciona o nó com o custo mais baixo entre os nodos não processados e o marca como processado. Em seguida, atualiza os custos dos nodos vizinhos se um caminho mais curto for encontrado através do nó atual. Este processo é repetido até que todos os nodos tenham sido processados ou até que o destino desejado seja alcançado.<br>
</p>
</blockquote>
<h3 id="exemplo-de-código-6">Exemplo de Código</h3>
<a href="https://ibb.co/9Y9P5Cd"><img src="https://i.ibb.co/12fcWw4/dijkstra.png" alt="dijkstra" border="0"></a><br /><a target='_blank'>
<a href="https://github.com/Caracioly/algoritmos/blob/main/codigos/dijkstra.py">Copiar</a></p>
</div>
</div>
</body>
</html>