Análise de Algoritmos

Ronaldo Cristiano Prati

Bloco A, sala 513-2

ronaldo.prati@ufabc.edu.br

Ordenação

  • Algortimos de ordenação ordenam uma sequência de valores
    • vamos assumir por enquanto que os valores a serem ordenados são todos distintos entre si.

Ordenação por inserção

  • Dado um vetor AA com nn números, a ordenação por inserção irá executar nn rodadas de instruções em que:
  • A cada rodada, temos um subvetor de AA ordenado que contém um elemento a mais do que o subvetor da rodada anterior:
    • Ao fim da i1i-1-ésima rodada, o subvetor A[1..i1]A[1..i-1] estará ordenado
  • Sabendo que o A[1..i1]A[1..i-1] está ordenado, é fácil encaixar o elemento A[i] na posição correta, para deixar o subvetor A[1..i]A[1..i] ordenado:
    • Seja atual=A[i]atual = A[i]. Iterativamente troque o elemento atualatual com os anteriores enquanto eles forem maiores que atualatual.

Ordenação por inserção

  • Algoritmo InsertionSort

Ordenação por inserção

Ordenação por inserção

Uma possível implementação em Python

def insertion_sort(A):
  for i in range(1, len(A)):
    atual = A[i]
    j = i - 1
    while j >= 0 and A[j] > atual:
      A[j+1] = A[j]
      j -= 1
    A[j+1] = atual

(observe que em Python a posição inicial do vetor é 0, então os índices foram ajustados adequadamente.)

Análise do InsertionSort

  • Vamos reponder as três perguntas com relação a análise de algoritmos:
    1. O algoritmo está correto?
    2. Quantos recursos o algoritmo consome?
    3. É possível fazer melhor?

Corretude do InsertionSort

  • Algoritmos frequentemente inicializam, modificam, apagam ou inserem novos dados

    • Existe uma maneira de provar que o algoritmo funciona, sem checar (as infinitas) entradas?
  • Ideia principal: encontrar um invariante.

    • para raciociar sobre o comportamento de um algoritmo, frequentemente é útil identificar coisas que não mudam.

Invariante do InsertionSort

  • Suponha que temos o vetor [1,2,3,5,6,7,84][1,2,3,5,6,7,8|\mathbf{4}], em que o subvetor [1,2,3,5,6,7,8][1,2,3,5,6,7,8] já está ordenado e o elemento atual é o 4\mathbf{4}.
  • Iserir o 4\mathbf{4} imediatamente à direita do maior elemento do subvetor que é menor que 4\mathbf{4} (isto é, à direita de 33) produz um outro vetor ordenado.
  • Observe que este novo vetor é mais longo que o anterior por um elemento: A=[1,2,3,4,5,6,7,8]A=[1,2,3,\mathbf{4},5,6,7,8]

Invariante do InsertionSort

  • Podemos aplicar essa ideia a cada passo:

    • [6,5,3,1,8,7,2,4][6|,\mathbf{5},3,1,8,7,2,4]: o subvetor [6][6] está ordenado. Inserir o 5\mathbf{5} na posição correta gera um subvetor ordenado [5,6][5,6]
    • [5,6,3,1,8,7,2,4][5,6|,\mathbf{3},1,8,7,2,4]: o subvetor [5,6][5,6] está ordenado. Inserir o 3\mathbf{3} na posição correta gera um subvetor ordenado [3,5,6][3,5,6]
    • [3,5,6,1,8,7,2,4][3,5,6,|\mathbf{1},8,7,2,4]: o subvetor [3,5,6][3,5,6] está ordenado. Inserir o 1\mathbf{1} na posição correta gera um subvetor ordenado [1,3,5,6][1,3,5,6]
    • \cdots
    • [1,2,3,5,6,7,84][1,2,3,5,6,7,8|\mathbf{4}]: o subvetor [1,2,3,5,6,7,8][1,2,3,5,6,7,8] está ordenado. Inserir o 4\mathbf{4} na posição correta gera um subvetor ordenado [1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8]

Corretude do InsertionSort

  • Existe um nome para a condição que é verdadeira antes e depois de cada iteração de um laço: invariante de laço

  • Para provar a corretudo do InsertionSort, vamos usar o invariante de laço e fazer uma prova por indução

  • Nesse caso, o invariante de laço é que, ao início da iteração ii (a interação que queremos inserir o elemento A[i]A[i] no subvetor ordenado), o subvetor A[1..i1]A[1..i-1] está ordenado

Corretude do InsertionSort

  • Em uma prova por indução, temos quatro componentes:

    • Hipótese de indução: o invariante de laço é verdadeiro depois da ii-ésima iteração

    • Caso base: o invariante de laço é verdadeiro na primeira iteração.

    • Passo de indução: se o invariante de laço é verdadeira dapara a ii-ésima interação, então ele também é verdadeiro para i+1i+1-ésima iteração

    • Conclusão: se o invariante de laço é veradeira após a última iteração, então o algoritmo está correto!

