Cálculo da Complexidade
de Algoritmos Iterativos — Parte 2

Análise de Algoritmos • Aula 5

Pedro Ximenes

Universidade Católica de Pernambuco (UNICAP)

Semestre Letivo 2026.1

Seção 1

Revisão da Aula Anterior

Método dos 3 passos e tabela de padrões fundamentais.

Seção 2

Ordenação Quadrática

Selection Sort vs. Bubble Sort otimizado e somas triangulares.

Seção 3

Melhor, Pior e Caso Médio

Definições formais e o exemplo da Busca Linear.

Seção 4

Novos Padrões de Análise

Múltiplos parâmetros $O(n \cdot m)$ e primalidade em $O(\sqrt{n})$.

Seção 5

Técnicas Eficientes

A técnica dos Dois Ponteiros (Palíndromo e Two Sum em $O(n)$).

Seções 6-10

Resumo, Exercícios e Desafio

Tabela de reconhecimento, 10 exercícios com gabarito e mini-projeto.

📌 Método dos 3 passos

Identificar as operações primitivas: atribuições, comparações, acessos a arrays e operações aritméticas básicas executadas em tempo constante $O(1)$.
Contar quantas vezes cada operação acontece no pior caso: estruturar os limites de laços e condições de parada matematicamente.
Somar os custos e simplificar pela ordem de crescimento: descartar constantes multiplicativas e termos de menor ordem assintótica.

Padrão	Estrutura Típica	Classe Assintótica
Sem loop	Sequência simples de operações primitivas	$O(1)$
1 loop simples	Percorrer vetor de tamanho $n$ uma vez	$O(n)$
Loop com divisão por 2	Descartar metade do espaço a cada iteração	$O(\log n)$
Dois loops aninhados	Comparar todos os pares possíveis ($n \times n$)	$O(n^2)$
Três loops aninhados	Visitar todas as triplas ($n \times n \times n$)	$O(n^3)$
Loops sequenciais	Somar os custos e tomar o termo dominante	$O(\max(f(n), g(n)))$

💡 Ideia do algoritmo

A cada rodada, procuramos o menor elemento da parte ainda não ordenada do vetor. Depois disso, colocamos esse menor elemento na primeira posição disponível da porção desordenada.

🔍 Como o vetor evolui

O vetor vai sendo dividido em duas partes conceituais:
À esquerda: parte já organizada (prefixo ordenado definitivo).
À direita: parte ainda desorganizada (sufixo a ser varrido).
Em cada rodada, exatamente um novo elemento entra na parte organizada.

💻 Pseudocódigo comentado

algoritmo SelectionSort(V, n)
    para i de 0 ate n-2 faca
        // No início da rodada, assume que o menor está em i
        i_menor <- i
        para j de i+1 ate n-1 faca
            // Se aparecer valor menor, atualiza a posição do menor
            se V[j] < V[i_menor] entao
                i_menor <- j
            fim se
        fim para
        // Ao fim da rodada, coloca o menor valor na posição i
        troca(V[i], V[i_menor])
    fim para
fim algoritmo

📥 Entrada inicial

$$V = [7, 4, 5, 2]$$

Rodada 1: $i = 0$

Começamos assumindo que o menor está na posição $0$ ($i\_menor = 0$, valor $7$).
Comparamos com $4$ em $j=1$: $4 < 7 \implies i\_menor = 1$.
Comparamos com $5$ em $j=2$: $5 \not< 4 \implies i\_menor = 1$.
Comparamos com $2$ em $j=3$: $2 < 4 \implies i\_menor = 3$.
O menor encontrado ao final da rodada é $2$ na posição $3$.
Efetuamos a troca: $\text{troca}(V[0], V[3])$ (troca $7$ com $2$).

$$[7, 4, 5, 2] \longrightarrow [\mathbf{2}, 4, 5, 7]$$

Rodada 2: $i = 1$

Agora olhamos apenas para a parte não ordenada $[4, 5, 7]$. O menor já é $4$ na posição $1$. Nenhuma troca altera posições. $$[2, 4, 5, 7] \longrightarrow [2, \mathbf{4}, 5, 7]$$

Rodada 3: $i = 2$

