Comparing algorithms and ADTs in algorithms
Introduzido| English | Significado |
|---|---|
| Big-O/bɪɡ əʊ/ | Notação 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 |
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.
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
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.
Which Big-O describes binary search?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Linear search is O(n), binary search O(log n), bubble sort O(n²).
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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8.
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.
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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
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 todos that apply.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
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.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
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.
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