Projeto e Análise de Algoritmos I

Aula 04 - Análise de Algoritmos e Notação Assintótica

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica

Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Medindo o Custo de Algoritmos

Como Medir o Custo de um Algoritmo?

Quando analisamos algoritmos, precisamos de uma métrica de custo.

Mas o que exatamente devemos medir?

Possíveis Medidas:

Tempo de execução (ms, segundos, minutos, dias, anos)
Espaço utilizado na memória (bits, KB, MB, GB, TB)
Consumo de energia (kWh)
Custos financeiros ($, R$, £, ¥)
Outros recursos (rede, hardware especializado, etc.)

P: Qual dessas medidas é a mais relevante para analisar algoritmos?

Modelo de Computação

Modelo RAM (Random Access Machine):

Vamos assumir um computador genérico, que executa operações em sequência, sem paralelismo.
E se o processador tem uma instrução para ordenação? Ordenação O(1)? Não realístico.
Exponenciação é operação de tempo constante?
- Pode ser implementado com shift-right/shift-left.
- Vamos assumir que 2^k tem tempo constante para k pequeno.
Não vamos considerar hierarquia de memória.

Modelo RAM (Random Access Machine)

Obs. Em geral é desnecessário definir o custo de cada instrução, assumimos um custo constante para qualquer instrução.

Def. Toda operação simples leva tempo constante:

Adição, subtração, multiplicação, divisão, \dots

Movimentos de dados (acesso e escrita na memória).

Controle condicional.

Obs. Operações complexas não levam tempo constante:

Loops.

Chamadas a sub-rotinas como ordenação.

Análise de Algoritmos

P: Como analisar o tempo de execução de um algoritmo?

Obs. O tempo requerido por um algoritmo depende da entrada:

Ordenar 100.000 números leva mais tempo que ordenar 3 números.

Precisamos levar o tamanho da entrada em consideração.

Análise de Algoritmos: Tamanho da Entrada

Tamanho da Entrada:

Depende do problema a ser estudado.

Geralmente o número de itens na entrada (números).

Multiplicar dois números inteiros: número de bits.

Pode ser descrito por mais de um número: grafos (V e E).

P: Qual o tamanho da entrada de um Cubo Mágico?

Análise de Algoritmos: Tempo de Execução

Def. (Tempo de Execução): Para uma entrada específica, é o número de instruções primitivas (steps) executadas.

Instruções independentes de máquina:

Cada linha i custa tempo constante \textcolor{red}{c_i}.
Uma linha que custa \textcolor{red}{c_i} e é executada n vezes vai contribuir \textcolor{red}{c_i} \cdot n.

T(n) = número de instruções executadas para entrada de tamanho n.

Laços (Loops)

O teste do laço é executado uma vez a mais que o conteúdo do bloco:

\begin{algorithmic} \Procedure{Zera-Vetor}{$A, n$} \For{$j \gets 1$ \To $n$} \Comment{Executa $n + 1$ vezes} \State $A[j] \gets 0$ \Comment{Executa $n$ vezes} \EndFor \EndProcedure \end{algorithmic}

\begin{algorithmic} \Procedure{Exemplo-While}{$j$} \While{$j > 0$} \Comment{Executa $X + 1$ vezes} \State $j \gets \dots$ \Comment{Executa $X$ vezes} \EndWhile \EndProcedure \end{algorithmic}

Análise do Insertion Sort

Ordenação por Inserção (Insertion Sort)

\begin{algorithmic} \Procedure{InsertionSort}{$A$} \For{$j \gets 2$ \To $\text{length}(A)$} \State $key \gets A[j]$ \State \Comment{Insere $A[j]$ em $A[1 \dots j-1]$} \State $i \gets j-1$ \While{$i > 0$ \And $A[i] > key$} \State $A[i+1] \gets A[i]$ \State $i \gets i-1$ \EndWhile \State $A[i+1] \gets key$ \EndFor \EndProcedure \end{algorithmic}

Linha	Custo	Repetições
1.	\textcolor{red}{c_1}	n
2.	\textcolor{red}{c_2}	n-1
3.	0	n-1
4.	\textcolor{red}{c_4}	n-1
5.	\textcolor{red}{c_5}	\sum_{j=2}^n t_j
6.	\textcolor{red}{c_6}	\sum_{j=2}^n (t_j - 1)
7.	\textcolor{red}{c_7}	\sum_{j=2}^n (t_j - 1)
8.	\textcolor{red}{c_8}	n-1

t_j: nº de repetições do laço da linha 5 para aquele valor de j.