Olhamos apenas para a parte $[5, 7]$. O menor já é $5$ na posição $2$. $$[2, 4, 5, 7] \longrightarrow [2, 4, \mathbf{5}, 7]$$

⚠️ Observação Crucial

Mesmo quando o vetor quase não muda ou já está ordenado, o algoritmo ainda realiza todas as comparações em busca do menor elemento.

📊 Quantas comparações acontecem?

Na primeira rodada ($i = 0$): comparamos com $n-1$ elementos.
Na segunda rodada ($i = 1$): comparamos com $n-2$ elementos.
Na terceira rodada ($i = 2$): comparamos com $n-3$ elementos.
...
Na última rodada ($i = n-2$): resta apenas $1$ comparação.

$$\sum_{i=1}^{n-1} i = (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} = \frac{n^2 - n}{2}$$

🏗️ Estrutura de custo

O custo dominante não vem das trocas (que ocorrem no máximo $n-1$ vezes). O custo dominante vem da busca repetida pelo menor elemento em cada rodada.

🎯 Resultado Assintótico

$$\boxed{\text{SelectionSort} \in \Theta(n^2)}$$

📝 Conclusão

O Selection Sort sempre faz essencialmente a mesma quantidade de comparações $\frac{n(n-1)}{2}$, independente da disposição inicial dos dados. Por isso, melhor caso, pior caso e caso médio pertencem todos à mesma classe $\Theta(n^2)$.

Rodada: 1/8 Comparações: 0 Trocas: 0

Clique em Iniciar para observar o algoritmo encontrando o menor valor a cada passada.

Já Ordenado Posição Atual ($i$) Menor Atual ($i\_menor$) Comparando ($j$)

💡 Ideia do algoritmo

Comparamos pares adjacentes $(V[j], V[j+1])$. Quando um par está fora de ordem, fazemos uma troca imediata. Ao final de cada passada, o maior elemento da porção não ordenada "flutua" para sua posição definitiva no final do vetor.

🌊 Efeito de cada passada

Depois da primeira passada: o maior valor já fica garantidamente no lugar certo.
Depois da segunda passada: o segundo maior também fica na posição correta.
A cada passada $i$, o laço interno precisa inspecionar apenas até $n-2-i$.

💻 Pseudocódigo comentado

algoritmo BubbleSortOtimizado(V, n)
    para i de 0 ate n-2 faca
        // A flag registra se houve troca nesta passada
        trocou <- falso
        para j de 0 ate n-2-i faca
            // Se o par estiver fora de ordem, corrige localmente
            se V[j] > V[j+1] entao
                troca(V[j], V[j+1])
                trocou <- verdadeiro
            fim se
        fim para
        // Se nada mudou, o vetor ja estava ordenado
        se trocou = falso entao
            retorne
        fim se
    fim para
fim algoritmo

📥 Entrada inicial

$$V = [5, 3, 4, 1]$$

Passada 1 ($i = 0$)

Compara $V[0]=5$ e $V[1]=3$: $5 > 3 \implies$ troca $\to [3, 5, 4, 1]$
Compara $V[1]=5$ e $V[2]=4$: $5 > 4 \implies$ troca $\to [3, 4, 5, 1]$
Compara $V[2]=5$ e $V[3]=1$: $5 > 1 \implies$ troca $\to [3, 4, 1, 5]$

$$[5, 3, 4, 1] \longrightarrow [3, 4, 1, \mathbf{5}]$$

📌 Leitura

Ao fim da primeira passada, o maior elemento ($5$) já está em sua posição definitiva no final do vetor.

Passada 2 ($i = 1$)

Compara $3$ e $4$: $3 \le 4 \implies$ não troca.
Compara $4$ e $1$: $4 > 1 \implies$ troca $\to [3, 1, 4, 5]$.

$$[3, 4, 1, 5] \longrightarrow [3, 1, \mathbf{4}, \mathbf{5}]$$

Passada 3 ($i = 2$)

Compara $3$ e $1$: $3 > 1 \implies$ troca $\to [1, 3, 4, 5]$.

$$[3, 1, 4, 5] \longrightarrow [\mathbf{1}, \mathbf{3}, \mathbf{4}, \mathbf{5}]$$

📌 Leitura

