Análise de Algoritmos

Ronaldo Cristiano Prati

Bloco A, sala 513-2

ronaldo.prati@ufabc.edu.br

Exemplo 1

  • Considere que T(n)=3T(n/3)+1T(n)= 3T(n/3)+1 e queremos provar pelo método da substituição que ele é O(n)O(n)
  • Temo que provar que T(n)cnT(n) \leq cn para alguma constante positiva cc, por indução em nn
  • No passo indutivo, temos:
    T(n)=3T(n/3)+1cn+1\begin{aligned} T(n) &= 3T(n/3)+1 \\ & \leq cn +1 \end{aligned}
  • Entretanto, a nossa hipótese é que T(n)cnT(n) \leq cn, (e não cn+1cn+1, como obtivemos no passo indutivo)

Exemplo 1

  • Isso não significa em T(n)O(n)T(n) \neq O(n).
  • O problema é que a expressão que usamos para provar nosso palpite não foi "forte" o suficiente. Vamos tentar provar que T(n)cndT(n) \leq cn -d, que contina sendo O(n)O(n). No passo indutivo temos:

T(n)=3T(n/3)+13(cn3d)+1=cn3d+1cnd\begin{aligned} T(n) &=3 T(n / 3)+1 \\ & \leq 3\left(\frac{c n}{3}-d\right)+1 \\ &=c n-3 d+1 \\ & \leq c n-d \end{aligned}

  • No caso base tesmo que T(1)=1cdT(1)=1 \leq c-d sempre que cd+1c \geq d+1, portanto T(n)=O(cnd)=O(n)T(n)=O(c n-d)=O(n)

Exemplo 2

  • Considere que T(n)=T(n/2+2)+1T(n)=T(\lfloor n / 2\rfloor+ 2)+1 e queremos provar pelo método da substituição que ele é O(logn)O(\log n), assumindo o caso base T(4)=1T(4)=1

Exemplo 2

  • É possível provar T(n)clognT(n) \leq c \log n, que no passo indutivo fica
    T(n)=T(n/2+2)+1clog(n2+2)+1=clog(n+42)+1clog(3n/2)c+1=clognc(2log3)+1clogn\begin{aligned} T(n) &=T(\lfloor n / 2\rfloor+ 2)+1 \\ & \leq c \log \left(\frac{n}{2}+2\right)+1 \\ &=c \log \left(\frac{n+4}{2}\right)+1 \\ & \leq c \log (3 n / 2)-c+1 \\ &=c \log n-c(2-\log 3)+1 \\ & \leq c \log n \end{aligned}
  • em que a penúltima desigualdade vale para n>8n>8 e a última para c1/(2log3)c \geq 1 /(2-\log 3)

Exemplo 2

  • Entretanto, fortalecendo a hipótese indutiva para T(n)clog(na)T(n) \leq c \log (n-a), no passo indutivo temos
    T(n)=T(n/2+2)+1clog(n2+2a)+1=clog(na2)+1=clog(na)c+1clog(na)\begin{aligned} T(n) &=T(\lfloor n / 2\rfloor+ 2)+1 \\ & \leq c \log \left(\frac{n}{2}+2-a\right)+1 \\ &=c \log \left(\frac{n-a}{2}\right)+1 \\ &=c \log (n-a)-c+1 \\ & \leq c \log (n-a) \end{aligned}

  • em que a primeira desigualdade vale para a4a\geq 4 e a última para c1c \geq 1. Escolhendo a=4a=4, T(6)=T(5)+1=T(4)+2=3clog(64)T(6)=T(5)+1=T(4)+2=3 \leq c \log (6-4) para c3c\geq 3. Portanto, fazendo a=4a=4 e c3c\geq 3, temos que T(n) \leq c \log (n-a) para n6n\geq 6.

Fila de Prioridade

  • Em algumas situações associamos uma prioridade a cada item coleção, e gostaríamos de ter acesso rápido ao item de maior prioridade

  • É uma coleção dinâmica de elementos que possuem prioridades associadas e a operação de remoção deve sempre remover o elemento que possui maior prioridade.

  • O termo prioridade é genérico: ter maior prioridade não significa necessariamente o maior valor.

    • Atendimento a idoso em um banco: maior idade \rightarrow maior prioridade
    • Gerenciamento de estoque: menor quantidade de items \rightarrow maior prioridade

