Passo 1 de 9
Definir o tamanho da entrada e o trabalho contado
Escolha o que representa o tamanho de uma entrada e declare qual trabalho será contado antes de comparar algoritmos.
Trilha de aprendizado · Nível 14 · Tutorial 1
Estime como o trabalho e a memória necessária crescem com o tamanho da entrada, distinguindo limites assintóticos de tempos medidos em uma máquina.
Definir o tamanho da entrada e o trabalho contado
Escolha o que representa o tamanho de uma entrada e declare qual trabalho será contado antes de comparar algoritmos. 2 min
Interpretar O grande como limite de crescimento
Simplifique contagens de trabalho e use O grande para descrever crescimento, não duração exata. 2 min
Reconhecer as principais ordens de crescimento
Compare ordens de crescimento comuns e entenda por que reduções sucessivas pela metade produzem um custo logarítmico. 3 min
Compor custos de trechos e laços
Some custos de blocos e conte as execuções reais dos laços para classificar trechos de código. 3 min
Incluir o trabalho das operações do Python
Veja como chamadas curtas podem esconder percursos, cópias e ordenação ao estimar o tempo de uma função. 2 min
Contar chamadas e profundidade na recursão
Estime o trabalho total e a profundidade máxima de padrões recursivos simples, distinguindo a árvore completa de chamadas do caminho que fica ativo. 3 min
Estimar a memória necessária ao mesmo tempo
Separe entrada, saída e memória auxiliar para estimar quanto armazenamento uma função precisa manter simultaneamente. 3 min
Distinguir pior caso, caso médio e amortização
Qualifique custos de busca e de inserção ao final de listas, separando pior caso, caso médio e custo amortizado. 4 min
Aplicar um roteiro completo de análise
Integre a análise de tempo e memória em exemplos completos e separe estimativas assintóticas de medições reais. 4 min
Passo 1 de 9
Escolha o que representa o tamanho de uma entrada e declare qual trabalho será contado antes de comparar algoritmos.
Antes de analisar uma função, defina o tamanho relevante da entrada. Ele costuma ser uma quantidade, não o valor numérico de um argumento.
Por exemplo, para range(limite), se o trabalho percorre os valores produzidos, importa quantos valores são visitados. Já um argumento chamado idade=80 não significa, por si só, que a entrada tem tamanho 80.
Duas coleções podem crescer separadamente: use uma variável para cada dimensão.
Use n para a quantidade de itens de uma coleção e m para a de outra. Não suponha que elas crescem juntas.
A análise começa escolhendo uma operação que represente o trabalho, como uma comparação ou a atualização de um contador. Declare também a hipótese usada: neste início, considere que operações sobre valores de tamanho limitado têm custo constante.
Essa hipótese não vale automaticamente para todo objeto: inteiros enormes, textos muito longos ou métodos personalizados podem exigir uma análise diferente.
Considere n como a quantidade de valores em numeros.
def contar_positivos(numeros):
total = 0
for numero in numeros:
if numero > 0: # operação observada: comparação
total += 1 # atualização do contador
return totalDica
Contar comparações estima trabalho. Estimar armazenamento pergunta quantos valores ficam guardados ao mesmo tempo. Medir segundos ou bytes depende da máquina, da implementação e das entradas reais. Vamos manter essas perguntas separadas.
Relacione cada situação à forma adequada de representar o tamanho da entrada.
Toque em um item e depois no par correspondente.
Para a função contar_positivos, escreva qual operação você contaria e uma hipótese de custo que está adotando.
Escreva pelo menos 20 caracteres (0/20).
Passo 2 de 9
Simplifique contagens de trabalho e use O grande para descrever crescimento, não duração exata.
Depois de contar o trabalho de uma função, usamos O grande para descrever como esse trabalho pode crescer quando a entrada fica suficientemente grande.
Dizer que um custo é O(f(n)) significa que, a partir de certo tamanho de entrada, ele não ultrapassa uma constante multiplicada por f(n). A constante representa detalhes como quantas operações semelhantes ocorrem em cada etapa; ela não muda a tendência de crescimento.
A curva de trabalho pode variar nos tamanhos pequenos, mas fica abaixo de uma versão ampliada da função de referência depois de certo ponto.
O foco está no crescimento para entradas grandes, não em uma contagem exata para cada valor de n.
Exemplo
Se uma contagem de trabalho é 3n + 12, para entradas grandes o termo 3n domina o 12, e o fator 3 não altera a ordem de crescimento. Portanto:
3n + 12 → O(n)
Se a contagem é 2n² + 7n + 4, o termo quadrático cresce mais rápido que os demais:
2n² + 7n + 4 → O(n²)
Uma quantidade fixa, como 25, não cresce com n:
25 → O(1)
Dica
Em expressões de uma variável, mantenha o termo que mais cresce e descarte seus fatores constantes. Essa é uma simplificação assintótica, não uma afirmação de que os outros termos nunca são executados.
A contagem 5n² + 20n + 9 é classificada como ____.
Um custo O(n) também está dentro de O(n²), pois uma função linear acaba ficando abaixo de alguma constante vezes n². Ainda assim, O(n) é o limite superior mais informativo nesse caso.
O grande também não informa automaticamente se a análise é de pior caso, nem converte custo em segundos ou bytes exatos. Máquina, implementação, dados e tamanhos pequenos influenciam medições reais.
Se uma função é O(n) e outra é O(n²), a primeira obrigatoriamente será mais rápida em qualquer computador e para toda entrada pequena.
Passo 3 de 9
Compare ordens de crescimento comuns e entenda por que reduções sucessivas pela metade produzem um custo logarítmico.
Além de O(1), O(n) e O(n²), use estas referências para comparar tendências:
Elas descrevem crescimento assintótico, não segundos medidos no seu computador.
Observe que as curvas podem parecer próximas em entradas pequenas, mas se afastam muito à medida que n aumenta.
Para entradas grandes: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Quando cada etapa reduz o tamanho restante por um fator constante, a quantidade de etapas é logarítmica. Por exemplo, partindo de 1.024 e dividindo por 2 repetidamente:
1.024 → 512 → 256 → … → 1
São 10 reduções. Como 2¹⁰ = 1.024, essa quantidade é log₂(1.024) = 10. Em uma estimativa assintótica, escrever O(log n) basta.
Exemplo
Usar log₂ n, log₁₀ n ou log₃ n altera apenas um fator constante. Por isso, todas essas formas pertencem a O(log n).
O que caracteriza essa ordem é a redução repetida por uma proporção fixa, e não a base escolhida para escrever o logaritmo.
Dica
Se dobrar n acrescenta aproximadamente uma etapa de redução pela metade, a tendência é logarítmica. Isso não informa a duração exata de cada etapa.
Em O(n log n), há n unidades de trabalho, e cada uma vem acompanhada de um fator que cresce logaritmicamente.
Como referência matemática, se n = 1.024, então log₂ n = 10 e n log₂ n = 10.240 unidades de referência. Isso cresce mais que n, mas muito menos que n², que seria 1.048.576 nessa mesma entrada.
Atenção
Esses números comparam funções de referência sob hipóteses simplificadas. Uma implementação O(n²) pode terminar antes de uma O(n log n) para entradas pequenas, dependendo de constantes, dados e máquina. A medição será tratada adiante.
Coloque as funções em ordem de crescimento assintótico, da menor para a maior.
Uma rotina reduz um tamanho de 1.024 pela metade a cada etapa até chegar a 1. Quantas etapas de redução ela faz?
Passo 4 de 9
Some custos de blocos e conte as execuções reais dos laços para classificar trechos de código.
Quando blocos são executados um depois do outro, some seus trabalhos. Por exemplo, um percurso de n itens seguido de um percurso de m itens custa O(n + m). Não transforme isso em O(n): n e m são dimensões independentes.
Se os dois trechos dependem da mesma dimensão, como n + n, a soma é 2n e simplifica para O(n). A simplificação vem depois da contagem.
Compare os dois desenhos: percursos separados somam; cada item de uma coleção combinado com cada item da outra multiplica.
Dois percursos separados: n + m. Todos os pares possíveis: n vezes m.
Exemplo
for item in lista_a executa n vezes e for item in lista_b executa m vezes: trabalho proporcional a n + m.
Já colocar o segundo percurso dentro do primeiro executaria o corpo uma vez para cada par (item_a, item_b): n · m vezes.
Em um aninhamento, some o trabalho interno ao longo das iterações externas. Só multiplique diretamente quando o laço interno tem o mesmo limite em todas as voltas.
Um laço externo com n voltas e um interno com limite fixo de 3 executa cerca de 3n ações: O(n), não O(n²). Já um limite interno que cresce com a posição externa forma uma soma triangular.
Considere apenas as atualizações de total como trabalho constante.
# 1. Limite fixo: 3 atualizações para cada item
for item in valores: # n voltas
for tentativa in range(3):
total += 1 # 3n atualizações -> O(n)
# 2. Grade completa: n atualizações para cada item
for esquerda in valores: # n voltas
for direita in valores: # n voltas em cada volta externa
total += 1 # n * n atualizações -> O(n²)
# 3. Triângulo: o limite interno depende de i
for i in range(n):
for j in range(i):
total += 1 # 0 + 1 + ... + (n - 1) -> O(n²)A forma das execuções revela por que os dois últimos trechos são quadráticos, embora o triângulo não execute exatamente n² atualizações.
Grade: n × n. Triângulo: 0 + 1 + ... + (n − 1); ambos têm ordem quadrática.
Se cada um dos n itens inicia uma redução sucessiva pela metade, o trabalho interno é O(log n) para cada item. Repetido n vezes, o total é O(n log n).
Conte as execuções do while; não basta olhar o número de níveis de indentação.
Suponha que limite seja proporcional a n e que as operações do corpo tenham custo constante.
passos = 0
for item in valores: # n itens
tamanho = len(valores)
while tamanho > 1: # reduz pela metade: O(log n) voltas
tamanho //= 2
passos += 1
# Total: n grupos de O(log n) passos -> O(n log n)Relacione cada descrição à ordem de crescimento mais informativa.
Toque em um item e depois no par correspondente.
Considere que comparacoes += 1 tem custo constante e que n é o tamanho de valores. Qual é a ordem de crescimento do trabalho? Justifique pela contagem.
comparacoes = 0
for i in range(n):
for j in range(i):
comparacoes += 1Escreva pelo menos 40 caracteres (0/40).
Dica
for.
Passo 5 de 9
Veja como chamadas curtas podem esconder percursos, cópias e ordenação ao estimar o tempo de uma função.
A quantidade de linhas não determina a ordem de crescimento. Ao analisar uma função, considere o que cada operação executa internamente.
No modelo usual para listas, len(valores) e valores[i] são O(1): obtêm o tamanho ou um elemento por posição sem percorrer a lista. Já alvo in valores pode examinar elemento por elemento, portanto é O(n) no pior caso.
Compare uma consulta direta com uma busca que pode varrer a lista.
Índice e tamanho usam informação direta; pertencimento em lista pode exigir uma varredura.
Dica
Estas classificações assumem elementos de tamanho limitado e comparações de custo constante. Comparar textos muito longos ou objetos com comparações personalizadas pode acrescentar outro custo.
Considere itens com n elementos e k elementos na fatia.
tem_erro = "erro" in itens # O(n) no pior caso
soma = sum(itens) # O(n)
inicio = itens[:k] # O(k)
ordenados = sorted(itens) # O(n log n)sum(itens) agrega todos os elementos e pode percorrê-los. A fatia itens[:k] constrói uma nova lista com k referências, então seu tempo é O(k). sorted(itens) ordena n elementos em O(n log n), supondo comparações O(1).
Uma fatia não é gratuita só porque aparece em uma expressão curta. Aqui estamos estimando tempo; a memória adicional dessa cópia será tratada depois.
Considere uma lista com n elementos e uma fatia com k elementos.
Toque em um item e depois no par correspondente.
clientes tem n elementos e bloqueados tem m elementos.
def contar_liberados(clientes, bloqueados):
total = 0
for cliente in clientes:
if cliente not in bloqueados:
total += 1
return totalO laço externo percorre n clientes. Em cada volta, cliente not in bloqueados pode fazer uma busca linear em uma lista de m elementos. O trabalho total é O(nm), não O(n): uma expressão curta está dentro de outra repetição.
Esse é um limite de pior caso para a busca em lista. Não conclua, por essa ordem, quantos segundos a função levará em uma máquina específica.
Para uma lista valores de tamanho n, considere sum(valores[:k]), com k ≤ n. Qual estimativa temporal é mais informativa?
Passo 6 de 9
Estime o trabalho total e a profundidade máxima de padrões recursivos simples, distinguindo a árvore completa de chamadas do caminho que fica ativo.
Ao analisar uma função recursiva, separe três perguntas:
A árvore de chamadas mostra todas as chamadas que ocorrerão. Já a profundidade acompanha apenas um caminho, da chamada inicial até um caso base.
A mesma recursão pode criar muitos nós ao longo da execução, mas manter ativo apenas um ramo por vez.
Nós da árvore representam chamadas totais; o caminho destacado representa a profundidade máxima.
Cada chamada faz trabalho local constante e delega o restante para n - 1.
def contar_regressivo(n):
if n == 0:
return 0
return 1 + contar_regressivo(n - 1)Exemplo
As chamadas formam uma corrente:
contar_regressivo(4) → 3 → 2 → 1 → 0
Há cerca de n + 1 chamadas. Como cada uma faz O(1) de trabalho local, o tempo total é O(n). O maior caminho ativo também tem cerca de n + 1 chamadas, então a profundidade é proporcional a n.
Agora o tamanho do problema cai por um fator constante a cada chamada.
def contar_metades(n):
if n <= 1:
return 1
return 1 + contar_metades(n // 2)Para n = 16, os argumentos seguem 16 → 8 → 4 → 2 → 1. Cada redução pela metade aproxima o caso base; por isso há O(log n) chamadas, tempo O(log n) e profundidade O(log n), assumindo trabalho local O(1).
Sem reutilizar resultados, cada chamada não base abre duas novas chamadas.
def bifurcar(n):
if n == 0:
return 1
return bifurcar(n - 1) + bifurcar(n - 1)No nível 0 há 1 chamada; no próximo, 2; depois, 4; e assim por diante. A árvore inteira tem ordem de O(2^n) nós. Com trabalho local O(1), o tempo é O(2^n).
Porém, uma chamada termina uma ramificação antes de executar a outra. Assim, o maior caminho ativo vai de n até 0 e tem profundidade O(n) — não O(2^n).
Atenção
Essas classificações supõem que cada chamada faz apenas trabalho local constante além das chamadas recursivas. Criar uma fatia, copiar uma coleção ou percorrer parte da entrada dentro de cada chamada adiciona trabalho e pode mudar a análise.
Considere trabalho local O(1) e ausência de cópias ou percursos extras dentro das chamadas.
Toque em um item e depois no par correspondente.
Por que bifurcar(n) tem trabalho total O(2^n), mas profundidade O(n)? Explique usando a diferença entre toda a árvore de chamadas e um único caminho ativo.
Escreva pelo menos 80 caracteres (0/80).
Passo 7 de 9
Separe entrada, saída e memória auxiliar para estimar quanto armazenamento uma função precisa manter simultaneamente.
Ao analisar espaço, separe três parcelas:
n referências, a entrada ocupa O(n).k elementos, a saída ocupa O(k).Essa convenção evita esconder custos diferentes em uma única expressão. Uma função pode ter entrada O(n), saída O(1) e memória auxiliar O(1), por exemplo.
Para a memória auxiliar, conte o espaço extra que está vivo no mesmo instante de maior uso — o pico simultâneo.
Dica
Se uma estrutura temporária é criada, usada e liberada antes de outra ser criada, o espaço relevante é o maior pico entre elas, não a soma das duas. A análise de espaço pergunta: “qual é o máximo adicional mantido ao mesmo tempo?”
A entrada já é a lista valores. A função mantém apenas total e valor durante o percurso.
def contar_positivos(valores):
total = 0
for valor in valores:
if valor > 0:
total += 1
return totalExemplo
Para contar_positivos(valores), se valores tem n elementos:
total e pela variável do laço.Percorrer n elementos leva tempo linear, mas não exige guardar n elementos adicionais.
A fatia é criada antes de sum percorrê-la.
def somar_primeira_metade(valores):
metade = valores[:len(valores) // 2]
return sum(metade)Com n elementos de entrada, metade tem aproximadamente n/2 referências. Logo, essa cópia rasa acrescenta memória auxiliar O(n), embora cada objeto apontado não seja duplicado por causa da fatia.
O mesmo raciocínio vale para uma cópia rasa com valores[:]: há um novo contêiner proporcional ao número de referências copiadas.
A lista pares permanece viva até o retorno.
def pares_positivos(valores):
pares = []
for valor in valores:
if valor > 0 and valor % 2 == 0:
pares.append(valor)
return paresSe k valores passam pelo filtro, a saída materializada ocupa O(k). Como pares é justamente o resultado devolvido, informe normalmente: entrada O(n), saída O(k) e memória auxiliar O(1), além do armazenamento da saída.
Processar cada item um por vez pode evitar uma coleção temporária, mas não faz desaparecer uma entrada que já chegou como lista materializada.
Para observar o comportamento, use valores pequenos de n, como 4 ou 5.
def caminhos(n):
if n == 0:
return 1
return caminhos(n - 1) + caminhos(n - 1)caminhos faz duas chamadas recursivas para n - 1, então o total de chamadas cresce como O(2^n). Porém, uma chamada termina antes de a outra começar: a maior cadeia ativa reduz n até zero. Se cada chamada guarda apenas estado constante, a pilha usa O(n), proporcional à profundidade máxima, e não ao total de nós da árvore de chamadas.
Considere uma entrada valores com n elementos e esta função. Se ela devolve k elementos, qual descrição está correta?
def selecionar(valores):
selecionados = []
for valor in valores:
if valor > 10:
selecionados.append(valor)
return selecionadosAnalise a função abaixo para uma lista valores de tamanho n. Informe a memória da entrada, da saída e a memória auxiliar. Explique por que a fatia importa.
def total_copiado(valores):
copia = valores[:]
return sum(copia)Escreva pelo menos 80 caracteres (0/80).
Passo 8 de 9
Qualifique custos de busca e de inserção ao final de listas, separando pior caso, caso médio e custo amortizado.
Considere uma busca que percorre uma lista e para assim que encontra o alvo. Para listas com o mesmo tamanho n, o trabalho depende da entrada:
O pior caso é o maior custo entre entradas de mesmo tamanho: aqui, O(n). Isso não é a definição de O grande; O grande continua sendo um limite de crescimento. É preciso declarar qual caso está sendo analisado.
A mesma lista de tamanho n pode exigir quantidades diferentes de comparações.
A função encerra assim que encontra o valor.
def contem(valores, alvo):
for valor in valores:
if valor == alvo:
return True
return FalseExemplo
Se o alvo está presente e sua posição é uniformemente distribuída entre as n posições, a busca faz, em média, aproximadamente (n + 1) / 2 comparações. Portanto, o custo médio é O(n).
Essa conclusão depende da hipótese de distribuição. Se os alvos mais procurados costumam estar no início, a média observada pode ser menor. Sem declarar como as entradas são distribuídas, não há um único “caso médio” definido.
Relacione cada termo à sua descrição.
Toque em um item e depois no par correspondente.
Uma lista dinâmica mantém espaço de capacidade além dos elementos já usados. Em geral, um append ocupa uma posição livre: custo O(1).
Quando a capacidade se esgota, a lista precisa obter um bloco maior e copiar as referências dos elementos atuais. Se havia n elementos, essa chamada específica pode custar O(n). Não é necessário conhecer a fórmula de crescimento usada pela implementação para analisar a ideia.
Há cópia no redimensionamento, mas ele não ocorre a cada append.
Exemplo
Partindo de uma lista vazia, faça N chamadas de append. Algumas são caras por causa dos redimensionamentos, mas muitas apenas ocupam uma vaga. Com crescimento de capacidade por um fator constante, o trabalho total da sequência é O(N).
Por isso, cada inserção ao final é dita O(1) amortizado: o custo total O(N) é distribuído pelas N operações. Não significa que toda chamada individual custa O(1), nem é uma média baseada em probabilidade.
Se append é O(1) amortizado, então cada chamada de append isoladamente custa O(1).
Dizer que uma busca linear tem custo médio O(n) exige explicitar uma hipótese sobre as entradas, como a posição do alvo.
Passo 9 de 9
Integre a análise de tempo e memória em exemplos completos e separe estimativas assintóticas de medições reais.
Ao analisar uma função, siga este roteiro: 1. defina as dimensões da entrada; 2. declare as hipóteses de custo; 3. identifique o trabalho relevante; 4. componha as repetições; 5. simplifique a expressão; 6. informe o caso analisado e separe entrada, saída e memória auxiliar.
Considere n = len(valores_a), m = len(valores_b) e k como a quantidade de pares cuja soma supera limite. Não suponha que n e m crescem juntos.
As duas funções devolvem a quantidade de pares válidos.
def contar_com_lista(valores_a, valores_b, limite):
pares_validos = []
for a in valores_a:
for b in valores_b:
if a + b > limite:
pares_validos.append((a, b))
return len(pares_validos)
def contar_com_contador(valores_a, valores_b, limite):
total = 0
for a in valores_a:
for b in valores_b:
if a + b > limite:
total += 1
return totalCada elemento de valores_a é comparado com cada elemento de valores_b.
As duas versões examinam n × m pares. Só a primeira mantém os k pares válidos simultaneamente.
Produza uma análise para as duas funções do código. Declare uma hipótese de custo constante, justifique o tempo em função de n e m e informe a memória auxiliar de cada versão em função de k. Considere que ambas devolvem apenas um inteiro e que as listas de entrada já existem.
Escreva pelo menos 180 caracteres (0/180).
Em uma recursão com duas chamadas sobre n - 1, sem reutilizar resultados, a árvore pode ter trabalho total O(2n). Porém, em um instante há apenas um caminho de chamadas ativo: se cada chamada guarda estado constante, a pilha máxima é O(n), não O(2n).
Uma função faz duas chamadas recursivas com argumento n - 1, tem caso base em n == 0 e realiza trabalho local constante. Sem memoização, qual análise está correta?
Resumo
Use a estimativa para explicar como o custo cresce; use uma medição para investigar a duração observada em um cenário concreto.
Parabéns! Você concluiu: Estimar tempo e memória com notação O grande
Muito bem! Agora você consegue justificar uma estimativa de tempo e memória sem confundir ordem de crescimento com segundos ou bytes exatos.
Milhares de cursos online em vídeo, ebooks e áudiobooks.
Para testar seus conhecimentos no decorrer dos cursos online
Gerado diretamente na galeria de fotos do seu celular e enviado ao seu e-mail
Baixe nosso aplicativo pelo QR Code ou pelos links abaixo:.
Leve o conhecimento no seu bolso.
Baixe o aplicativo Cursa.
São centenas de Cursos gratuitos a disposição, com Certificado de conclusão gratuito que é salvo em sua galeria de imagens do celular.
Baixe o app para ter acesso ao Certificado de conclusão de Curso Gratuitamente.
+ de 10 milhões
de alunos
Certificado grátis e
válido em todo o Brasil
60 mil exercícios
gratuitos
4,8/5 classificação
nas lojas de apps
Cursos gratuitos em
vídeo, ebooks e audiobooks