Após $3$ passadas, o vetor inteiro está perfeitamente ordenado.

⚠️ Pior Caso (Decrescente)

Quando o vetor começa em ordem inversa, toda comparação gera troca: $$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$$ $$\boxed{\text{Pior Caso} \in \Theta(n^2)}$$

✨ Melhor Caso (Já Ordenado)

Com a versão otimizada:

Faz $1$ passada de $n-1$ comparações.
Nenhuma troca ocorre ($\text{trocou} = \text{falso}$).
O laço encerra imediatamente!

$$\boxed{\text{Melhor Caso} \in \Theta(n)}$$

Algoritmo	Melhor Caso	Caso Médio	Pior Caso
Selection Sort	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$
Bubble Sort Otimizado	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$

💡 Comparação Importante

Dois algoritmos podem parecer estruturalmente semelhantes porque ambos utilizam dois laços aninhados, mas detalhes de controle de fluxo interno (como flags de parada antecipada) mudam drasticamente a classe do melhor caso.

Passada: 1/7 Comparações: 0 Trocas: 0

Clique em Iniciar ou selecione "Testar Melhor Caso" para ver a parada em 1 passada.

📚 Definições Formais

Melhor caso: a entrada de tamanho $n$ mais favorável possível, que minimiza a quantidade de operações executadas.
Pior caso: a entrada de tamanho $n$ mais custosa possível, que maximiza o tempo de execução e estabelece um teto de custo seguro.
Caso médio: o comportamento esperado considerando uma distribuição estatística de probabilidade sobre as entradas possíveis.

🎯 Foco Central da Análise

O foco principal da análise assintótica continua sendo o pior caso, porque ele fornece uma garantia matemática inequívoca sobre o limite superior de desempenho do sistema sob qualquer circunstância.

🔍 Problema

Procurar o valor $x = 8$ em um vetor de $n$ posições.

Entrada Favorável (Melhor Caso)

$$V = [\mathbf{8}, 4, 3, 1]$$

O algoritmo inspeciona a primeira posição ($i = 0$).
Já encontra o valor procurado ($V[0] == 8$).
Retorna imediatamente após $1$ única comparação.

$$\boxed{\text{Melhor Caso da Busca Linear} \in \Theta(1)}$$

Entrada 2: Alvo no Final

$$V = [4, 3, 1, \mathbf{8}]$$ O algoritmo realiza $n$ comparações até atingir a última posição.

Entrada 3: Alvo Ausente

$$V = [4, 3, 1, 2], \quad x = 8$$ O algoritmo percorre todas as $n$ posições sem encontrar o elemento.

$$\boxed{\text{Pior Caso da Busca Linear} \in \Theta(n)}$$

📊 Caso Médio

Assumindo probabilidade uniforme de encontrar o elemento em qualquer posição, a média é $\approx \frac{n+1}{2} = \Theta(n)$.

Selecione um caso acima para iniciar a demonstração.

📌 Situação

Nem sempre uma entrada é descrita apenas por um único parâmetro $n$. Uma matriz bidimensional, por exemplo, possui $n$ linhas e $m$ colunas.

❓ A Pergunta Certa

Se o algoritmo percorre uma matriz completa, o custo total depende simultaneamente de quantas linhas existem ($n$) e de quantas colunas existem ($m$). Não podemos assumir $n=m$ sem especificação prévia!

💻 Pseudocódigo comentado

algoritmo BuscaMatriz(M, n, m, x)
    // Percorre as n linhas da matriz
    para i de 0 ate n-1 faca
        // Percorre as m colunas da linha atual
        para j de 0 ate m-1 faca
            // Testa se o valor procurado foi encontrado
            se M[i][j] = x entao
                retorne verdadeiro
            fim se
        fim para
    fim para
    retorne falso
fim algoritmo

📥 Entrada

$$M = \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \end{bmatrix}, \quad x = 9$$

Análise das iterações

A matriz tem $n = 2$ linhas.
Cada linha tem $m = 3$ colunas.
Como $x = 9$ não pertence à matriz, o algoritmo visita todas as posições:

$$2 \cdot 3 = 6 \text{ células inspecionadas}$$

📊 Leitura da Estrutura

