MC102MN

Na aula passada vimos como declarar e usar vetores de forma simples. Nessa aula vamos ver algumas operações mais complexas. Além de usar um vetor para guardar uma lista de valores, podemos usar para guardar um vetor mesmo (no sentido de álgebra linear).

Uma característica importante dos vetores de C é que eles não carregam internamente informação sobre o seu tamanho. Podemos fazer funções genéricas, que operam sobre vetores de qualquer tamanho, mas precisamos passar um inteiro para servir de limite.

Assim podemos definir operações úteis que operam sobre esse vetor, como produto interno:

double prod_interno(double v1[], double v2[], int n) {
  int i;
  double res = 0;
  for (i = 0; i < n; ++i)
    res += v1[i]*v2[i];
  return res;
}

ou adição de vetores

void soma_vet(double v1[], double v2[], double res[], int n) {
  int i;
  for (i = 0; i < n; ++i)
    res[i] = v1[i]+v2[i];
} 

Ou multiplicação de um vetor por uma constante (mas deixarei isso como exercício).

Nem todas as operações com vetores necessariamente passam apenas uma vez por cada elemento do vetor. Por exemplo, podemos definir a operação "minimo", que retorna o índice do menor valor entre dois elementos no vetor:

int minimo(int v[], int inf, int sup) {
  int i, mi = inf, mv = v[inf];
  for(i = inf; i < sup; ++i) {
     if (v[i] < mv) {
       mi = i;
       mv = v[i];
     }
  }
  return mi;
}

Com essa função, podemos definir um algoritmo de ordenação chamado de ordenação por seleção, que vai ordenar os elementos do vetor escolhendo sempre o menor elemento. Por exemplo:

void selection_sort(int v[], int n) {
  int i, tmp, m;
  for (i = 0; i < n-1; ++i) {
    m = minimo(v, i, n);
    tmp = v[m];
    v[m] = v[i];
    v[i] = tmp;
  }
}

Existem algoritmos de ordenação bem mais simples que esse, mas esse é fácil o suficiente de entender.

Uma boa pergunta que podemos fazer agora é quão rápidos são esses programas? Isso é chamado de complexidade computacional, e existe toda uma área da computação dedicada a calcular a complexidade de programas complicados e fazer programas mais complicados ainda que rodem rápido para resolver alguns problemas.

Para calcular a complexidade de um programa usamos a idéia de análise assintótica, que é jogar fora todos os termos de baixa ordem (constantes, termos de menor grau em um polinômio, etc) para manter o essencial. Dizemos que um algoritmo é linear no tamanho da entrada () se o termo de mais alta ordem da sua complexidade é uma constante multiplicada pelo tamanho da entrada. Podemos ver que os dois primeiros algoritmos dessa aula têm essa complexidade.

Dizemos que um algoritmo é quadrático se o número de operações que ele faz é proporcional ao quadrado do tamanho da entrada. Enquanto minimo é linear (roda em tempo aproximadamente igual a sup-inf), selection_sort é quadrático (já que seu tempo é mais ou menos ).

Nessa matéria não entraremos formalmente em questões de complexidade, mas posso pedir para vocês me dizerem se um algoritmo é mais rápido ou devagar que outro, e como torná-lo mais rápido.

Uma coisa que se faz o tempo todo com computadores é guardar informação neles, e depois tentar recuperar. Existem muitas técnicas e áreas inteiras da computação dedicadas a fazer buscas funcionarem de forma eficiente.

Um dos métodos mais simples possíveis é a busca linear de um elemento em um vetor. Eis um exemplo:

int busca(int vetor[], int n, int elem) {
  int i;
  for (i = 0; i < n; ++i) {
    if (vetor[i] == elem) {
      return i;
    }
  }
  return -1;
}

Essa função percorre todos os elementos do vetor e, ao encontrar um elemento com o valor igual a elem, retorna a posição desse elemento.

A princípio isso parece o mais rápido que pode ser feito, mas existe uma variação, apenas para vetores ordenados, chamada busca binária, que é muito mais rápida. Ela funciona de forma bem parecida com o exemplo de inverter funções:

int busca_binaria(int vetor[], int n, int elem) {
 int a = 0, b = n-1, m = (a+b)/2, v;
 while (a < b) {
   v = vetor[m];
   if (v == elem) {
     return m;
   } else if (v < elem) {
     b = m-1;
   } else { 
     a = m+1;
   }
   m = (a+b)/2;
  }
  // Aqui com certeza a == b
  if (vetor[a] == elem) 
    return a;
  return -1;
}

Intuitivamente, podemos ver que a busca binária funciona em tempo proporcional a log n. Para isso, perceba que a cada iteração do laço ela reduz o tamanho da parte do vetor para o qual ela está olhando pela metade. Então se originalmente o valor buscado poderia estar em n posições, a partir da segunda etapa ele só pode estar em n/2; depois da terceira em n/4, depois em n/8, etc. Então se n = 2^x, o número de passos é no máximo x até encontrar.