Ordenação por Inserção (Insertion Sort)

Somando todos os custos:

T(n) = \textcolor{red}{c_1} n + \textcolor{red}{c_2}(n-1) + 0(n-1) + \textcolor{red}{c_4}(n-1) + \textcolor{red}{c_5} \sum_{j=2}^n t_j + \\ \textcolor{red}{c_6} \sum_{j=2}^n (t_j - 1) + \textcolor{red}{c_7} \sum_{j=2}^n (t_j - 1) + \textcolor{red}{c_8}(n-1)

Problema: Como nos livramos de t_j? O valor de t_j para cada j depende da sequência de entrada, que não temos como saber a priori.

Solução: Podemos analisar o melhor e o pior caso! Isto é, podemos inferir limites inferiores e limites superiores para t_j.

Ordenação por Inserção (Insertion Sort)

Melhor Caso: t_j = 1
A[i] \le key
Sequência já ordenada!

\begin{align*} T(n) &= \textcolor{red}{c_1} n + \textcolor{red}{c_2}(n-1) + 0(n-1) + \textcolor{red}{c_4}(n-1) + \textcolor{red}{c_5} \sum_{j=2}^n t_j + \\ &\quad \textcolor{red}{c_6} \sum_{j=2}^n (t_j - 1) + \textcolor{red}{c_7} \sum_{j=2}^n (t_j - 1) + \textcolor{red}{c_8}(n-1) \end{align*}

Ordenação por Inserção (Insertion Sort)

Melhor Caso: t_j = 1
Sequência já ordenada! A[i] \le key