Loop externo: executa $n$ vezes (uma para cada linha).
Loop interno: executa $m$ vezes para cada uma das $n$ linhas.
Total de iterações do corpo: $\sum_{i=0}^{n-1} m = n \cdot m$.

$$\boxed{f(n, m) \in O(n \cdot m)}$$

💡 Observação importante

Se a matriz for quadrada ($n = m$), recuperamos a conhecida classe quadrática $O(n^2)$.

Dimensão: 3 × 4 | Células Visitadas: 0 / 12

Clique em "Escanear Matriz" para acompanhar a visita $O(n \cdot m)$.

💻 Pseudocódigo comentado

algoritmo EhPrimo(n)
    // Elimina os casos menores que 2
    se n < 2 entao
        retorne falso
    fim se
    i <- 2
    enquanto i * i <= n faca
        // Se achou um divisor exato, n nao e primo
        se n mod i = 0 entao
            retorne falso
        fim se
        // Passa ao proximo candidato a divisor
        i <- i + 1
    fim enquanto
    retorne verdadeiro
fim algoritmo

📐 Por que só verificar divisores até $\sqrt{n}$?

Se $n$ é um número composto, então existem inteiros $a, b > 1$ tais que $n = a \times b$. Sem perda de generalidade, assuma $a \le b$. $$a \le \sqrt{n} \le b$$ (Se ambos fossem estritamente maiores que $\sqrt{n}$, teríamos $a \times b > \sqrt{n} \times \sqrt{n} = n$, uma contradição evidente!)
Logo, todo número composto possui pelo menos um divisor não trivial menor ou igual a $\sqrt{n}$.

$$\text{Condição } i^2 \le n \iff i \le \sqrt{n} \implies \boxed{f(n) \in O(\sqrt{n})}$$

⚡ Impacto Prático de Eficiência

Para $n = 1.000.000$: a busca ingênua faria $1.000.000$ iterações. Com a condição $i^2 \le n$, o laço executa apenas $\approx 1.000$ iterações!

Exemplos Numéricos

$n = 29$ (primo): testamos apenas $i \in \{2, 3, 4, 5\}$ ($\sqrt{29} \approx 5{,}38$).
$n = 30$ (composto): pára imediatamente em $i = 2$.

🚨 Sinal de Alerta

Sempre que o laço incrementar linearmente ($i \leftarrow i + 1$), mas sua condição de parada for $i^2 \le n$ (ou $i \times i \le n$), suspeite imediatamente de $O(\sqrt{n})$.

Testar valor de $n$:

💡 O que é a Técnica?

Uma técnica algorítmica elegante que utiliza dois índices (ponteiros) que se movem pelo vetor de forma estritamente coordenada, transformando problemas que ingenuamente exigiriam dois loops aninhados $O(n^2)$ em soluções lineares $O(n)$.

🔄 Variações Mais Comuns

Ponteiros convergentes (início e fim): um começa no índice $0$ e outro em $n-1$, movendo-se um em direção ao outro (ex.: palíndromo, Two Sum).
Ponteiros direcionais (lento e rápido / janela deslizante): ambos avançam na mesma direção em velocidades ou critérios distintos.

💻 Pseudocódigo comentado

algoritmo EhPalindromo(S, n)
    esq <- 0
    dir <- n - 1
    enquanto esq < dir faca
        // Se os extremos diferem, a palavra nao e palindromo
        se S[esq] != S[dir] entao
            retorne falso
        fim se
        // Aproxima os ponteiros do centro
        esq <- esq + 1
        dir <- dir - 1
    fim enquanto
    retorne verdadeiro
fim algoritmo

$$\text{Total de comparações} \le \lfloor n/2 \rfloor \implies \boxed{f(n) \in O(n)}$$

🎯 Problema

Dado um vetor já ordenado $V$, determinar se existem dois índices distintos $i, j$ tais que $V[i] + V[j] = k$.

💻 Pseudocódigo comentado

algoritmo TwoSum(V, n, k)
    esq <- 0,  dir <- n - 1
    enquanto esq < dir faca
        soma <- V[esq] + V[dir]
        se soma = k entao  retorne verdadeiro
        senao se soma < k entao  esq <- esq + 1
        senao  dir <- dir - 1
    fim enquanto
    retorne falso
