Projeto e Análise de Algoritmos I

Aula 05 - 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, André Grahl Pereira, Lucas Nunes Alegre, Marcus Ritt e Luciana Buriol.

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?

\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? 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?

\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? 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?

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)

Análise de Algoritmos

“Análise de algoritmos usualmente significa: atribuir uma expressão Big O para o tempo de execução. (Claro, Big \Theta seria muito melhor.)”

— Ian Parberry. “Problems on Algorithms”, 1994, p. 59.

Notação Big O – Limitante Superior

Notação Big O – Limitante Superior

Def. Seja T(n) uma função em n=1, 2, 3, \dots (em geral o pior tempo de execução de um algoritmo).

P: Quando T(n) é O(f(n))?

R: Se eventualmente (para n suficientemente grande), T(n) é limitado por cima por f(n) multiplicada por uma constante.

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.

Busca em Vetor Não Ordenado

\begin{algorithmic} \Procedure{Busca-Linear}{$x, A, 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

BubbleSort

\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}
  • Laço externo executa O(n) vezes.
  • Para cada iteração do laço externo, o laço interno executa O(n) vezes.
  • Então, o total de execuções do laço interno é O(n^2) (n \cdot n = n^2).
  • Cada iteração do laço interno custa O(1).
  • Logo, Ordenação por Bubble Sort é \mathcal{O}(n^2).

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_1n^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|.

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

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. Para todo \textcolor{orange}{k} \geq 1, n^{\textcolor{orange}{k}} não é O(n^{\textcolor{orange}{k}-1}).

Prova. Prova por contradição. Suponha que n^{\textcolor{orange}{k}} = O(n^{\textcolor{orange}{k}-1}).