\begin{align*} T(n) &= \textcolor{red}{c_1} n + \textcolor{red}{c_2}(n-1) + 0(n-1) + \textcolor{red}{c_4}(n-1) + \textcolor{red}{c_5} \sum_{j=2}^n 1 + \\ &\textcolor{red}{c_6} \sum_{j=2}^n (1 - 1) + \textcolor{red}{c_7} \sum_{j=2}^n (1 - 1) + \textcolor{red}{c_8}(n-1)\\ &= \textcolor{red}{c_1} n + \textcolor{red}{c_2}(n-1) + \textcolor{red}{c_4}(n-1) + \textcolor{red}{c_5}(n-1) + \textcolor{red}{c_8}(n-1) \\ &= (\textcolor{red}{c_1} + \textcolor{red}{c_2} + \textcolor{red}{c_4} + \textcolor{red}{c_5} + \textcolor{red}{c_8})n - (\textcolor{red}{c_2} + \textcolor{red}{c_4} + \textcolor{red}{c_5} + \textcolor{red}{c_8}) \\ &= \textcolor{#7c3aed}{a} \cdot n + \textcolor{#7c3aed}{b} \end{align*}

Lembrando que \sum_{j=2}^{n} 1 = n - 1.

Melhor Caso: Função linear em n.

Ordenação por Inserção (Insertion Sort)

Pior Caso: t_j = j
A[i] > key sempre
Sequência ordenada em ordem reversa!

\sum_{j=2}^n j = \frac{n(n+1)}{2} - 1 \quad \text{e} \quad \sum_{j=2}^n (j-1) = \frac{n(n-1)}{2}

\begin{align*} T(n) &= \textcolor{red}{c_1} n + \textcolor{red}{c_2} (n-1) + \textcolor{red}{c_4} (n-1) + \textcolor{red}{c_5} \left(\frac{n(n+1)}{2}-1\right) + \\ &=\textcolor{red}{c_6} \left(\frac{n(n-1)}{2}\right) + \textcolor{red}{c_7} \left(\frac{n(n-1)}{2}\right) + \textcolor{red}{c_8} (n-1) \\ &= \left( \frac{\textcolor{red}{c_5}}{2} + \frac{\textcolor{red}{c_6}}{2} + \frac{\textcolor{red}{c_7}}{2} \right) n^2 + \left( \textcolor{red}{c_1} + \textcolor{red}{c_2} + \textcolor{red}{c_4} + \frac{\textcolor{red}{c_5}}{2} - \frac{\textcolor{red}{c_6}}{2} - \frac{\textcolor{red}{c_7}}{2} + \textcolor{red}{c_8} \right) n - (\textcolor{red}{c_2} + \textcolor{red}{c_4} + \textcolor{red}{c_5} + \textcolor{red}{c_8})\\ &= \textcolor{#7c3aed}{a} n^2 + \textcolor{#7c3aed}{b} n + \textcolor{#7c3aed}{c} \end{align*}

Ordenação por Inserção (Insertion Sort)

Pior Caso: t_j = j

Pior Caso: Função quadrática em n.

\textcolor{#7c3aed}{a}, \textcolor{#7c3aed}{b} e \textcolor{#7c3aed}{c} dependem do custo das instruções (\textcolor{red}{c_i}).
T(n) = n^2?
Não é igual, mas cresce como n^2.
T(n) \sim n^2 (ordem de crescimento).

Análise de Algoritmos

P: Por que o pior caso?

Obs. Nós em geral nos preocupamos em encontrar o tempo de execução do pior caso:

O maior tempo de execução para qualquer entrada de tamanho n.

O pior caso dá uma garantia para qualquer entrada.

Para alguns algoritmos o pior caso ocorre com frequência:

Exemplo: busca de um item não presente em um vetor.

P: Alternativas ao pior caso?

Análise de Algoritmos

P: Qual é o caso médio do algoritmo de Ordenação por Inserção?

Obs. Para ordenar um vetor ordenado randomicamente com elementos distintos:

Em média A[j] é menor que metade dos elementos em A[1 \dots j-1].

Assim, o algoritmo deve comparar o elemento com metade dos elementos até encontrar a posição de key.

Obs. Então t_j = \frac{j}{2}, isso é aproximadamente metade do pior caso, mas ainda é uma função quadrática.

P: Quais instâncias aparecem no mundo real?

Busca em Vetor Não Ordenado

No nosso caso, abstraímos com unidades constantes de computação.

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

Passos unitários contados:

leitura de A[i]
comparação A[i]{=}x
incremento de i
return

Obs. Nessa disciplina, também iremos considerar unidades constantes de armazenamento para analisar a complexidade de espaço.

Busca em Vetor Não Ordenado

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

Exemplo: Procurar x=23 em A[1..10]

Índice	1	2	3	4	5	6	7	8	9	10
Valor	42	7	85	13	66	90	23	5	77	31

Busca em Vetor Não Ordenado

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

Exemplo: Procurar x=42 em A[1..10]

Índice	1	2	3	4	5	6	7	8	9	10
Valor	42	7	85	13	66	90	23	5	77	31

Busca em Vetor Não Ordenado

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

Exemplo: Procurar x=15 em A[1..10]

Índice	1	2	3	4	5	6	7	8	9	10
Valor	42	7	85	13	66	90	23	5	77	31

Qual Caso Devemos Considerar?

Melhor Caso: quando encontramos o elemento logo na primeira comparação.
Pior Caso: quando precisamos examinar todos os elementos do vetor.
Caso Médio: quando o elemento pode aparecer em qualquer posição com igual probabilidade.

P: Qual desses casos é o mais relevante para analisar algoritmos em teoria da computação?

Análise de Pior Caso

Procuramos um limite superior para o tempo de execução máximo de um algoritmo em entradas de tamanho N.
Pode parecer drástico, mas na prática a análise de pior caso costuma refletir bem a eficiência real.
Alternativa: análise de caso médio (entradas “aleatórias”), porém:
- Difícil definir uma distribuição de entradas realista.
- Resultados dependem mais do modelo de aleatoriedade do que do algoritmo.
Análise de pior caso é a abordagem padrão na teoria de algoritmos.

Benchmark inicial: comparação com busca força bruta sobre todo o espaço de soluções.

Busca em Vetor Não Ordenado

P: Qual o pior caso?

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

T(n) = 3n + 1

Bubble Sort

P: Qual o pior caso?

\begin{algorithmic} \Procedure{Troca}{$A, x, y$} \State $tmp \gets A[x]$ \State $A[x] \gets A[y]$ \State $A[y] \gets tmp$ \EndProcedure \end{algorithmic}

T(n) = 2 + 2 + 1 = 5

\begin{algorithmic} \Procedure{BubbleSort}{$A$} \State $n \gets \text{length}(A)$ \For{$i \gets 1$ \To $n-1$} \For{$j \gets 1$ \To $n-i$} \If{$A[j] > A[j+1]$} \State \Call{Troca}{$A, j, j+1$} \EndIf \EndFor \EndFor \EndProcedure \end{algorithmic}

T(n) = (n-1)(n-1)(1+5) = 6n^2 - 12n + 6

Ordem de Crescimento

Obs. Focar a análise nas características importantes.

Considerar apenas os termos de maior ordem da fórmula.
Remover os termos de menor ordem.
Ignorar os coeficientes (constantes).

Um Pensamento Moderno

Tempos de Execução

Eficiência: Diferentes algoritmos para resolver o mesmo problema podem diferir dramaticamente em sua eficiência.

Problema de Ordenação: Uma sequência de n=10.000.000 números.

Algoritmo A: T(n) = 2n^2.

Algoritmo B: T(n) = 50n \log n.

Constantes \textcolor{red}{c_1}=2 e \textcolor{red}{c_2}=50 não dependem de n.

P: Qual será a diferença de eficiência dos dois algoritmos?

Tempos de Execução

Computador 1: Executa 10 bilhões de instruções por segundo.

A-1: \dfrac{2 \cdot (10^7)^2 \text{ instruções}}{10^{10} \text{ instruções/segundo}} = 20.000 \text{ segundos } (5{,}5 \text{ horas}).

B-1: \dfrac{50 \cdot (10^7) \cdot \log(10^7) \text{ instruções}}{10^{10} \text{ instruções/segundo}} = 1{,}16 \text{ segundos}.

Computador 2: Executa 10 milhões de instruções por segundo.

A-2: \dfrac{2 \cdot (10^7)^2 \text{ instruções}}{10^{7} \text{ instruções/segundo}} = 20.000.000 \text{ segundos } (231 \text{ dias}).

B-2: \dfrac{50 \cdot (10^7) \cdot \log(10^7) \text{ instruções}}{10^{7} \text{ instruções/segundo}} = 1.163 \text{ segundos } (\approx 19 \text{ minutos}).

Tempos de Execução

Tempo de execução para diferentes algoritmos em entradas de tamanho crescente em um computador executando um milhão de instruções por segundo. Em casos com tempo \geq 10^{25} anos substituído por very long. Para referência, a idade estimada do universo é de aproximadamente 4 \times 10^{17} segundos.

Eficiência: Força Bruta

Espaço de Busca:

Os problemas que vamos estudar possuem natureza discreta.
Eles envolvem uma busca implícita sobre um grande conjunto de possibilidades combinatórias.
Com o objetivo de encontrar uma solução que satisfaz um conjunto de condições.
Para muitos problemas existirá a opção de realizar uma busca por força bruta checando todas as soluções.

P: Exemplo?

Obs. Em geral, nós consideramos o algoritmo mais eficiente se seu tempo de execução no pior caso tem ordem de crescimento menor (tese de Cobham-Edmonds).

P: Uma definição para um algoritmo eficiente?

Eficiência: Polinomial

Def. Nós dizemos que um algoritmo é eficiente se tem tempo de execução polinomial.

P: E se for n^{100} vs. 1.001^{n}?

Justificativa:

Funciona na prática.
Normalmente, algoritmos têm baixas constantes e baixos expoentes.
Desenvolver um algoritmo polinomial em geral envolve entender alguma estrutura fundamental do espaço de busca do problema.

Exexceptions:

Simplex vs. Método do Elipsoide.
Busca Heurística.

Análise Assintótica

Intuição

Ideia: Suprimir fatores constantes e termos de baixa ordem.

Independente de máquina.
Foco em grandes entradas.
Descreve o crescimento de funções.
Descreve o comportamento de funções no limite.

Exemplo: 8n^3 + 50n + 86 cresce como n^3.

Terminologia: O algoritmo tem tempo de execução O(n^3), onde n é o tamanho da entrada.

Intuição

Problema: O vetor A contém o número t?

\begin{algorithmic} \Procedure{Busca}{$A, n, t$} \For{$i \gets 1$ \To $n$} \If{$A[i] = t$} \Return \textbf{true} \EndIf \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

P: Qual é o tempo de execução?
P: Quanto espaço é usado?

Intuição

Problema: O vetor A contém o número t?

\begin{algorithmic} \Procedure{Busca}{$A, n, t$} \For{$i \gets 1$ \To $n$} \If{$A[i] = t$} \Return \textbf{true} \EndIf \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

P: Qual é o tempo de execução? O(n)

Intuição

Problema: O vetor A ou o vetor B contém o número t?

\begin{algorithmic} \Procedure{Busca-Dupla}{$A, B, n, t$} \For{$i \gets 1$ \To $n$} \If{$A[i] = t$} \Return \textbf{true} \EndIf \EndFor \For{$i \gets 1$ \To $n$} \If{$B[i] = t$} \Return \textbf{true} \EndIf \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

P: Qual é o tempo de execução?

Intuição

Problema: O vetor A ou o vetor B contém o número t?

P: Qual é o tempo de execução? O(n)

Intuição

Problema: O vetor A e o vetor B contêm um número em comum?

\begin{algorithmic} \Procedure{Busca-Comum}{$A, B, n$} \For{$i \gets 1$ \To $n$} \For{$j \gets 1$ \To $n$} \If{$A[i] = B[j]$} \Return \textbf{true} \EndIf \EndFor \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

P: Qual é o tempo de execução?

Intuição

Problema: O vetor A e o vetor B contêm um número em comum?

P: Qual é o tempo de execução? O(n^2)

Intuição

Problema: O vetor A tem um elemento duplicado?

\begin{algorithmic} \Procedure{Verifica-Duplicatas}{$A, n$} \For{$i \gets 1$ \To $n$} \For{$j \gets i+1$ \To $n$} \If{$A[i] = A[j]$} \Return \textbf{true} \EndIf \EndFor \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

P: Qual é o tempo de execução? O(n^2)

Notação Big O – Limitante Superior

Def. T(n) é O(f(n)) se e somente se existe uma constante \textcolor{red}{c} > 0 e um \textcolor{#2e7d32}{n_0} \geq 0 tal que T(n) \leq \textcolor{red}{c} \cdot f(n) para todo n \geq \textcolor{#2e7d32}{n_0}.

Exemplo: T(n) = 32n^2 + 17n + 1

T(n) é O(n^2).
T(n) é O(n^3).
T(n) não é O(n).
T(n) não é O(n\log(n)).
Uso: Ordenação por Inserção é O(n^2).

Obs. \textcolor{red}{c} e \textcolor{#2e7d32}{n_0} não podem depender de n.

Notação Big O – Limitante Superior

Def. T(n) é O(f(n)) se e somente se existe uma constante \textcolor{red}{c} > 0 e um \textcolor{#2e7d32}{n_0} \geq 0 tal que T(n) \leq \textcolor{red}{c} \cdot f(n) para todo n \geq \textcolor{#2e7d32}{n_0}.

Busca em Vetor Não Ordenado

\begin{algorithmic} \Procedure{Busca-Linear}{$x,\ A[1..n]$} \For{$i \gets 1$ \To $n$} \If{$A[i] = x$} \Return $i$ \EndIf \EndFor \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

T(n) = 3n + 1

T(n) é O(n): \textcolor{red}{c} = 4 e \textcolor{#2e7d32}{n_0} = 1, \textcolor{red}{c} = 3{,}5 e \textcolor{#2e7d32}{n_0} = 2, \dots

T(n) é O(n^2), O(n^3), \dots

https://www.geogebra.org/classic/czf4djzt

Bubble Sort

T(n) = (n-1)(n-1)(1+5) = 6n^2 - 12n + 6

T(n) é O(n^2): \textcolor{red}{c} = 6 e \textcolor{#2e7d32}{n_0} = 0, \dots

T(n) é O(n^3), O(n^4), \dots

T(n) não é O(n).

https://www.geogebra.org/classic/h2f2scrd

Notação Big O: Polinômios

Def. T(n) é O(f(n)) se e somente se existe uma constante \textcolor{red}{c} > 0 e um \textcolor{#2e7d32}{n_0} tal que T(n) \leq \textcolor{red}{c} \cdot f(n) para todo n \geq \textcolor{#2e7d32}{n_0}.

Afirmação. Se T(n) = a_{\textcolor{orange}{k}} n^{\textcolor{orange}{k}} + \dots + a_1 n^1 + a_0 então T(n) = O(n^{\textcolor{orange}{k}}).

Prova. Escolha \textcolor{#2e7d32}{n_0}=1 e \textcolor{red}{c}=|a_{\textcolor{orange}{k}}|+\dots+|a_1|+|a_0|.

Nós temos que mostrar que \forall n \geq \textcolor{#2e7d32}{n_0}, T(n) \leq \textcolor{red}{c} \cdot n^{\textcolor{orange}{k}}.

T(n) \leq |a_{\textcolor{orange}{k}}|n^{\textcolor{orange}{k}}+\dots+|a_1|n^1+|a_0|n^{0}.

T(n) \leq |a_{\textcolor{orange}{k}}|n^{\textcolor{orange}{k}}+\dots+|a_1|n^{\textcolor{orange}{k}}+|a_0|n^{\textcolor{orange}{k}}.

T(n) \leq (|a_{\textcolor{orange}{k}}| + \dots + |a_1| + |a_0|)n^{\textcolor{orange}{k}}.

T(n) \leq \textcolor{red}{c} \cdot n^{\textcolor{orange}{k}} \blacksquare

https://www.geogebra.org/classic/dhycydkx