0Pricing
DSA Interview Prep · Aula

Analisando Laços e Laços Aninhados

Calcule a complexidade temporal de laços simples, laços aninhados e laços com intervalos decrescentes, como na busca binária ou em iterações triangulares.

Analisando Laços e Laços Aninhados é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

Um único laço: O(n)

O laço mais simples executa seu corpo n vezes, portanto é O(n). Um passo maior altera a quantidade de execuções, mas não a classe. Comece sempre contando quantas vezes o corpo é executado. Consulte o código.

# O(n): body runs n times
def count_ops_linear(n):
    ops = 0
    for i in range(n):
        ops += 1     # constant work
    return ops

print(count_ops_linear(100))  # 100

# Still O(n): step=2 halves count but same class
def count_ops_half(n):
    ops = 0
    for i in range(0, n, 2):
        ops += 1
    return ops

print(count_ops_half(100))    # 50  => O(n)

Laços aninhados: O(n²) e além

Dois laços aninhados, cada um executado n vezes, resultam em n x n = O(n^2); três resultam em O(n^3). Porém, se o laço interno for executado um número fixo de vezes, tudo continua linear.

def count_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(n):      # n iterations each
            ops += 1
    return ops

print(count_pairs(10))   # 100 = 10^2
print(count_pairs(100))  # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)

Laço triangular: O(n²/2) = O(n²)

Quando o laço interno começa em i+1, as iterações formam um triângulo: n(n-1)/2, que continua sendo O(n^2) depois que a metade é eliminada. Problemas que envolvem todos os pares únicos têm esse formato.

def count_unique_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(i+1, n): # n-1, n-2, ..., 0
            ops += 1
    return ops

print(count_unique_pairs(10))  # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped

Laço com intervalo decrescente: O(log n)

Quando a variável do laço é dividida pela metade a cada etapa, você obtém O(log n). A pergunta principal é: o intervalo diminui multiplicativamente (log n) ou aditivamente (n)? Consulte o código.

def count_log_ops(n):
    ops = 0
    i = n
    while i >= 1:
        ops += 1
        i //= 2   # halve each iteration
    return ops

import math
for n in [8, 16, 64, 1024]:
    ops = count_log_ops(n)
    print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely

Laço aninhado com interno decrescente: O(n log n)

Um laço externo executado n vezes com um laço interno O(log n) resulta em O(n log n) — o formato da ordenação por intercalação. Identificar uma etapa O(log n) interna é essencial para analisar algoritmos de ordenação.

import math

def count_n_log_n(n):
    ops = 0
    for i in range(n):    # n iterations
        j = n
        while j >= 1:     # log n iterations
            ops += 1
            j //= 2
    return ops

for n in [8, 32, 128]:
    ops = count_n_log_n(n)
    predicted = int(n * math.log2(n))
    print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')

Laços internos dependentes

Quando o intervalo do laço interno depende do índice externo, conte o número total de iterações, não o número por etapa. Um laço interno que percorre 0..i soma n(n-1)/2 = O(n^2). Consulte o código.

# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
    ops = 0
    for i in range(n):
        for j in range(i):   # runs 0,1,2,...,n-1 times
            ops += 1
    return ops

print(sum_inner_i(10))  # 45 = 10*9/2  => O(n^2)

# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
    ops = 0
    i = 1
    while i <= n:
        for j in range(n // i):
            ops += 1
        i *= 2
    return ops
print(sum_inner_n_over_i(64))  # ~ 64*6 = 384

Análise da ordenação por bolhas passo a passo

A ordenação por bolhas faz n(n-1)/2 comparações, portanto é O(n^2). Mesmo com uma saída antecipada, uma entrada ordenada ao contrário ainda exige todas as comparações. É lenta demais para entradas grandes.

def bubble_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:  # early exit if sorted
            break
    return comparisons

arr = list(range(10, 0, -1))  # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}')  # 45 = 10*9/2

Laços sobre strings e substrings

Atenção: o fatiamento do Python é O(k), não gratuito, e concatenar strings com + em um laço é O(n^2), porque uma cópia é feita a cada vez. Use ''.join(parts) no lugar. Consulte o código.

# O(n^2): string concat in loop
def build_bad(n):
    s = ''
    for i in range(n):
        s += str(i)  # copies s each time!
    return s

# O(n): join is a single pass
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))
    return ''.join(parts)

print(build_good(10))  # '0123456789'

Múltiplos parâmetros de entrada

Com duas entradas, a complexidade pode usar ambas: O(m + n) para trabalho separado e O(m x n) para trabalho aninhado. Em grafos, é comum escrever O(V + E). Dê nomes claros a cada variável.

# O(m + n): two independent loops
def independent(m, n):
    a = sum(range(m))  # O(m)
    b = sum(range(n))  # O(n)
    return a + b       # total O(m + n)

# O(m * n): nested
def nested(m, n):
    count = 0
    for i in range(m):     # O(m)
        for j in range(n): # O(n) each
            count += 1
    return count  # O(m * n)

print(independent(5, 10))  # 10 + 45 = 55
print(nested(5, 10))       # 50

Laços aninhados versus chamadas sequenciais

Uma chamada de função não é gratuita — o laço dentro dela também conta. Chame um auxiliar O(n) n vezes e você terá O(n^2). Ao analisar, sempre examine o interior das chamadas de caixa-preta.

# Naive string matching: O(n*m)
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):  # O(n)
        if text[i:i+m] == pattern:  # O(m) comparison + O(m) slice
            matches.append(i)
    return matches
# Total: O(n*m)

print(naive_search('abcabcabc', 'abc'))  # [0, 3, 6]

Prática: identifique a complexidade de relance

Crie o hábito: conte o aninhamento dos laços, verifique se o laço interno depende do externo e fique atento aos custos ocultos em chamadas de função e fatiamentos. O código é um desafio para você experimentar.

# What is the complexity of this function?
def mystery(nums):
    result = []
    for i in range(len(nums)):          # O(n)
        for j in range(i, len(nums)):   # O(n) worst
            if sum(nums[i:j+1]) == 0:   # O(n) slice + sum!
                result.append((i, j))
    return result
# Answer: O(n^3)  -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)

Verificação rápida

Verificação rápida — veja como você assimilou as técnicas de análise de laços. Confie no seu raciocínio. 💪

Recapitulação da lição

Recapitulação: laços aninhados são multiplicados e laços independentes são somados; um laço interno que reduz pela metade resulta em O(n log n), e os custos ocultos dentro de chamadas e fatiamentos também devem ser contabilizados.

Perguntas Frequentes

A aula “Analisando Laços e Laços Aninhados” é grátis?

Sim — o texto completo de “Analisando Laços e Laços Aninhados” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Analisando Laços e Laços Aninhados”?

Calcule a complexidade temporal de laços simples, laços aninhados e laços com intervalos decrescentes, como na busca binária ou em iterações triangulares. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Analisando Laços e Laços Aninhados”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Notação Big-O do Zero
  2. Analisando Laços e Laços Aninhados
  3. Recursão e o Método da Árvore de Recorrência
  4. Complexidade de Espaço e Compromissos
← Voltar para DSA Interview Prep