Corretude do InsertionSort

  • Especificamente para o InsertionSort:

    • Hipótese de indução: na iteração ii, A[1..i1]A[1..i-1] está ordenado

    • Caso base: A[1]A[1] está ordenado.

    • Passo de indução: ao inserir o elemento A[i]A[i], A[1..i]A[1..i] continua ordenado

    • Conclusão: na nn-ésima iteração (ao final do algortimo), A[1..n]A[1..n] (portanto o vetor inteiro) estará ordenado.

Corretude do InsertionSort

  • O caso base é verdade, pois um sub-vetor de 1 único elemento está ordenado.
  • Vamos supor que a hipótese de indução é válida para um i(2..n)i \in (2..n) (isto é, A[1..i1]A[1..i-1] está ordenado).
  • Enquanto o laço "move" o elemento atual(A[i])atual (A[i]) para a esquerda, os elementos maiores que atualatual são movidos uma posição para a direita, e continuam or ordem.

Corretude do InsertionSort

  • Quanto atualatual chega na posição "correta" no subvetor, todos os elementos à direita são maiores e todos os elementos a direta são menores que atualatual. Portanto, A[1..i]A[1..i] está ordenado e a invariante se mantém.
  • O laço termina quando i=ni=n, portanto A[1..n]A[1..n] está ordenado e contendo todos os elementos do vetor AA.
  • Podemos concluir que o algoritmo está correto.

Quantos recursos o algoritmo consome?

  • A quantidade de memória extra é desprezível: só precisamos de espaço extra para armazenar atualatual (ordenação in place)

  • Com relação ao tempo:

    • O laço da linha 1 é executado nn vezes. Consequentemente, as linhas 2, 3 e 7 são executadas n1n-1 vezes cada.
    • Seja rir_i a quantidade de vezes que o laço da linha 4 é executado para a iteração ii. As linhas 5 e 6 são executacas ri1r_i -1 vezes cada.

Quantos recursos o algoritmo consome?

  • Vamos escrever o tempo gasto pelo algoritmo com um polinômio T(n)T(n):

    T(n)=n+3(n1)laço externo+i=2nri+2i=2n(ri1)laço internoT(n)=4n2+3i=2nri2i=2n1T(n)=2n+3i=2nri\begin{aligned} T(n) &= \underbrace{n + 3(n-1)}_{\text{laço externo}}+ \underbrace {\sum_{i=2}^n r_i + 2\sum_{i=2}^n (r_i-1) }_{\text{laço interno}} \\ T(n) &= 4n-2 + 3 \sum_{i=2}^n r_i -2 \sum_{i=2}^n 1 \\ T(n) &= 2n + 3 \sum_{i=2}^n r_i \end{aligned}

  • Para saber quantos recursos o algoritmo consome, precisamos saber o valor de rir_i.

Quantos recursos o algoritmo consome?

  • Melhor caso:

    • se o vetor já estiver odenado, o laço da linha 4 é executado 1 única vez (ri=1,i2..nr_i =1, \forall i \in 2..n) para cada iteração.

    T(n)=2n+3i=2nri=5n3\begin{aligned} T(n) &= 2n + 3 \sum_{i=2}^n r_i \\ &= 5n -3 \end{aligned}

Quantos recursos o algoritmo consome?

  • Pior caso:
    • se o vetor estiver inversamente odenado, o laço da linha 4 é executado ii vezes (ri=i,i2..nr_i =i, \forall i \in 2..n) para cada iteração.
      T(n)=2n+3i=2nri=n2+2n6\begin{aligned} T(n) &= 2n + 3 \sum_{i=2}^n r_i \\ &= n^2 + 2n - 6 \end{aligned}
      (veja a somatório de Gauss para calcular o somatório)

Quantos recursos o algoritmo consome?

  • Caso médio:
    - para fazer uma análise do caso médio, precisamos fazer alguma suposição sobre rir_i. Supunha que, em um caso típico, linha 4 é executada metade das vezes com relação ao pior caso (ri=i2,i2..nr_i =\frac{i}{2}, \forall i \in 2..n) para cada iteração.

T(n)=2n+3i=2nri=2n+n(n1)4\begin{aligned} T(n) &= 2n + 3 \sum_{i=2}^n r_i \\ &= 2n + \frac{n(n-1)}{4} \end{aligned}

Notação assintótica

  • O que significa medir o "tempo de execução" de um algoritmo?
    • Engenheiros provavelmente se importam com o "tempo de execução" (wall time): quanto tempo o algoritmo leva em segundos, minutos, horas, etc.
    • Isso depende de características do hardware, implementação, linguagem de programação, etc.
    • Apesar de importante, não será o nosso foco
    • Ao invés, queremos uma medida que é independente dessas considerações.