fim algoritmo

📌 Leitura da Complexidade

A cada iteração do laço, ou esq avança para a direita ou dir recua para a esquerda. Como a distância total inicial é $n-1$, o laço executa no máximo $n-1$ passos. $$\boxed{f(n) \in O(n)}$$

Padrão	Como Reconhecer no Código	Classe Assintótica
Selection Sort	Busca repetida de menor: soma triangular constante	$\Theta(n^2)$
Bubble Sort (Pior Caso)	Trocas consecutivas em vetor inverso	$\Theta(n^2)$
Bubble Sort (Melhor Caso)	Flag `trocou` encerra na 1ª passada	$\Theta(n)$
Dois Parâmetros	Laços aninhados de dimensões independentes	$O(n \cdot m)$
Raiz Quadrada	Condição de parada do laço com $i^2 \le n$	$O(\sqrt{n})$
Dois Ponteiros	Dois índices convergindo em passos unitários	$O(n)$

🎯 Fechamento

Os padrões apresentados nesta sessão cobrem os casos mais frequentes de algoritmos iterativos e constituem os blocos construtores para a análise de algoritmos avançados.

Tamanho $n$:

Classe	Custo ($n = 16$)

📝 Estratégia de Resolução Recomendada

Identificar o padrão dominante de repetição: laço com divisão por $2$, laço com saltos de tamanho $i$, somatório triangular ou produto cartesiano.
Contar o custo de cada laço e montar a soma matemática: escrever explicitamente $\sum (\dots)$ sem omitir limites inferiores e superiores.
Simplificar pela ordem de crescimento: classificar na notação adequada ($\Theta$, $O$ ou $\Omega$) e confrontar com o gabarito.

algoritmo Exercicio1(n)
    i <- n
    enquanto i >= 1 faca
        para j de 1 ate n faca
            // Operação O(1)
        fim para
        i <- i / 2
    fim enquanto
fim algoritmo

Resolução: O laço enquanto divide $i$ sucessivamente por $2$, executando $\lfloor\log_2 n\rfloor + 1$ vezes. Em cada rodada, o para executa $n$ operações. Custo total: $n \times \Theta(\log n) = \boxed{\Theta(n \log n)}$.

algoritmo Exercicio2(n)
    para i de 1 ate n faca
        j <- 1
        enquanto j < i faca
            j <- j * 2
        fim enquanto
    fim para
fim algoritmo

Resolução: Para cada $i$, o laço enquanto dobra $j$, custando $\Theta(\log i)$ iterações. A soma total é $\sum_{i=1}^n \log i = \log(n!) = \boxed{\Theta(n \log n)}$ (pela fórmula de Stirling).

algoritmo Exercicio3(n, m)
    para i de 0 ate n-1 faca
        para j de 0 ate m-1 faca
            para k de 0 ate n-1 faca
                // Operação O(1)
            fim para
        fim para
    fim para
fim algoritmo

Resolução: Três laços aninhados independentes: $n \times m \times n = \boxed{O(n^2 \cdot m)}$.

algoritmo Exercicio4(V, n)
    para i de 0 ate n-1 faca
        para j de 0 ate n-1-i faca
            se V[j] > V[j+1] entao
                troca(V[j], V[j+1])
            fim se
        fim para
    fim para
fim algoritmo

Resolução: Trata-se da estrutura do Bubble Sort clássico sem flag. O laço interno executa $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} = \boxed{\Theta(n^2)}$.

algoritmo Exercicio5(V, n)
    para i de 0 ate n-1 faca
        j <- i
        enquanto j > 0 e V[j] < V[j-1] faca
            troca(V[j], V[j-1])
            j <- j - 1
        fim enquanto
    fim para
fim algoritmo

Resolução: Padrão do Insertion Sort. No pior caso (vetor em ordem decrescente), o enquanto recua $i$ posições para cada $i$, gerando $\sum_{i=1}^{n-1} i = \boxed{\text{Pior Caso } \Theta(n^2)}$.

algoritmo Exercicio6(n)
    s <- 0
    para i de 1 ate n faca
        para j de 1 ate i*i faca
            s <- s + 1
        fim para
    fim para
    retorne s
fim algoritmo

