Comparing algorithms and ADTs in algorithms · Comparando algoritmos e TADs em algoritmos
| English | Português |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | complexidade temporal |
| space complexity/speɪs kəmˈpleksɪti/ | complexidade espacial |
| depth-first/depθ fɜːst/ | profundidade-first |
| breadth-first/bredθ fɜːst/ | largura-first |
| binary tree/ˈbaɪnəri triː/ | árvore binária |
The algorithm that would outlive the universe
- A salesman must visit 25 cities and return home by the shortest route. Try every order and there are about $10^{23}$ of them. A machine checking a billion a second would take three million years.
- Add one more city and the work multiplies by 25. That is not a computer that needs to be faster; it is an approach that can never work, at any speed, on any hardware.
- Knowing that before you write the program is what complexity analysis is for. It is the difference between choosing an algorithm and discovering, months later, that yours does not scale.
- This lesson is Big-O 大O表示法 for time and space, and how ADTs shape the algorithms built on them.
O algoritmo que sobreviveria ao universo
- Um vendedor deve visitar 25 cidades e retornar para casa pela rota mais curta. Tente cada ordem e haverá cerca de $10^{23}$ delas. Uma máquina verificando um bilhão por segundo levaria três milhões de anos.
- Adicione mais uma cidade e o trabalho multiplica por 25. Isso não é um computador que precisa ser mais rápido; é uma abordagem que nunca funcionará, em qualquer velocidade, em qualquer hardware.
- Saber disso antes de escrever o programa é para que serve a análise de complexidade. É a diferença entre escolher um algoritmo e descobrir, meses depois, que o seu não escala.
- Esta aula é sobre Big-O 大O表示法 para tempo e espaço, e como as ADTs moldam os algoritmos construídos sobre elas.
Time complexity
- Time complexity 时间复杂度 describes how the running time grows with the input size $n$. It is written in Big-O notation, which keeps only the dominant term and drops constants.
- $O(1)$ constant, the time does not depend on $n$ at all. $O(\log n)$ logarithmic, as in binary search. $O(n)$ linear, as in linear search. $O(n \log n)$, the good sorts. $O(n^2)$ quadratic, as in bubble and insertion sort.
- The reason constants are dropped: they are swamped. An $O(n^2)$ algorithm might beat an $O(n \log n)$ one for $n = 10$, but at $n = 10{,}000$ nothing about the constants can save it.
The curves cross once, and after that the order decides everything
Complexidade de tempo
- Complexidade de tempo 时间复杂度 descreve como o tempo de execução cresce com o tamanho da entrada $n$. Ela é escrita em notação Big-O, que mantém apenas o termo dominante e elimina constantes.
- $O(1)$ constante, o tempo não depende de $n$ de forma alguma. $O(\log n)$ logarítmica, como na busca binária. $O(n)$ linear, como na busca linear. $O(n \log n)$, as boas ordenações. $O(n^2)$ quadrática, como na ordenação por bolha e inserção.
- A razão para eliminar constantes: elas são insignificantes. Um algoritmo $O(n^2)$ pode vencer um $O(n \log n)$ para $n = 10$, mas em $n = 10{,}000$ nada nas constantes pode salvá-lo.
As curvas se cruzam uma vez, e depois disso a ordem decide tudo
How running time grows with n · Como o tempo de execução cresce com n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs. · Deslize n para cima e compare as curvas: O(1) e O(log n) permanecem quase planas, O(n) sobe consistentemente, O(n²) explode. É por isso que o Big-O — não um cronômetro — é como comparamos algoritmos em entradas grandes.
Which Big-O describes binary search? · Qual Big-O descreve a busca binária?
Halving the range each step is logarithmic — O(log n). · Reduzir pela metade o intervalo a cada passo é logarítmico — O(log n).
Which Big-O describes bubble sort in the worst case? · Qual Big-O descreve a ordenação por bolha no pior caso?
Two nested loops over n elements give O(n²). · Dois loops aninhados sobre n elementos dão O(n²).
Match each algorithm to its time complexity. · Combine cada algoritmo com sua complexidade de tempo.
Linear search is O(n), binary search O(log n), bubble sort O(n²). · Busca linear é O(n), busca binária O(log n), ordenação por bolha O(n²).
Worked example: what doubling the input does
- An algorithm takes 4 seconds on 1,000 items. Estimate its time on 2,000 items if it is $O(n)$, then if it is $O(n^2)$.
- $O(n)$: doubling $n$ doubles the time, so about 8 seconds.
- $O(n^2)$: doubling $n$ quadruples the time, so about 16 seconds. At 10,000 items it would be 100 times the original, about 400 seconds.
- $O(\log n)$ would add only a single step, and $O(1)$ would not change at all. Reason from the order, not from a formula.
Exemplo resolvido: o que dobrar a entrada faz
- Um algoritmo leva 4 segundos para processar 1,000 itens. Estime o tempo necessário para 2,000 itens se a complexidade for $O(n)$, e depois se for $O(n^2)$.
- $O(n)$: dobrar $n$ dobra o tempo, então cerca de 8 segundos.
- $O(n^2)$: dobrar $n$ quadruplica o tempo, ou seja, cerca de 16 segundos. Com 10,000 itens, seria 100 vezes o original, cerca de 400 segundos.
- $O(\log n)$ adicionaria apenas um passo, e $O(1)$ não mudaria de forma alguma. Raciocine pela ordem, não por uma fórmula.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000? · Um algoritmo O(n²) leva 4 segundos para 1,000 itens. Aproximadamente, quantos segundos ele levará para 2,000?
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8. · Dobrar n quadruplica o tempo de um algoritmo O(n quadrado). O mesmo dobramento levaria um algoritmo O(n) de 4 segundos para 8.
Space complexity
- Space complexity 空间复杂度 is the extra memory an algorithm needs, beyond the input itself.
- Bubble and insertion sort use $O(1)$ extra memory: they work in place, needing only a couple of variables. Merge sort uses $O(n)$, since it builds a second array.
- Recursion uses stack memory proportional to its depth, because every unfinished call keeps its own frame.
- There is often a time and memory trade-off: storing results to avoid recomputing them, as memoisation does, buys speed with space.
Complexidade de espaço
- Complexidade de espaço 空间复杂度 é a memória extra que um algoritmo precisa, além da própria entrada.
- Bolha e inserção usam $O(1)$ de memória extra: funcionam in-place, precisando apenas de algumas variáveis. Merge sort usa $O(n)$, pois constrói um segundo array.
- Recursão usa memória de pilha proporcional à sua profundidade, porque toda chamada inacabada mantém seu próprio frame.
- Há frequentemente um compromisso entre tempo e memória: armazenar resultados para evitar recalcular, como memoização faz, compra velocidade com espaço.
What else decides the choice
- Big-O is about growth, not absolute speed. For a small $n$, a simple $O(n^2)$ algorithm can beat a complicated $O(n \log n)$ one, and it is easier to write correctly.
- Stability matters when a list is already ordered by another field. Simplicity matters because a simple algorithm has fewer places to hide a bug.
- The honest answer to "which algorithm" often names the order and the conditions: this one, because $n$ is large and the data arrives unsorted.
O que mais decide a escolha
- Big-O trata de crescimento, não de velocidade absoluta. Para uma pequena $n$, um simples $O(n^2)$ pode vencer um complexo $O(n \log n)$, e é mais fácil escrever corretamente.
- Estabilidade importa quando uma lista já está ordenada por outro campo. Simplicidade importa porque um algoritmo simples tem menos lugares para esconder um bug.
- A resposta honesta a "qual algoritmo" geralmente nomeia a ordem e as condições: este, porque $n$ é grande e os dados chegam desordenados.
An "in place" sort: · Uma ordenação "in-place":
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space. · Algoritmos in-place (como ordenação por bolha e inserção) ordenam dentro do array original, usando espaço extra constante.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items? · Por que a complexidade de espaço da ordenação por bolha é O(1) mesmo ordenando um array de n itens?
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth. · Ela ordena in-place. A ordenação por fusão é O(n) porque constrói um segundo array, e a recursão custa memória proporcional à sua profundidade.
ADTs inside algorithms
- The abstract data types from topic 10 are the machinery algorithms are built from, and choosing one shapes the algorithm.
- A stack gives depth-first 深度优先 search: push the neighbours, take the most recent, and the search plunges down one path before backing up. Recursion uses the call stack for exactly this.
- A queue gives breadth-first 广度优先 search: enqueue the neighbours, take the oldest, and the search spreads outward in rings, which is what finds the shortest path in an unweighted graph.
- A binary tree 二叉树 keeps values in order so that a search discards half the remaining nodes at each step, giving binary search's $O(\log n)$ over a structure that can also grow.
ADTs dentro dos algoritmos
- As abstrações de tipos de dados do tópico 10 são a maquinaria da qual os algoritmos são construídos, e escolher uma molda o algoritmo.
- Uma pilha oferece busca depth-first 深度优先: empilha os vizinhos, pega o mais recente, e a busca mergulha em um caminho antes de retroceder. Recursão usa a pilha de chamadas exatamente para isso.
- Uma fila oferece busca breadth-first 广度优先: enfileira os vizinhos, pega o mais antigo, e a busca se espalha em anéis para fora, o que encontra o caminho mais curto em um grafo não ponderado.
- Uma árvore binária 二叉树 mantém valores em ordem para que uma busca descarte metade dos nós restantes a cada passo, dando a busca binária's $O(\log n)$ sobre uma estrutura que também pode crescer.
Which statements about Big-O are correct? Select all · todos that apply. · Quais afirmações sobre Big-O estão corretas? Selecione todas as que se aplicam.
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes. · Big-O não diz nada sobre segundos; é sobre crescimento. É por isso que o ponto de virada com um algoritmo mais simples existe em tamanhos pequenos.
Worked example: the same graph, two searches
- A maze is explored from one entrance. Contrast using a stack with using a queue.
- With a stack, the most recently found path is explored next, so the search goes deep down one route until it dead-ends, then backtracks. It uses memory proportional to the depth of the path.
- With a queue, the oldest found path is explored next, so the search examines everything one step away, then everything two steps away. It finds the shortest route first, but holds every position at the current distance in memory.
- Name the ADT, name the resulting order of exploration, and name the consequence.
Exemplo resolvido: o mesmo grafo, duas buscas
- Um labirinto é explorado a partir de uma entrada. Contraste usar uma pilha com usar uma fila.
- Com uma pilha, o caminho encontrado mais recentemente é explorado a seguir, então a busca vai fundo em uma rota até encontrar um beco sem saída, depois retrocede. Usa memória proporcional à profundidade do caminho.
- Com uma fila, o caminho encontrado mais antigo é explorado a seguir, então a busca examina tudo a um passo, depois tudo a dois passos. Encontra a rota mais curta primeiro, mas guarda todas as posições na distância atual na memória.
- Nomeie a ADT, nomeie a ordem resultante de exploração e nomeie a consequência.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal. · Uma pilha (LIFO) naturalmente direciona uma travessia em profundidade, enquanto uma fila (FIFO) direciona uma travessia em largura.
The ADT you choose decides the search order — stack goes deep first, queue explores level by level. · O TAD que você escolhe decide a ordem de busca — pilha vai fundo primeiro, fila explora nível por nível.
Match each ADT to the search it produces and its consequence. · Combine cada TAD com a busca que ele produz e sua consequência.
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide. · Mais recente primeiro, ou mais antigo primeiro. Essa única escolha decide se a busca vai fundo ou larga.
Marks that slip away
- Big-O describes growth with input size, not seconds. "It is fast" is not a complexity answer.
- Doubling the input doubles an $O(n)$ time and quadruples an $O(n^2)$ one. Reason from the order.
- Space complexity is the extra memory, which is why an in-place sort is $O(1)$ even though the array is size $n$.
- Stack gives depth-first, queue gives breadth-first. Getting that pair the right way round is the whole of several questions.
Marcas que escapam
- Big-O descreve crescimento com o tamanho da entrada, não segundos. "É rápido" não é uma resposta de complexidade.
- Dobrar a entrada dobra um tempo $O(n)$ e quadruplica um $O(n^2)$. Raciocine pela ordem.
- Complexidade de espaço é a memória extra, que é por que uma ordenação in-place é $O(1)$ mesmo que o array tenha tamanho $n$.
- Pilha dá depth-first, fila dá breadth-first. Acertar esse par no lugar certo é o cerne de várias questões.
You've got it
- time complexity in Big-O describes growth with $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constants are dropped because at scale the order decides
- doubling $n$ doubles $O(n)$ and quadruples $O(n^2)$; the crossover with a "worse" algorithm only exists for small $n$
- space complexity is the extra memory: in place sorts are $O(1)$, merge sort is $O(n)$, and recursion costs stack depth
- a stack gives depth-first search, a queue gives breadth-first, and a binary tree halves the remaining nodes at each step
Entendeu?
- complexidade de tempo em Big-O descreve crescimento com $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constantes são eliminadas porque em escala a ordem decide
- dobrar $n$ dobra $O(n)$ e quadruplica $O(n^2)$; o ponto de interseção com um algoritmo "pior" só existe para pequenas $n$
- complexidade de espaço é a memória extra: ordenações in place são $O(1)$, merge sort é $O(n)$, e recursão custa profundidade de pilha
- uma pilha dá busca depth-first, uma fila dá breadth-first, e uma árvore binária reduz a metade os nós restantes a cada passo