Lançado · em melhoria
Algorithm
Aprenda a analisar com a notação Big O como o tempo e a memória de um algoritmo crescem com o tamanho da entrada, e a confirmar isso medindo.
A análise de complexidade descreve quanto o tempo e a memória de que um algoritmo precisa crescem à medida que a entrada aumenta. Em vez de segundos, que dependem do hardware e da linguagem, ela conta operações básicas em função do tamanho da entrada n e mantém apenas o termo dominante. O resultado é escrito em notação assintótica: Big O para um limite superior, Big Omega para um limite inferior e Big Theta para um limite justo.
Ela importa porque, quando os dados crescem, a diferença entre ordens de crescimento supera qualquer fator constante. Uma rotina O(n²) que vai bem com mil itens pode levar horas com um milhão, enquanto uma O(n log n) termina em segundos. A complexidade orienta a escolha de estruturas de dados, a leitura dos limites de entrada de um problema de programação, a busca de custos escondidos em code review e a estimativa de se um sistema vai escalar.
Comece contando operações em laços simples e aprendendo as classes mais comuns: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) e O(n!). Depois avance para melhor caso, caso médio e pior caso, análise amortizada, complexidade de espaço e resolução de recorrências com o teorema mestre. Confira sempre o raciocínio com um experimento de duplicação: meça o código com n e com 2n e compare a razão.
O, Ω e Θ dão limites superiores, inferiores e justos para o crescimento, ignorando constantes e termos de ordem menor.
Blocos em sequência somam seus custos, laços aninhados os multiplicam e reduzir o problema pela metade a cada passo leva a um logaritmo.
Distribui o custo por toda uma sequência de operações; por isso adicionar a um array dinâmico é O(1), mesmo que às vezes seja preciso copiar tudo.
Memória auxiliar e profundidade de recursão também contam, e o teorema mestre resolve recorrências de divisão e conquista.
O script resolve o mesmo problema de duas formas: testando todos os pares ou percorrendo a lista uma vez e guardando em um dicionário os valores já vistos. Medindo as duas com timeit para n = 500, 1.000 e 2.000, cada duplicação deixa a versão quadrática cerca de quatro vezes mais lenta e a linear cerca de duas.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySeis capítulos que levam você da instalação aos conceitos essenciais de Análise de complexidade.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Análise de complexidade.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.