Fila de Prioridade

Operações

  • Constrói uma fila de prioridade a partir de um conjunto

  • Insere elemento na fila

  • Remove elemento com maior prioridade

  • Alteração da prioridade de um elemento

Vetores ordenados

  • Uma maneira de dar suporte a essas operações é usar um vetor ordenado

    • Contrução: O(nlogn)\mathcal{O}(n \log n),
    • Inserção/Alteração de prioridade: O(n)\mathcal{O}(n)
    • Remoção: O(1)\mathcal{O}(1)

Heap

  • Uma outra alternativa é usar Heaps

    • Construção: O(n)\mathcal{O}(n),
    • Inserção/Alteração de prioridade: O(logn)\mathcal{O}(\log n)
    • Remoção: O(logn)\mathcal{O}(\log n)

Heap

  • Heap pode ser entendida com uma árvore
    • quase completa:
      • Todos os níveis exceto o último devem estar totalmente preenchidos.
      • Se o seu último nível não estiver preenchido, os nós devem estar preenchidos da esquerda para a direita.
    • satisfaz a propriedade heap:
      • Um nó deve ter prioridade maior ou igual à prioridade de seus filhos, se eles existirem.

Heap

Heap

  • No entanto, heaps são normalmente implementadas em um vetor

  • Nesse caso, para uma determinada posição ii

    • pai(i)=i2pai(i) = \lfloor \frac{i}{2} \rfloor

    • filhoEsquerdo(i)=2ifilhoEsquerdo(i) = 2*i

    • filhoDireito(i)=2i+1filhoDireito(i) = 2*i + 1

    • (obs): i2\frac{i}{2} e 2i2*i podem ser implementados de maneira eficiente usando bit shifts

Heap

Heap

  • No caso de índice começando em zero, para uma determinada posição ii

    • pai(i)=i12pai(i) = \lfloor \frac{i-1}{2} \rfloor

    • filhoEsquerdo(i)=2i+1filhoEsquerdo(i) = 2*i + 1

    • filhoDireito(i)=2i+2filhoDireito(i) = 2*i + 2

Construção do Heap

  • Um vetor ordenado é pela priopridade é um Heap

  • Um problema é que ordenar o vetor tem custo de (pelo menos) O(nlogn)\mathcal{O}(n \log n)

  • No entanto, o vetor não precisa estar completamente ordenado... somente os caminhos da "raíz" (primeiro nível) até as "folhas" (último nível) é que precisa estar ordenado

Construção da HEAP

Corrige Heap Descendo

  • Suponha que um determinada subárvore cuja raíz é H[i]H[i] viola a propriedade heap (isto é, sua prioridade é menor que a de (pelo menos um) seus filhos)

  • Entretanto, as subárvores filhas H[2i]H[2i] e H[2i+1]H[2i+1] são heap.

  • Podemos corrigir a heap "descendo" o elmento H[i]H[i]:

    • Trocar H[i]H[i] com o filho de maior prioridade
    • Chamar recursivamente CorrigeDescendo para o filho trocado (pois a propriedade Heap pode continuar violada para ele)

Corrige Heap Descendo

  • Exemplos de CorrigeHeapDescendo(H,2)

Corrige Heap Descendo

Corretude: Corrige Heap Descendo

Seja hx=log(n/x)h_x = \lfloor \log(n/x) \rfloor a altura do nó que está na posição xx

  • Caso Base: hi=0h_i = 0 o nó é uma folha, portanto não tem filhos e a propriedade heap é válida
  • Hipótese: Se H[2k]H[2k] e H[2k+1]H[2k+1] são heaps, CorrigeHeapDescendo(H,kH,k) restaura a Heap para todo nó de altura hk<hih_k < h_i
    • Se H[i] tem prioridade maior que seus filhos, o algoritmo não faz nada pois a proriedade heap já é valida. Temos que mostrar por indução que CorrigeHeapDescendo(H,iH,i) está correto
    • Se a prioridade de H[i]H[i] é menor que um de (pelo menos um de) seus filhos, o algoritmo troca H[i]H[i] com o maior deles, e chama recursivamente CorrigeHeapDescendo(H,maiorH,maior). Como a altura do filho é menor que a do pai, pela Hipótese de indução, H[i]H[i] agora é uma haep.