Notação assintótica

  • Ideia principal: focar como o tempo de execução escala em função de nn (o tamanho da entrada).
    • Vantagens:
      • Abstrai o hardware, linguagem de programação, etc.
      • Mais genérica que a abordagem de implementar e testar
    • Desvantagens:
      • Só faz sentido se nn é grande comparado com as constantes (9.999.999.999.999n9.999.999.999.999 n é melhor que n2n^2?)

A notação OO

  • A notação OO (big-O) é uma notação matemática para considerar o limite superior para o crescimento de uma função
    • Informalmente, ela pode ser obtida ignorando-se as constantes e termos que não dominam o crescimento da função

A notação OO

  • Seja T(n)T(n) e g(n)g(n) funções sobre inteiros positivos.

    • Podemos pensar em T(n)T(n) como funções de tempo de execução: positiva e crescente em função de nn.
  • Dizemos que "T(n)T(n) é O(g(n))O(g(n))" se g(n)g(n) cresce pelo menos tão rápido quanto T(n)T(n) conforme, nn cresce.

  • Mais formalmente

T(n)=O(g(n))T(n) =O(g(n)) se existem constantes positivas CC e n0n_0 tais que T(n)Cg(n)T(n)\leq C g(n) para todo nn0n\geq n_0;

A notação OO

  • Graficamente:

A notação OO

  • Graficamente:

A notação OO

  • Graficamente:

A notação OO

  • Graficamente:

A notação OO

  • Graficamente:

A notação OO

  • Para provar que T(n)=O(g(n))T(n) = O(g(n)), temos que mostrar que existe um cc e n0n_0 que satizfaz a definição.

  • Por exemplo, queremos provar que T(n)=10n2+5n+3T(n) = 10n^2+ 5n+ 3 and g(n)=n2g(n) = n^2. Podemos mostrar que T(n)=O(g(n))T(n) = O(g(n)) encontrando um cc e n0n_0 de acordo com a definição. Por exemplo:
    C=10n2+5n+3n2=10+5n+3n2C = \frac{10n^2+ 5n+ 3}{n^2} = 10 + \frac{5}{n} + \frac{3}{n^2}
    para n1n\geq 1 temos que
    10+5n+3n210+5+3=1810 + \frac{5}{n} + \frac{3}{n^2} \leq 10 + 5 + 3 = 18

  • Basta tomar n0=1n_0=1 e C=18C=18, e temos que T(n)=O(g(n))T(n) = O(g(n))

A notação Ω\Omega

  • A notação Ω\Omega (big-Ω\Omega) é uma notação matemática para considerar o limite inferior para o crescimento de uma função
    • Informalmente, ela pode ser obtida ignorando-se as constantes e termos que não dominam o crescimento da função

A notação Ω\Omega

  • Seja T(n)T(n) e g(n)g(n) funções sobre inteiros positivos.

  • Dizemos que "T(n)T(n) é Ω(g(n))\Omega(g(n))" se g(n)g(n) cresce no máximo tão rápido quanto T(n)T(n) conforme, nn cresce.

  • Mais formalmente

T(n)=Ω(g(n))T(n) = \Omega(g(n)) se existem constantes positivas cc e n0n_0 tais que cg(n)T(n)c g(n)\leq T(n) para todo nn0n\geq n_0;

A notação Ω\Omega

  • Graficamente:

A notação Ω\Omega

  • Similarmente, podemos provar que T(n)=Ω(g(n))T(n) = \Omega(g(n)), temos que mostrar que existe um cc e n0n_0 que satizfaz a definição.

  • Por exemplo, queremos provar que T(n)=10n2+5n+3T(n) = 10n^2+ 5n+ 3 and g(n)=n2g(n) = n^2. Podemos mostrar que T(n)=Ω(g(n))T(n) = \Omega(g(n)) encontrando um cc e n0n_0 de acordo com a definição. Por exemplo:

    c10+5n+3n2c \leq 10 + \frac{5}{n} + \frac{3}{n^2}

para n1n\geq 1 temos que

10+5n+3n21010 + \frac{5}{n} + \frac{3}{n^2} \geq 10

Basta tomar n0=1n_0=1 e c=10c=10, que T(n)=Ω(g(n))T(n) = \Omega(g(n))

A notação Θ\Theta

  • Dizemos que T(n)=Θ(g(n))T(n) = \Theta(g(n)) se, e somente se:

    • T(n)=O(g(n))T(n) = O(g(n)) e
    • T(n)=Ω(g(n))T(n) = \Omega(g(n))
  • T(n)=10n2+5n+3=Θ(n2)T(n) = 10n^2+ 5n+ 3 = \Theta (n^2) pois, como vimos anteriormente, T(n)=10n2+5n+3=O(n2)T(n) = 10n^2+ 5n+ 3 = O (n^2) e T(n)=10n2+5n+3=Ω(n2)T(n) = 10n^2+ 5n+ 3 = \Omega (n^2)