Então existem \textcolor{red}{c}, \textcolor{#2e7d32}{n_0} tal que n^{\textcolor{orange}{k}} \leq \textcolor{red}{c} \cdot n^{\textcolor{orange}{k}-1}, \forall n \geq \textcolor{#2e7d32}{n_0}.

Mas dividindo ambos os lados por n^{\textcolor{orange}{k}-1}:

\dfrac{n^{\textcolor{orange}{k}}}{n^{\textcolor{orange}{k}-1}} \leq \dfrac{\textcolor{red}{c} \cdot n^{\textcolor{orange}{k}-1}}{n^{\textcolor{orange}{k}-1}}, \forall n \geq \textcolor{#2e7d32}{n_0}

n \leq \textcolor{red}{c}, \forall n \geq \textcolor{#2e7d32}{n_0}.

O que é uma contradição (pois \textcolor{red}{c} é uma constante). \blacksquare

Notação Big O

Sinal de Igual: O(f(n)) é um conjunto de funções, mas comumente escrevemos T(n) = O(f(n)) em vez de T(n) \in O(f(n)).


  • O domínio de f(n) em geral são os números naturais.


  • OK abusar, mas não usar incorretamente.

Notação Big \Omega (Omega) – Limitante Inferior

Notação Big \Omega (Omega) – Limitante Inferior

Def. T(n) é \Omega(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) \geq \textcolor{red}{c} \cdot f(n) para todo n \geq \textcolor{#2e7d32}{n_0}.


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

  • T(n) é \Omega(n^2).
  • T(n) é \Omega(n).
  • T(n) não é \Omega(n^3).
  • T(n) não é \Omega(n^3\log(n)).

Uso: Ordenação por Inserção é \Omega(n).

Notação Big \Theta (Theta) – Limites Precisos

Notação Big \Theta (Theta) – Limites Precisos

Def. T(n) é \Theta(f(n)) se e somente se existem constantes \textcolor{red}{c_1}, \textcolor{red}{c_2} > 0 e um \textcolor{#2e7d32}{n_0} \geq 0 tal que \textcolor{red}{c_1} \cdot f(n) \leq T(n) \leq \textcolor{red}{c_2} \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) é \Omega(n^2).
  • T(n) é \Theta(n^2).
  • T(n) não é \Theta(n^3).
  • T(n) não é \Theta(n).

Uso: BubbleSort é \Theta(n^2).

Notação Big \Theta (Theta) – Limites Precisos

Def. T(n) é \Theta(f(n)) se e somente se T(n) = O(f(n)) e T(n) = \Omega(f(n)).


Análise Assintótica

Exemplo: Seja T(n) = \frac{1}{2}n^2 + 3n. Quais dos seguintes é verdadeiro (apresente constantes e n_0)?

  • T(n) = O(n)?
  • T(n) = \Omega(n)?
  • T(n) = O(n^3)?
  • T(n) = \Theta(n^2)?

Visualização Interativa: O, \Omega e \Theta

Demonstração Interativa: Comparação de Big O, Omega e Theta
Fórmula Renderizada:
T(n) = 0.5n² + 3n
|
f(n) = n²
✓ Notação válida

Análise Assintótica

Exemplo: Seja T(n) = \frac{1}{2}n^2 + 3n. Quais dos seguintes é verdadeiro (apresente constantes e n_0)?


  • T(n) não é O(n).
  • T(n) = \Omega(n), \textcolor{#2e7d32}{n_0}=1, \textcolor{red}{c}=\frac{1}{2}.
  • T(n) = O(n^3), \textcolor{#2e7d32}{n_0}=1, \textcolor{red}{c}=4.
  • T(n) = \Theta(n^2), \textcolor{#2e7d32}{n_0}=1, \textcolor{red}{c_1}=\frac{1}{2}, \textcolor{red}{c_2}=4.

Limites Estritos

Limites Estritos

  • Além das notações O, \Omega e \Theta, existem duas notações para representar limites estritos.

  • Essas duas notações, todavia, são raramente encontradas na literatura de computação.

  • Nos próximos slides, apresentamos a notação o e \omega para completude, porém, não as utilizaremos nesta disciplina.

Notação Pequeno o – Limitante Superior Estrito

Def. T(n) é o(f(n)) se e somente se para toda constante \textcolor{red}{c} > 0 existe uma constante \textcolor{#2e7d32}{n_0} > 0 tal que T(n) < \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^3).
  • T(n) não é o(n^2).


Uso: BubbleSort é o(n^3), mas não é o(n^2).

Notação Pequeno \omega (Omega) – Limitante Inferior Estrito

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


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

  • T(n) é \omega(n).
  • T(n) não é \omega(n^2).


Uso: BubbleSort é \omega(n).

Resumo das Notações Assintóticas

Resumo das Notações Assintóticas

  • \textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) \approx \textcolor{blue}{f}(n) \leq \textcolor{orange}{g}(n)
    • \textcolor{blue}{f} cresce no máximo tão rápido quanto \textcolor{orange}{g}, é um limitante superior.
  • \textcolor{blue}{f}(n) = \Omega(\textcolor{orange}{g}(n)) \approx \textcolor{blue}{f}(n) \geq \textcolor{orange}{g}(n)
    • \textcolor{blue}{f} cresce no mínimo tão rápido quanto \textcolor{orange}{g}, é um limitante inferior.
  • \textcolor{blue}{f}(n) = \Theta(\textcolor{orange}{g}(n)) \approx \textcolor{blue}{f}(n) = \textcolor{orange}{g}(n)
    • \textcolor{blue}{f} cresce tão rápido quanto \textcolor{orange}{g}, é um limitante preciso.
  • \textcolor{blue}{f}(n) = o(\textcolor{orange}{g}(n)) \approx \textcolor{blue}{f}(n) < \textcolor{orange}{g}(n)
    • \textcolor{blue}{f} cresce mais devagar que \textcolor{orange}{g}, é um limitante superior estrito.
  • \textcolor{blue}{f}(n) = \omega(\textcolor{orange}{g}(n)) \approx \textcolor{blue}{f}(n) > \textcolor{orange}{g}(n)
    • \textcolor{blue}{f} cresce mais rápido que \textcolor{orange}{g}, é um limitante inferior estrito.

Definições Alternativas (Limites)

Definições Alternativas (Limites)

\textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) \iff \lim_{n\to\infty} \dfrac{\textcolor{blue}{f}(n)}{\textcolor{orange}{g}(n)} < \infty


\textcolor{blue}{f}(n) = \Omega(\textcolor{orange}{g}(n)) \iff \lim_{n\to\infty} \dfrac{\textcolor{blue}{f}(n)}{\textcolor{orange}{g}(n)} > 0


\textcolor{blue}{f}(n) = \Theta(\textcolor{orange}{g}(n)) \iff \lim_{n\to\infty} \dfrac{\textcolor{blue}{f}(n)}{\textcolor{orange}{g}(n)} = \textcolor{red}{c} > 0


\textcolor{blue}{f}(n) = o(\textcolor{orange}{g}(n)) \iff \lim_{n\to\infty} \dfrac{\textcolor{blue}{f}(n)}{\textcolor{orange}{g}(n)} = 0


\textcolor{blue}{f}(n) = \omega(\textcolor{orange}{g}(n)) \iff \lim_{n\to\infty} \dfrac{\textcolor{blue}{f}(n)}{\textcolor{orange}{g}(n)} = \infty

História

Quem Culpar?

“Well, I think I have beat this issue to death, knowing of no other arguments pro or con the introduction of \Theta and \Omega. On the basis of the issues discussed here, I propose that members of SIGACT, and editors of computer science and mathematics journals, adopt the O, \Theta, \Omega notations as defined above, unless a better alternative can be found reasonably soon.”

— “Big Omicron and Big Omega and Big Theta”, SIGACT News, 1976.

Quem Culpar?

Donald Knuth:

  • Professor emérito da Universidade de Stanford.
  • É o autor do livro The Art of Computer Programming: American Scientist has included this work among “100 or so Books that shaped a Century of Science”.
  • Prêmio Turing em 1974.
  • Análise de Algoritmos e \LaTeX.

Relações Assintóticas

Transitividade

Def. (Transitividade): Se \textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = O(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = O(\textcolor{#0284c7}{h}(n)).

Prova. É dado que:

  • \textcolor{blue}{f}(n) \leq c' \textcolor{orange}{g}(n) para todo n \geq n_0' e
  • \textcolor{orange}{g}(n) \leq c'' \textcolor{#0284c7}{h}(n) para todo n \geq n_0''.
  • Considere n_0 = \max(n_0', n_0''), então nós temos que
  • \textcolor{blue}{f}(n) \leq c' \textcolor{orange}{g}(n) \leq c' c'' \textcolor{#0284c7}{h}(n).
  • Logo, \textcolor{blue}{f}(n) \leq c' c'' \textcolor{#0284c7}{h}(n) e
  • \textcolor{blue}{f}(n) = O(\textcolor{#0284c7}{h}(n)). \blacksquare

Transitividade

Def. (Transitividade): Se \textcolor{blue}{f}(n) = \Omega(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = \Omega(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = \Omega(\textcolor{#0284c7}{h}(n)).


P: O que podemos concluir?


Se \textcolor{blue}{f}(n) = \Theta(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = \Theta(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = \Theta(\textcolor{#0284c7}{h}(n)).

Transitividade

  • Se \textcolor{blue}{f}(n) = \Theta(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = \Theta(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = \Theta(\textcolor{#0284c7}{h}(n)).
  • Se \textcolor{blue}{f}(n) = \Omega(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = \Omega(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = \Omega(\textcolor{#0284c7}{h}(n)).
  • Se \textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = O(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = O(\textcolor{#0284c7}{h}(n)).
  • Se \textcolor{blue}{f}(n) = o(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = o(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = o(\textcolor{#0284c7}{h}(n)).
  • Se \textcolor{blue}{f}(n) = \omega(\textcolor{orange}{g}(n)) e \textcolor{orange}{g}(n) = \omega(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) = \omega(\textcolor{#0284c7}{h}(n)).

Reflexividade

  • \textcolor{blue}{f}(n) = \Theta(\textcolor{blue}{f}(n)).
  • \textcolor{blue}{f}(n) = \Omega(\textcolor{blue}{f}(n)).
  • \textcolor{blue}{f}(n) = O(\textcolor{blue}{f}(n)).
  • \textcolor{blue}{f}(n) = o(\textcolor{blue}{f}(n))? Não.
  • \textcolor{blue}{f}(n) = \omega(\textcolor{blue}{f}(n))? Não.

Simetria e Simetria Transposta

  • \textcolor{blue}{f}(n) = \Theta(\textcolor{orange}{g}(n)) se e somente se \textcolor{orange}{g}(n) = \Theta(\textcolor{blue}{f}(n)).
  • \textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) se e somente se \textcolor{orange}{g}(n) = \Omega(\textcolor{blue}{f}(n)).
  • \textcolor{blue}{f}(n) = o(\textcolor{orange}{g}(n)) se e somente se \textcolor{orange}{g}(n) = \omega(\textcolor{blue}{f}(n)).

Prova (\textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) \iff \textcolor{orange}{g}(n) = \Omega(\textcolor{blue}{f}(n))):

  • \textcolor{blue}{f}(n) = O(\textcolor{orange}{g}(n)) \iff \exists \textcolor{red}{c} > 0, \textcolor{#2e7d32}{n_0} \geq 0 tal que \textcolor{blue}{f}(n) \leq \textcolor{red}{c} \cdot \textcolor{orange}{g}(n) para todo n \geq \textcolor{#2e7d32}{n_0}.
  • Dividindo por \textcolor{red}{c}:
  • \textcolor{orange}{g}(n) \geq \frac{1}{\textcolor{red}{c}} \cdot \textcolor{blue}{f}(n) para todo n \geq \textcolor{#2e7d32}{n_0}.
  • Escolhendo c' = \frac{1}{\textcolor{red}{c}} > 0, temos por definição que \textcolor{orange}{g}(n) = \Omega(\textcolor{blue}{f}(n)). \blacksquare

Soma de Funções

Def. (Soma de Funções): Se \textcolor{blue}{f}(n) = O(\textcolor{#0284c7}{h}(n)) e \textcolor{orange}{g}(n) = O(\textcolor{#0284c7}{h}(n)) então \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = O(\textcolor{#0284c7}{h}(n)).

Prova. É dado que:

  • \textcolor{blue}{f}(n) \leq c' \textcolor{#0284c7}{h}(n) para todo n \geq n_0' e
  • \textcolor{orange}{g}(n) \leq c'' \textcolor{#0284c7}{h}(n) para todo n \geq n_0''.
  • Considere n_0 = \max(n_0', n_0''), então nós temos que
  • \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) \leq c' \textcolor{#0284c7}{h}(n) + c'' \textcolor{#0284c7}{h}(n) = (c' + c'') \textcolor{#0284c7}{h}(n).
  • Logo, \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = O(\textcolor{#0284c7}{h}(n)). \blacksquare

Soma de Funções

Def. (Soma de Funções): Seja \textcolor{orange}{k} uma constante, \textcolor{blue}{f}_1(n), \textcolor{blue}{f}_2(n), \dots, \textcolor{blue}{f}_{\textcolor{orange}{k}}(n) e \textcolor{#0284c7}{h}(n) funções tal que \forall i, \textcolor{blue}{f}_i(n) = O(\textcolor{#0284c7}{h}(n)). Então \textcolor{blue}{f}_1(n) + \textcolor{blue}{f}_2(n) + \dots + \textcolor{blue}{f}_{\textcolor{orange}{k}}(n) = O(\textcolor{#0284c7}{h}(n)).

Consequência:

  • Para um algoritmo com duas partes onde é fácil mostrar que uma das partes possui o maior custo.
  • Assintoticamente o custo do algoritmo é o custo da parte de maior custo.
  • Exemplo: Condicional.

Soma de Funções

Def. (Soma de Funções): Sejam \textcolor{blue}{f}(n) e \textcolor{orange}{g}(n) duas funções tal que \textcolor{orange}{g}(n) = O(\textcolor{blue}{f}(n)). Então \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = \Theta(\textcolor{blue}{f}(n)).

Prova.

  • Temos que \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) \geq \textcolor{blue}{f}(n),
  • Logo, \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = \Omega(\textcolor{blue}{f}(n)).
  • Já que \textcolor{orange}{g}(n) = O(\textcolor{blue}{f}(n)) e \textcolor{blue}{f}(n) = O(\textcolor{blue}{f}(n)), então
  • \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = O(\textcolor{blue}{f}(n)).
  • Logo, \textcolor{blue}{f}(n) + \textcolor{orange}{g}(n) = \Theta(\textcolor{blue}{f}(n)). \blacksquare

Propriedades Assintóticas de Funções

Polinômios

Def. f(n) = a_{\textcolor{orange}{k}} n^{\textcolor{orange}{k}} + \dots + a_1 n^1 + a_0 para algum \textcolor{orange}{k} > 0 com a_{\textcolor{orange}{k}} > 0.


Algoritmos Polinomiais:

  • O(n^2) e O(n^3).
  • O(n^{\textcolor{orange}{k}}) onde \textcolor{orange}{k} não é inteiro.
  • O(n^{1{,}59}) e O(\sqrt{n}).
  • O(n\log(n)).

Logaritmos

Def. \log_{\textcolor{blue}{b}} n é o número x tal que \textcolor{blue}{b}^x = n.


  • \textcolor{red}{a} = \textcolor{blue}{b}^{\log_{\textcolor{blue}{b}}\textcolor{red}{a}}
  • \log_c(\textcolor{red}{a}\textcolor{blue}{b}) = \log_c\textcolor{red}{a} + \log_c\textcolor{blue}{b}
  • \log_{\textcolor{blue}{b}}\textcolor{red}{a}^n = n\log_{\textcolor{blue}{b}}\textcolor{red}{a}
  • \log_{\textcolor{blue}{b}}\textcolor{red}{a} = \dfrac{\log_c\textcolor{red}{a}}{\log_c\textcolor{blue}{b}}
  • \log_{\textcolor{blue}{b}}(1/\textcolor{red}{a}) = -\log_{\textcolor{blue}{b}}\textcolor{red}{a}
  • \log_{\textcolor{blue}{b}}\textcolor{red}{a} = \dfrac{1}{\log_{\textcolor{red}{a}}\textcolor{blue}{b}}
  • \textcolor{red}{a}^{\log_{\textcolor{blue}{b}}c} = c^{\log_{\textcolor{blue}{b}}\textcolor{red}{a}}

Logaritmos

Afirmação. Para todo b > 1 e todo \textcolor{orange}{k} > 0, nós temos que \log_{\textcolor{blue}{b}} n = o(n^{\textcolor{orange}{k}}) (portanto \log_{\textcolor{blue}{b}} n \neq \Theta(n^{\textcolor{orange}{k}})).

Prova.

\lim_{n\to\infty} \frac{\log_{\textcolor{blue}{b}} n}{n^{\textcolor{orange}{k}}} = 0

Intuição:

  • Escrevemos \log_{\textcolor{blue}{b}} n = \dfrac{\ln n}{\ln \textcolor{blue}{b}}.
  • O limite se torna: \lim_{n\to\infty} \dfrac{\ln n}{\ln \textcolor{blue}{b} \cdot n^{\textcolor{orange}{k}}}.
  • Como \ln \textcolor{blue}{b} é uma constante que independe de n, podemos fatorá-lo para fora do limite.
  • O limite é do tipo \infty/\infty, então podemos aplicar a regra de L’Hôpital.
  • Derivando numerador e denominador: \lim_{n\to\infty} \dfrac{1/n}{\textcolor{orange}{k} n^{\textcolor{orange}{k}-1}} = \lim_{n\to\infty} \dfrac{1}{\textcolor{orange}{k} n^{\textcolor{orange}{k}}} = 0. \blacksquare

Logaritmos

Def. \log_{\textcolor{blue}{b}} n é o número x tal que \textcolor{blue}{b}^x = n.


Obs. A base do logaritmo não importa.

Afirmação. \log_{\textcolor{red}{a}} n = \Theta(\log_{\textcolor{blue}{b}} n).

Prova.

  • \log_{\textcolor{red}{a}} n = \dfrac{\log_{\textcolor{blue}{b}} n}{\log_{\textcolor{blue}{b}} \textcolor{red}{a}}
  • \log_{\textcolor{red}{a}} n = \dfrac{1}{\log_{\textcolor{blue}{b}} \textcolor{red}{a}} \cdot \log_{\textcolor{blue}{b}} n
  • \dfrac{1}{\log_{\textcolor{blue}{b}} \textcolor{red}{a}} é uma constante maior que zero que independe de n. \blacksquare

Exponenciais

Def. f(n) = \textcolor{blue}{r}^n com \textcolor{blue}{r} > 1.


Afirmação. Para todo \textcolor{blue}{r} > 1 e todo \textcolor{orange}{k} > 0, nós temos que n^{\textcolor{orange}{k}} = o(\textcolor{blue}{r}^n).

Prova. \lim_{n\to\infty} \frac{n^{\textcolor{orange}{k}}}{\textcolor{blue}{r}^n} = 0

Intuição: O denominador cresce mais rapidamente.

  • Como o limite é do tipo \infty/\infty, aplicamos a regra de L’Hôpital.
  • Derivando o numerador \textcolor{orange}{k} vezes, obtemos uma constante \textcolor{orange}{k}!.
  • Derivando o denominador \textcolor{orange}{k} vezes, ainda teremos um termo exponencial (\ln \textcolor{blue}{r})^{\textcolor{orange}{k}} \cdot \textcolor{blue}{r}^n. \blacksquare

Exponenciais

Def. f(n) = \textcolor{blue}{r}^n com \textcolor{blue}{r} > 1.


  • \textcolor{blue}{r}^0 = 1
  • \textcolor{blue}{r}^1 = \textcolor{blue}{r}
  • \textcolor{blue}{r}^{-1} = \dfrac{1}{\textcolor{blue}{r}}
  • (\textcolor{blue}{r}^m)^n = (\textcolor{blue}{r}^n)^m
  • (\textcolor{blue}{r}^m)^n = \textcolor{blue}{r}^{nm}
  • \textcolor{blue}{r}^m \cdot \textcolor{blue}{r}^n = \textcolor{blue}{r}^{n+m}

Exponenciais

Obs. A base da exponencial importa.

Afirmação. Para \textcolor{blue}{r} > \textcolor{orange}{s}, \textcolor{blue}{r}^n \neq \Theta(\textcolor{orange}{s}^n).

Prova. Suponha, para obter contradição, que \textcolor{blue}{r}^n = \Theta(\textcolor{orange}{s}^n). Então existem constantes \textcolor{red}{c_1}, \textcolor{red}{c_2} > 0 e n_0 tais que: \textcolor{red}{c_1} \textcolor{orange}{s}^n \leq \textcolor{blue}{r}^n \leq \textcolor{red}{c_2} \textcolor{orange}{s}^n \quad \text{para todo } n \geq n_0.

Em particular, teríamos a cota superior \textcolor{blue}{r}^n \leq \textcolor{red}{c_2} \textcolor{orange}{s}^n, isto é, \left(\dfrac{\textcolor{blue}{r}}{\textcolor{orange}{s}}\right)^n \leq \textcolor{red}{c_2} \quad \text{para todo } n \geq n_0.

Mas como \dfrac{\textcolor{blue}{r}}{\textcolor{orange}{s}} > 1, temos \left(\dfrac{\textcolor{blue}{r}}{\textcolor{orange}{s}}\right)^n \to \infty quando n \to \infty, o que contradiz a existência de tal \textcolor{red}{c_2} independente de n. Logo, \textcolor{blue}{r}^n \notin O(\textcolor{orange}{s}^n) e \textcolor{blue}{r}^n \neq \Theta(\textcolor{orange}{s}^n). \blacksquare

Fatoriais

Obs. Fatoriais crescem mais rapidamente que exponenciais de base fixa.

Afirmação. Para todo \textcolor{blue}{r} > 0, \textcolor{blue}{r}^n = o(n!) (então n! \notin O(\textcolor{blue}{r}^n)).

Prova. Para n \geq 2: n! = \prod_{\textcolor{orange}{k}=1}^n \textcolor{orange}{k} \geq \prod_{\textcolor{orange}{k}=\lceil n/2 \rceil + 1}^n \textcolor{orange}{k} \geq \left(\frac{n}{2}\right)^{n/2}.

Logo, 0 \leq \dfrac{\textcolor{blue}{r}^n}{n!} \leq \dfrac{\textcolor{blue}{r}^n}{\left(\frac{n}{2}\right)^{n/2}} = \left(\dfrac{\textcolor{blue}{r}}{\sqrt{n/2}}\right)^n.

Como \textcolor{blue}{r} é constante e \sqrt{n/2} \to \infty, existe n_0 tal que \dfrac{\textcolor{blue}{r}}{\sqrt{n/2}} < 1 para todo n \geq n_0, e então \lim_{n\to\infty} \left(\dfrac{\textcolor{blue}{r}}{\sqrt{n/2}}\right)^n = 0. Portanto, \lim_{n\to\infty} \dfrac{\textcolor{blue}{r}^n}{n!} = 0, isto é, \textcolor{blue}{r}^n = o(n!). \blacksquare

Principais Classes Assintóticas

Constante – O(1)

\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}


Outros exemplos: deletar elemento de um vetor indexado, pop de uma pilha, \dots

Sublinear – O(\log n)

A é um vetor ordenado de tamanho n.

\begin{algorithmic} \Procedure{Busca-Binaria}{$A, n, T$} \State $L \gets 0$ \State $R \gets n-1$ \While{$L \leq R$} \State $m \gets L + \lfloor (R - L)/2 \rfloor$ \If{$A[m] < T$} \State $L \gets m + 1$ \ElsIf{$A[m] > T$} \State $R \gets m - 1$ \Else \Return $m$ \EndIf \EndWhile \Return \textsc{Não-Encontrado} \EndProcedure \end{algorithmic}

Por que a Busca Binária é O(\log n)?

  • A cada passo, o vetor é dividido ao meio.
  • Restam \frac{n}{2} elementos, depois \frac{n}{4}, depois \frac{n}{8}, e assim por diante.
  • O processo termina quando sobra apenas 1 elemento.

n \;\to\; \frac{n}{2} \;\to\; \frac{n}{4} \;\to\; \frac{n}{8} \;\to\; \dots \;\to\; 1

Quantas divisões? Seja \textcolor{orange}{k} o número de passos. Temos:

\frac{n}{2^{\textcolor{orange}{k}}} = 1 \;\;\;\Rightarrow\;\;\; \textcolor{orange}{k} = \log_2 n.

Linear – O(n)

\begin{algorithmic} \Procedure{Merge}{$A, start, mid, end$} \For{$i \gets start$ \To $end$} \State $Aux[i] \gets A[i]$ \EndFor \State $i \gets start$; $j \gets mid+1$; $k \gets start$ \While{$i \leq mid$ \And $j \leq end$} \If{$Aux[i] < Aux[j]$} \State $A[k] \gets Aux[i]$; $i \gets i+1$ \Else \State $A[k] \gets Aux[j]$; $j \gets j+1$ \EndIf \State $k \gets k+1$ \EndWhile \While{$i \leq mid$} \State $A[k] \gets Aux[i]$; $i \gets i+1$; $k \gets k+1$ \EndWhile \While{$j \leq end$} \State $A[k] \gets Aux[j]$; $j \gets j+1$; $k \gets k+1$ \EndWhile \EndProcedure \end{algorithmic}
  • Há um vetor auxiliar Aux que recebe a porção do vetor a ser ordenada.
  • i aponta para o início do primeiro subvetor.
  • j aponta para o início do segundo subvetor.
  • k aponta para a posição de saída em A.
  • O laço principal compara os elementos dos dois subvetores e insere em ordem.


Outro exemplo: encontrar o máximo de um vetor.

O(n \log n)

\begin{algorithmic} \Procedure{MergeSort}{$A, start, end$} \If{$start < end$} \State $mid \gets \lfloor (start + end)/2 \rfloor$ \State \Call{MergeSort}{$A, start, mid$} \State \Call{MergeSort}{$A, mid+1, end$} \State \Call{Intercala}{$A, start, mid, end$} \EndIf \EndProcedure \end{algorithmic}


Observações:

  • start e end representam os índices de início e fim da parte do vetor a ser ordenada.
  • Para ordenar o vetor inteiro: MergeSort(A, 1, length(A)).

Complexidade de Tempo do MergeSort (pior caso)

  • Em cada nível da recursão, o vetor de tamanho n é dividido em duas partes de tamanho \approx n/2.
  • O custo de intercalar dois subvetores de tamanho total n é O(n).
  • A profundidade da recursão é \log_2 n (pois a cada passo dividimos ao meio).
  • Assim, em cada um dos \log_2 n níveis, o custo é O(n).

Complexidade de Tempo do MergeSort (pior caso)

Quadrática – O(n^2)

\begin{algorithmic} \Procedure{Gale-Shapley}{$H, E$} \State Inicialize $S \gets \emptyset$, e todos os hospitais e estudantes como livres \While{existe um hospital livre $h$ que ainda não propôs a todo estudante} \State Escolha um tal hospital $h$ \State Seja $e$ o estudante de maior preferência de $h$ ao qual $h$ ainda não propôs \If{$e$ está livre} \State $S \gets S \cup \{(h, e)\}$ \Else \State $e$ está atualmente emparelhado com $h'$ \If{$e$ prefere $h'$ a $h$} \State $h$ continua livre \Else \State $S \gets S \setminus \{(h', e)\}$ \State $S \gets S \cup \{(h, e)\}$ \State $h'$ fica livre \EndIf \EndIf \EndWhile \Return $S$ \EndProcedure \end{algorithmic}

Nota: depende de estruturas de dados adequadas.

Outros exemplos: InsertionSort, BubbleSort, QuickSort*, encontrar o par de pontos mais próximos por força bruta.

Cúbica – O(n^3)

Problema: Dados S_1, S_2, \dots, S_n \subseteq \{1, 2, \dots, n\}, decidir se existe um par (S_i, S_j) disjunto (sem elementos em comum).

\begin{algorithmic} \Procedure{Existe-Par-Disjunto}{$S_1, \dots, S_n$} \For{$i \gets 1$ \To $n$} \For{$j \gets 1$ \To $n$} \If{$i \neq j$} \State $encontrouComum \gets \textbf{false}$ \For{\textbf{cada elemento} $p$ \textbf{de} $S_i$} \If{$p \in S_j$} \State $encontrouComum \gets \textbf{true}$; \textbf{break} \EndIf \EndFor \If{$\neg encontrouComum$} \Return \textbf{true} \EndIf \EndIf \EndFor \EndFor \Return \textbf{false} \EndProcedure \end{algorithmic}

Nota: Existem algoritmos que melhoram o tempo de execução O(n^3) para este problema, mas são bastante complexos.

Exponenciais

  • Encontrar o conjunto independente máximo de um grafo: O(2^n)

  • Encontrar uma solução exata para o problema do caixeiro-viajante: O(n!)

https://en.wikipedia.org/wiki/Travelling_salesman_problem#/media/File:Bruteforce.gif

Prêmio Millennium

Encontrar um algoritmo polinomial para o problema do caixeiro-viajante vale 1 milhão de dólares!

?