Complexidade: Corrige Heap Descendo

  • CorrigeHeapDescendo(H,iH,i) tem um tempo proporcional a altura de ii, ou seja O(log(ni))O(\log (n-i)).

  • No pior caso, i é a raiz da árvore, então a complexidade é proporcianal a altura da árvore

  • Como a heap é uma árvore binária quase completa, sua altura é O(logn)O(\log n).

  • Portanto, a complexidade de CorrigeHeapDescendo é O(logn)O(\log n)

ConstroiHeap

  • Considere que temos um vetor qualquer (não heap), e queremos transformá-lo em uma heap

  • Podemos transformá-lo em uma haep utilizando CorrigeHeapDescendo como uma subrotina:

    • Observe que os nós folhas são heap (não tem filhos).
    • Podemos chamar CorrigeHeapDescendo para os nós não folha, começando pelo primeiro elemento não folha Hn/2H\lfloor n/2 \rfloor até o raíz H[1]H[1]

ConstroiHeap

ConstroiHeap

  • É fácil mostrar que ConstroiHeap funciona, já que ele faz suscessivas chamadas a CorrigeHeapDescendo

  • A invariante de laço é que a cada iteração do laço para indexado por ii, para todo jj tal que i+1jni+ 1\leq j\leq n , a ́arvore enraizada em H[j]H[j] e um heap.

  • Como CorrigeHeapDescendo é excutado Hn/2H\lfloor n/2 \rfloor até H[i]H[i], a invariante de laço se mantém e por indução podemos provar que ConstroiHeap constrói uma heap para qualquer vetor.

ConstroiHeap: Complexidade

  • Uma análise preliminar, podemos constantar que ConstroiHeap tem complexidade O(nlogn)O(n \log n), uma vez CorrigeHeapDescendo tem complexidade O(logn)O(\log n) e ele é executado n/2\lfloor n/2 \rfloor vezes, que é O(n)O(n)

  • Entretanto, observe que O(logn)O(\log n) é um limite superior para a complexidade de ConstroiHeap. Na verdade sua complexidade é proporcianal à algura do elemente ii, ou seja, O(log(ni))O(\log (n-i)).

  • Podemos usar esse fato para encontrar uma complexidade mais justa para o ConstroiHeap

ConstroiHeap: Complexidade

  • Uma estimativa quantidade de nós em uma dada altura hh da heap é n2h+1\lceil \frac{n}{2^{h+1}} \rceil.
  • Podemos escrever a complexidade do ConstroiHeap como:
    T(n)=h=0log(n)n2h+1×O(h)=O(n×h=0lg(n)h2h)=O(n×h=0h2h)\begin{aligned} T(n) &=\sum_{h=0}^{\log(n)}\left\lceil\frac{n}{2^{h+1}}\right\rceil \times O(h) \\ &=O\left(n \times \sum_{h=0}^{\lg (n)} \frac{h}{2^{h}}\right) \\ &=O\left(n \times \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right) \end{aligned}

ConstroiHeap: Complexidade

  • Observe que para i1i \geq 1, ((i+1)/2i+1)/(i/2i)<1\left((i+1) / 2^{i+1}\right) /\left(i / 2^{i}\right)<1 .

T(n)=O(n×h=0h2h)cn=O(n)\begin{aligned} T(n) &= O\left(n \times \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right)\\ & \leq cn \\ & = O(n) \end{aligned}

Remover item da heap

  • Uma outra operação da heap é a remoção do item de maior prioridade
  • Observe que o primeiro elmento da heap é o item de maior prioridade. Então acessá-lo é O(1)O(1)
  • Para a remoção, precisamos colocar outro elmento no lugar.
  • Uma alteração que mexe o mínimo possível na Heap é trocar o primeiro com o último elemento.
  • Podemos então usar CorrigeHeapDescendo(H,1H,1) para corrigir a heap

RemoveDaHeap

Complexidade e Corretude de RemoveDaHeap

  • Observe que RemoveDaHeap viola apenas a propriedade heap do nó raiz, já que o último elemento é uma folha e não mexemos em outras posições da heap.

    • CorrigeHeapDescendo(H,1H,1) restaura a propriedade heap, portanto RemoveDaHeap está correto
  • A complexidade é dominada por CorrigeHeapDescendo(H,1H,1), já que a troca é O(1)O(1). Portanto, a complexidade é O(logn)O(\log n)