Resolução: Para cada $i$, o laço interno executa $i^2$ vezes. Custo total: $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3 + 3n^2 + n}{6} = \boxed{\Theta(n^3)}$.

algoritmo Proposto1(n)
    para i de n ate 1 (decrementando) faca
        para j de i ate n faca
            // Operação O(1)
        fim para
    fim para
fim algoritmo

Resolução: Quando $i = n \implies 1$ vez; $i = n-1 \implies 2$ vezes; ... até $i = 1 \implies n$ vezes. Soma: $1 + 2 + \dots + n = \frac{n(n+1)}{2} = \boxed{\Theta(n^2)}$.

algoritmo Proposto2(n)
    i <- 1
    enquanto i*i*i <= n faca
        i <- i + 1
    fim enquanto
fim algoritmo

Resolução: O laço executa enquanto $i^3 \le n \iff i \le \sqrt[3]{n}$. Como $i$ cresce de $1$ em $1$, o número de iterações é $\approx n^{1/3} \implies \boxed{\Theta(n^{1/3})}$.

algoritmo Proposto3(n)
    para i de 1 ate n faca
        j <- n
        enquanto j > i faca
            j <- j - i
        fim enquanto
    fim para
fim algoritmo

Resolução: O enquanto diminui $j$ em passos de tamanho $i$, executando $\approx \frac{n-i}{i} \approx \frac{n}{i} - 1$ vezes. Somando para todos os $i$: $\sum_{i=1}^n \frac{n}{i} = n \sum_{i=1}^n \frac{1}{i} = n H_n \approx n(\ln n + \gamma) = \boxed{\Theta(n \log n)}$.

algoritmo Proposto4(n)
    para i de 1 ate n faca
        para j de 1 ate n (passo i) faca
            // Operação O(1)
        fim para
    fim para
fim algoritmo

Resolução: O laço interno visita $\lceil n/i \rceil$ posições a cada valor de $i$. A soma total resulta na série harmônica: $\sum_{i=1}^n \frac{n}{i} = n H_n = \boxed{\Theta(n \log n)}$.

Gabarito 1: Laço com divisão sucessiva

O laço enquanto divide $i$ por $2$ a cada rodada: $\Theta(\log n)$ iterações.
O loop interno para executa sempre $n$ vezes a cada rodada do while.

$$\boxed{\Theta(n \log n)}$$

Gabarito 2: Laço com multiplicação por 2

Para cada $i$, o enquanto dobra $j$ até atingir $i$, com custo $\Theta(\log i)$.
Somando para todos os valores: $\sum_{i=1}^n \log i = \log(n!) = \Theta(n \log n)$.

$$\boxed{\Theta(n \log n)}$$

Gabarito 3: Três loops multivariáveis

Primeiro loop: $n$ vezes.
Segundo loop: $m$ vezes.
Terceiro loop: $n$ vezes.

$$\boxed{O(n^2 \cdot m)}$$

Gabarito 4: Padrão do Bubble Sort

O loop interno executa $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$.

$$\boxed{\Theta(n^2)}$$

Gabarito 5: Insertion Sort Pior Caso

No pior caso, o enquanto recua $i$ posições a cada $i$, gerando $1 + 2 + \dots + (n-1)$.

$$\boxed{\text{Pior Caso } \Theta(n^2)}$$

Gabarito 6: Soma dos Quadrados

Para cada $i$, o laço executa $i^2$ vezes. Soma total: $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.

$$\boxed{\Theta(n^3)}$$

Gabarito 7: Loop com limite inferior dinâmico

O loop interno executa $n - i + 1$ vezes, produzindo outra soma triangular clássica.

$$\boxed{\Theta(n^2)}$$

Gabarito 8: Raiz Cúbica

O laço pára quando $i^3 > n \iff i > \sqrt[3]{n}$.

$$\boxed{\Theta(n^{1/3})}$$

Gabarito 9: Saltos de tamanho $i$

O custo por valor de $i$ é $\approx n/i$. A soma total resulta em $n \sum \frac{1}{i} = n H_n$.

$$\boxed{\Theta(n \log n)}$$

Gabarito 10: Laço com passo $i$

O laço visita $n/i$ posições. Somando para todos os $i \in [1, n]$, obtemos $\Theta(n \log n)$.

