MO417- Complexidade de Algoritmos I
Aula de 28/02/2003
Ata da Resolução de Exercícios

Livro Texto: ALGORITMOS - Teoria e Prática
Capítulo 2 - Conceitos Básicos
Redator: André Santanchè

Considere o problema de pesquisa:

Entrada: Uma seqüência de n números A = <a₁, a₂, ..., a_n> e um valor v.

Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não aparecer em A.

Escreva um pseudocódigo para pesquisa linear, que faça a varredura da seqüência, procurando por v {a}. Usando um loop invariante, prove que seu algoritmo é correto. Certifique-se de que seu loop invariante satisfaz às três propriedades necessárias {b}.

{a} Pseudocódigo
int busca_linear(int ve[], int n, int v)
{
  for (int i = 0; i < n; i++)
  {
    if (ve[i] == v) return i;
  }
  return NULL;
}

{b}

Considere a ordenação de n números armazenados no arranjo A, localizando primeiro o menor elemento de A e permutando esse elemento com o elemento contido em A[1]. Em seguida, encontre o segundo menor elemento de A e o troque pelo elemento A[2]. Continue dessa maneira para os primeiros n-1 elementos de A. Escreva o pseudocódigo para esse algoritmo, conhecido como ordenação por seleção {a}. Que loop invariante esse algoritmo mantém? {b} Por que ele só precisa ser executado para os n-1 elementos, e não para todos os n elementos? {c} Forneça os tempos de execução do melhor caso e do pior caso da ordenação por seleção em notação {d}.
 

{a} Pseudocódigo
for i = 1 to length[A] - 1
  menor = i
  for j = i+1 to length[A]
    if A[menor] > A[j]
      menor = j
  tmp = A[i]
  A[i] = A[menor]
  A[menor] = tmp

{b}

{c} Porque trata-se de um algoritmo baseado na comparação de um elemento chave com seus vizinhos de modo que se possa selecionar o menor elemento do subconjunto em questão e se realizar uma troca. Quando resta apenas um último elemento a ser ordenado, já não há mais outros elementos com os quais comparar, além disto, este último elemento já ocupa a sua posição correta na ordenação de maior elemento.

{d} (n²) tanto no melhor quanto no pior caso.

Descreva um algoritmo de tempo (n lg n) que, dado um conjunto S de n inteiros e outro inteiro x, determine se existem ou não dois elementos em S cuja soma seja exatamente x.

soma_igual(S, x, existem)
  merge_sort(S)
  existem = false
  esquerda = 1
  direita = length[S]
  while esquerda < direita and S[esquerda]+S[direita] <> x
    if S[esquerda]+S[direita] > x
      direita = direita - 1
    else
      esquerda = esquerda + 1
  if esquerda < direita
    existem = true

Explicação:
O princípio de funcionamento deste algoritmo pode ser entendido da seguinte maneira:

1. Inicialmente realiza-se uma classificação (merge_sort) no vetor com tempo Theta(n lg n).
2. Em seguida fixam-se dois índices: esquerda e direita. O da esquerda estará inicialmente na primeira posição apontando, deste modo, o menor elemento do vetor, o da direita estará inicialmente na última posição apontando, deste modo, o maior elemento do vetor.

Toda vez que nos referirmos nas próximas etapas ao sub-vetor S[e..d], estaremos indicando apenas o segmento do vetor S que inicia na posição indexada por esquerda e termina na posição indexada por direita.
3. Se a soma do elemento S[esquerda] (menor) com o elemento S[direita] (maior) for:
• igual a x, os elementos procurados foram encontrados (existem).
• maior que x, significa que não existe nenhum elemento no sub-vetor S[e..d] que somado com o elemento da direita (maior) seja igual x, dado que ele (elemento da direita) foi somado ao menor elemento do no sub-vetor S[e..d] e mesmo assim ultrapassou x. Por este motivo o elemento da direita sai do sub-vetor S[e..d] (índice da direita segue para o elemento anterior).
• menor que o x, significa que não existe nenhum elemento no sub-vetor S[e..d] que somado com o elemento da esquerda (menor) possa alcançar x, dado que ele (elemento da esquerda) foi somado ao maior elemento do sub-vetor S[e..d] e mesmo assim não alcançou x. Por este motivo o elemento da esquerda sai do sub-vetor S[e..d] (índice da esquerda segue para o próximo elemento).
4. É intuitivo entender a validade deste processo quando o sub-vetor S[e..d] corresponde ao vetor completo, como acontece na primeira iteração. Mas precisamos provar que isto é verdadeiro para as demais iterações que tratam com subconjuntos de S.
5. Se levarmos em conta que a cada iteração um elemento sai do sub-vetor S[e..d] (através do deslocamento de esquerda ou direita) pois "não existe combinação possível com este elemento que alcance a soma procurada", concluiremos que no início de cada iteração possuímos um sub-vetor S[e..d] que mantém apenas "os elementos com os quais é possível se encontrar a soma procurada". Além disto, este sub-vetor se encontra em condições equivalentes ao vetor original, ou seja, é um vetor ordenado de números inteiros, o que nos permite repetir o passo 4 até encontrarmos os elementos que correspondem a soma procurada, ou até que reste um único elemento no sub-vetor S[e..d], o que indica que não existem os elementos procurados.
6. Como o tempo de execução das instruções após o merge_sort é O(n), o algoritmo completo será Theta(n lg n).