Inserir elemento na heap

  • Caso haja espaço na heap, uma estratégia é inserir na primeira posição disponível
  • Obviamente, isso pode violar propriedade heap
  • No entanto, antes da inserção, a propriedade heap está mantida.
  • O procedimento CorrigeHeapSubindo pode ser usado para restaurar a priopridade heap

CorrigeHeapSubindo

  • Dada uma posição H(i)H(i), se a prioridade de H(i)H(i) é maior que a de seu pai, podemos trocar H(i)H(i) com o seu pai.
  • A propriedade heap das subárvores está restabelecida, mas eventualmente é preciso continuar subindo até chegar ao nó raiz.

CorrigeHeapSubindo

CorrigeHeapSubindo

Complexidade e Corretude do CorrigeHeapSubindo

  • Um argumento similar ao usado para CorrigeHeapDescendo pode ser usado para demonstrar por indução que CorrigeHeapSubindo está correto

  • De maneira similar, podemos mostrar que a complexidade de CorrigeHeapSubindo é O(nlogn)O(n \log n)

InserirNaHeap

Complexidade e Corretude de RemoveDaHeap

  • Observe que InserirNaHeap viola apenas a propriedade heap do último nó, já que não mexemos em outras posições da heap.

    • CorrigeHeapSubindo(H,1H,1) restaura a propriedade heap, portanto InserirNaHeap está correto
  • A complexidade é dominada por CorrigeHeapSubindo, já que a inserção é O(1)O(1). Portanto, a complexidade é O(logn)O(\log n)

Altera prioridade de um elemento

  • Para alterar a prioridade de um elemento, podemos usar CorrigeHeapSubindo ou CorrigeHeapDescendo, dependendo se a prioridade do elemento ii subiu ou desceu
    • Se a prioridade cresceu, chamar CorrigeHeapSubindo(H,iH,i)
    • Se a prioridade desceu, CorrigeHeapDescendo(H,iH,i)

AlteraHeap

Complexidade e Corretude de AlteraHeap

  • Como AlteraHeap é baseado em CorrigeHeapSubindo e CorrigeHeapDescendo, podemos concluir que ele está correto, e que a sua complexidade é O(logn)O( \log n)

Selection Sort

  • Uma estratégia simples para ordenar vetor é:

    • Percorrer o vetor e encontrar o máximo
    • Trocar o último elemento pelo máximo
    • Repetir o processo, considerando o vetor com tamanho n1n-1
  • Essa estratégia é conhecida como como Selecion Sort

Selection Sort

Selection Sort

Selection Sort

  • A análise de corretude do selecion sort é similar a do heap sort (veremos mais adiante), assumindo que o algoritmo que seleciona o máximo funciona

  • A complexidade é O(n2)O(n^2)

Heap Sort

  • Podemos usar uma Heap para ordenar um vetor

    • A ideia é construir uma Heap com o vetor, e trocar o último elemento com o primeiro, rafazendo-se a Heap com tamanho n1n-1

    • Repete-se esse processo até ter o vetor ordenado

Heap Sort

Heap Sort

Corretude do Heap Sort

  • Antes de cada iteração ii do laço para, temos que:

    • O subvetor A[i+1..n]A[i+1..n] contém os ni+1n-i+1 elmentos de AA em ordem crescente
    • O subvetor A[1..i]A[1..i] é uma heap
  • No início da iteração ii, HeapSort troca A[1]A[1] (que por definição é o maior elemento da Heap) com A[i]A[i], e diminui o tamanho da heap em 1. - A[i]A[i] é menor que os elementos A[i+1..n]A[i+1..n], portanto A[i..n]A[i..n] continua ordenado.

  • Sabemos que CorrigeHeapDescendo(A,1A,1), está correto. Portanto a propriedade se mantém, e podemos provar por indução que HeapSort está correto

Heap Sort

  • Heap Sort tem complexidade O(nlogn)O(n \log n) (cada chamada para refazer a heap tem custo O(logn)O(\log n), e é chamada nn vezes).

  • Além disso, também há o custo adicional de construir a heap O(n)\mathcal{O}(n).

  • A ordem original dos elementos iguais pode mudar, portanto ele não é estável