$$\boxed{\Theta(n \log n)}$$

🎯 Objetivo

Implementar, instrumentar e analisar três soluções distintas para o problema de verificar se um array contém dois elementos cuja soma é igual a um valor $k$:

Força Bruta ($O(n^2)$): testar todos os pares possíveis com dois loops aninhados.
Ordenação + Dois Ponteiros ($O(n \log n)$ ou $O(n)$): ordenar o vetor e convergir os ponteiros.
Tabela Hash ($O(n)$ tempo / $O(n)$ memória): busca de complementos $k - V[i]$ em tempo constante médio.

📦 O que entregar

Código-fonte completo (Python, C, Java, Rust ou JavaScript).
Relatório analítico comparando a dedução teórica passo a passo com medições empíricas de tempo para $n \in [10^2, 10^5]$ e gráfico comparativo.

📋 Checklist de Avaliação

Corretude: implementar e testar com rigor as $3$ abordagens com casos de teste representativos.
Análise Teórica: deduzir a complexidade de tempo e memória de cada solução passo a passo.
Validação Experimental: confrontar a curva teórica com os tempos reais cronometrados.
Discussão de Trade-offs: explicar o compromisso entre tempo de execução e consumo de memória auxiliar.

🚀 Aula 6 — Algoritmos Recursivos e Relações de Recorrência

Como expressar custos de algoritmos de Divisão e Conquista: Relações de Recorrência.
Método da Substituição: prova indutiva de limites assintóticos.
Método da Árvore de Recursão: visualização do trabalho por nível e número de folhas.
Teorema Mestre: fórmula geral para resolver recorrências da forma $T(n) = aT(n/b) + f(n)$.

Dúvidas?

📚 Bibliografia Recomendada

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
Algoritmos: Teoria e Prática. 3ª edição, Elsevier / Campus, 2012. Capítulos 2 e 3.
J. A. B. Monteiro.
Notas de Aula — Estruturas de Dados e Algoritmos.
Disponível em: joaoarthurbm.github.io/eda

Cálculo da Complexidadede Algoritmos Iterativos — Parte 2

Roteiro da Aula

Revisão essencial da Aula 4

Padrões já conhecidos

Selection Sort: intuição

Selection Sort: pseudocódigo

Selection Sort: exemplo de entrada

Selection Sort: continuando o exemplo

Selection Sort: contando as comparações

Selection Sort: conclusão

Simulador Interativo: Selection Sort

Bubble Sort: intuição

Bubble Sort otimizado: pseudocódigo

Bubble Sort: exemplo de entrada

Bubble Sort: continuando o exemplo

Bubble Sort: análise de casos

Selection Sort $\times$ Bubble Sort

Simulador Interativo: Bubble Sort

Por que falamos em casos diferentes?

Exemplo simples: busca linear

Busca linear: pior caso e caso médio

Simulador Interativo: Busca Linear

Quando a entrada tem dois tamanhos

Exemplo simples: busca em matriz

Busca em matriz: exemplo de entrada

Busca em matriz: conclusão

Simulador Interativo: Busca em Matriz $n \times m$

Exemplo simples: teste de primalidade

Análise — Verificação de Primalidade

De onde aparece o padrão $O(\sqrt{n})$?

Técnica dos Dois Ponteiros

Exemplo 1: verificação de palíndromo

Palíndromo: exemplo e simulação

Exemplo 2: Two Sum em vetor ordenado

Two Sum: rastreamento e simulação

Resumo operacional da aula

Comparativo Gráfico de Complexidade

Exercícios: orientações

Exercício 1

Exercício 2

Exercício 3

Exercício 4

Exercício 5

Exercício 6

Exercício 7

Exercício 8

Exercício 9

Exercício 10

Gabarito: Exercícios 1 e 2

Gabarito: Exercícios 3 e 4

Gabarito: Exercícios 5 e 6

Gabarito: Exercícios 7 e 8

Gabarito: Exercícios 9 e 10

Desafio: Mini-Projeto de Análise

Critérios de Avaliação do Desafio

Próxima Aula

Dúvidas?

Referências Bibliográficas

Cálculo da Complexidade
de Algoritmos Iterativos — Parte 2