Propriedades da notação assintótica

  • Sejam f(n)f(n), g(n)g(n) e h(n)h(n) funcoes positivas. Temos que:
  1. f(n)=Θ(f(n))f(n) = \Theta(f(n));
  2. f(n)=Θ(g(n))f(n) = \Theta(g(n)) se e somente se g(n)=Θ(f(n))g(n) = \Theta(f(n));
  3. f(n)=O(g(n))f(n) = O(g(n)) se e somente se g(n)=Ω(f(n))g(n) = \Omega(f(n));
  4. Se f(n)=O(g(n))f(n)=O(g(n)) e g(n)=Ω(h(n))g(n) = \Omega(h(n)), então f(n)=O(h(n))f(n) =O(h(n)); O mesmo vale substituindo OO por Ω\Omega;
  5. Se f(n)=Θ(g(n))f(n) = Θ(g(n)) e g(n)=O(h(n))g(n) =O(h(n)), entao f(n)=O(h(n))f(n) =O(h(n)); O mesmo vale substituindo OO por Ω\Omega;
  6. f(n)=O(g(n)+h(n))f(n) =O(g(n) +h(n)) se e somente se f(n)=O(g(n))+O(h(n))f(n) =O(g(n)) +O(h(n)); O mesmo vale substituindo OO por Ω\Omega ou por Θ\Theta;
  7. Se f(n)=O(g(n))f(n) =O(g(n)) e g(n)=O(h(n))g(n) =O(h(n)), entao f(n)=O(h(n))f(n) =O(h(n)); O mesmo vale substituindo OO por Ω\Omega ou por Θ\Theta.

Complexidade do InsertionSort

  • A complexidade do InstertionSort é:
Melhor caso Caso médio Pior caso
Θ(n)\Theta(n) Θ(n2)\Theta(n^2) Θ(n2)\Theta(n^2)

Complexidade do InsertionSort

  • Relembre que, no melhor caso
    T(n)=5n3T(n) = 5n -3

  • De acordo com as propriedades 1 e 2, temos que:

T(n)=5n3=Θ(n)T(n) = 5n -3 = \Theta(n)

Complexidade do InsertionSort

  • Relembre que, no pior caso
    T(n)=n2+2n6T(n) = n^2 + 2n - 6
  • Podemos provar como fizemos anteriormente (encontrar cc e n0n_0), mas obserse que, para qualquer T(n)T(n) na forma:
    T(n)=an2+bn+cT(n) = an^2 + bn + c
    se tomarmos n0=1n_0=1 e notar que para todo nn0n \geq n_0 temos que
    an2an2+bn+c(a+b+c)n2an^2\leq an^2 + bn + c\leq (a+b+c)n^2
    escolhendo c=ac=a e C=a+b+cC=a+b+c na definição de OO e Ω\Omega (por consequencia Θ\Theta), temos que
    T(n)=n2+2n6=Θ(n2)T(n) = n^2 + 2n - 6 = \Theta(n^2)

Função assintótica de polinômios

  • Com uma análise similiar, podemos mostrar que para qualquer polinômio
    T(n)=i=1kainiT(n) = \sum_{i=1}^k a^i n^i
    em que aia_i é uma constante para i1..ki \in 1..k, e ak>0a_k > 0, temos que

T(n)=Θ(ak)T(n) = \Theta(a^k)

Complexidade do InsertionSort

  • Relembre que, no caso médio
    T(n)=2n+n(n1)4=n24+7n4T(n) = 2n + \frac{n(n-1)}{4} = \frac{n^2}{4} + \frac{7n}{4}
    que é similar ao caso anterior, portanto
    T(n)=2n+n(n1)4=Θ(n2)T(n) = 2n + \frac{n(n-1)}{4} = \Theta(n^2)

Complexidade do InsertionSort

  • Na prática, como estamos interessados no comportamento assintótico, não precisamos fazer uma análise tão cuidadosa como a que fizemos no início da aula.
    • Por exemplo, não precisamos contar as linas 2,3,7 e 5,6, pois "o que importa" é número de repetições do laço
  • Essa é uma das vantagens de se utilizar notação assintótica para estimar os recursos de um algoritmo

Complexidade

  • Em geral, quando falamos da complexidade de um algoritmo, estamos interessados no pior caso
    • nem sempre é fácil definir um "caso médio"
  • Qual é o limite superior do pior caso desse algoritmo?

Complexidade do InsertionSort

  • É possível fazer melhor?
    • Sim, mas veremos nas próximas aulas 😃