Lesson07

Algoritmo

Um algoritmo é um procedimento bem definido que aceita uma dada entrada e produz uma dada saída, num número finito de passos.

Dado um problema, um algoritmo é correcto se e só se devolver a saída correcta para qualquer instância desse problema.

Exemplos de problemas:

1. calcular a média de um conjunto de valores;
2. ordenação de sequências de valores;
3. caminhos mais curtos em grafos dirigidos.

A complexidade de um algoritmo defini-se em termos do tempo e do espaço necessários para resolver as instâncias de um dado problema em função do tamanho dessas mesmas instâncias. A complexidade de um problema define-se como a menor complexidade de um algoritmo correcto para o mesmo.

Problema: mudar maiúsculas para minúsculas

Entrada: vector de caracteres com o texto.
Objectivo: mudar todas as letras maiúsculas do texto de entrada para as respectivas letras minúsculas.
Saída: vector de entrada alterado.

Algoritmo 1 (em C):

void lower(char s[]) 
{
  int i;

  for (i=0; i < strlen(s); i++)
    if (s[i] >= ’A’ && s[i] <= ’Z’)
      s[i] -= (’A’ -’a’);
}

Tempo de execução aproximado para um dado vector de caracteres: 14.88s

Algoritmo 2 (em C):

void lower(char s[])
{
  int i, len = strlen(s);

  for (i=0; i < len; i++)
    if (s[i] >= ’A’ && s[i] <= ’Z’)
      s[i] -= (’A’ -’a’);
}

Tempo de execução aproximado para um mesmo vector de caracteres: 0.14s

Análise de algoritmos

Como aferir a complexidade um algoritmo? Como comparar dois algoritmos diferentes?

• Medidas de complexidade: tempo (tempo de execução); espaço (memória).
• Notação assimptótica.

Notamos que mudança de operações realizadas em tempo constante não é relevante, a complexidade da solução algorítmica mantém-se. Em geral queremos saber qual é o número de "passos básicos" requeridos pelo algoritmo em função do tamanho da instância do problema, em que por "passo básico" é um passo do algoritmo que toma tempo constante e que, portanto, não depende da instância do problema.

Tanto o tempo como o espaço dependem do tamanho da entrada e, por outro lado, a entrada depende do problema que o algoritmo pretende resolver. No problema de mudar os caracteres de maiúsculas para minúsculas, o número de caracteres da string de entrada é uma medida razoável. Nos algoritmos de ordenação, uma medida razoável é o número de elementos a ordenar. Num grafo as medidas utilizadas são o número de vértices e o de arcos.

A análise de algoritmos consiste portanto em encontrar uma relação matemática que dependa do tamanho da instância do problema e que descreva do ponto de vista assimptótico a complexidade do algoritmo. Neste sentido podemos considerar vários casos na análise:

1. pior caso, que representa um limite superior/inferior no tempo de execução e que ocorre numerosas vezes, sendo em geral fácil de calcular.
2. melhor caso, fácil de calcular em geral, mas que não contribui com muita informação;
3. caso médio, muitas vezes próximo do pior caso, é em geral importante em algoritmos probabilísticos e depende do conhecimento da distribuição das instâncias do problema em estudo, sendo em geral difícil de calcular.

Crescimento de funções

Parâmetro primário: N

• Traduz a dimensão de um problema.
• Geralmente corresponde ao número de elementos do conjunto de dados de um problema.
• Exemplos: dimensão de uma matriz, tamanho de um ficheiro, número de caracteres de uma string.

É usual analisar o tempo de execução dos algoritmos em função de um único parâmetro.

• Exemplo: "o tempo de execução da multiplicação de duas matrizes de dimensão $N\times N$ é da ordem de $N^3$".
• Pode também analisar-se a memória consumida, bem como outras métricas.

Tempos de execução típicos:

Comparação:

Comparação $N=10$:

No Algoritmo 1 acima para o problema de transformar maiúsculas em minúsculas temos:

1  void lower(char *s) 
2  {
3    int i;
4  
5    for (i=0; i < strlen(s); i++)
6      if (s[i] >= ’A’ && s[i] <= ’Z’)
7        s[i] -= (’A’ -’a’);
8  }

Se $N$ for o número de caracteres da string de entrada temos que:

• na linha 5, strlen(s) é uma operação que percorre os $N$ caracteres;
• a linha 5 é executada $N$ vezes;
• logo, o algoritmo é quadrático, $N^2$, no tamanho da string.

No Algoritmo 2:

1  void lower(char s[])
2  {
3    int i, len = strlen(s);
4  
5    for (i=0; i < len; i++)
6      if (s[i] >= ’A’ && s[i] <= ’Z’)
7        s[i] -= (’A’ -’a’);
8  }

Se $N$ for novamente o número de caracteres da string de entrada temos que:

• a pperação strlen(s) é executada apenas 1 vez (linha 3);
• o ciclo for tem $N$ iterações;
• as perações do ciclo for são limitadas e cada uma é executada em tempo constante, ou seja, não depende da dimensão dos dados;
• logo, o algoritmo é linear, $N$, no tamanho da string.

Notação assimptótica

Objectivo: caracterizar matematicamente os tempos de execução dos algoritmos para tamanhos arbitrários das entradas.

A notação assimptótica permite-nos estabelecer taxas de crescimento dos tempo de execução dos algoritmos em função dos tamanhos das entradas, sendo em geral útil apenas para valores de tamanho das entradas elevados. Para valores pequenos até algoritmos pouco eficientes correm em tempo razoável. As constantes multiplicativas e aditivas tornam-se neste tipo de análise irrelevantes, ou seja, o tempo de execução de cada instrução não é essencial para o comportamento assimptótico de um algoritmo.

Limite assimptótico superior

$O(g) = \{f\ |\ \exists c \ \exists n_0\ \forall n\geq n_0\quad 0 \leq f(n) \leq c g(n)\}$

Permite aferir a complexidade no pior caso. Quando $f\in O(g)$, escrevemos em geral $f=O(g)$, ou $f(n)=O(g(n)$ uma vez que no caso da análise de algoritmos estamos a falar de funções sobre os naturais, i.e., $f,g:I\!\!N\rightarrow I\!\!R$.

Exemplo: $f (n) = 0.1 n^3 + 1000 n^2 + 2.5 * 10^9$

• $f(n) = O(n^\alpha)$, para $\alpha \geq 3$;
• $f(n) = O(\varphi^n)$, para $\varphi \geq 1$;
• $f(n) \neq O(n^\alpha)$, para $\alpha < 3$.

Limite assimptótico inferior

$\Omega(g) = \{f\ |\ \exists c \ \exists n_0\ \forall n\geq n_0\quad 0 \leq c g(n) \leq f(n) \}$

Permite aferir a complexidade no melhor caso.

Limite assimptótico apertado

$\Theta(g) = \{f\ |\ \exists c_1\ \exists c_2 \ \exists n_0\ \forall n\geq n_0\quad 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \}$

Notar que $\Theta(g) = O(g)\cap \Omega(g)$, i.e., $f(n)=\Theta(g(n))$ se e só se $f(n)=O(g(n))$ e $f(n)=\Omega(g(n))$.

Exemplo: Procura em vector ordenado

Em geral, num vector não ordenado, a procura de um elemento é realizada sequencialmente percorrendo todo o vector até encontrarmos o elemento. No pior caso, o vector é analisado até ao fim e, portanto, a complexidade é $O(n)$, em que $n$ é a dimensão do vector. Ou seja a procura é feita em tempo linear no pior caso. No melhor caso, a primeira posição do vector é o elemento que procuramos e, portanto, temos complexidade constante no melhor caso, i.e., $O(1)$. Em resumo, o limite assimptótico superior é $O(n)$ e o limite assimptótico inferior é $\Omega(1)$.

No caso em que o vector está ordenado conseguimos resolver o problema de forma mais eficiente através de pesquisa binária:

1. comparar elemento a procurar com o elemento no meio do vector e:
   1. se os elementos são iguais, termina a procura;
   2. se o elemento a procurar é maior, procurar apenas na 2ª metade do vector;
   3. se o elemento a procurar é menor, procurar apenas na 1ª metade do vector. Temos portanto uma função recursiva que a cada passo divide a entrada a metade. Qual é complexidade deste algoritmo?

Podemos descrever o custo deste algoritmo com uma recorrência: $$T(n) = T(n/2) + O(1)$$

Para resolver estas recorrências podemos utilizar o master theorem (ver abaixo) ou podemos resolver por substituição. Seja $n=2^k$, caso em que

$$ T(2^k) = T(2^{k-1}) + c = T(2^{k-2}) + 2 c = T(2^{k-3}) + 3 c = ... = T(0) + k c = (k+1) c $$

ou seja, $T(2^k) = O(k)$ e, dado que $n=2^k$, $T(n) = O(\log n)$.

Exercício: Factorial

long fact (int n) {
  if (n > 1)
    return n*fact(n-1);
  else
    return 1;
}

Complexidade?

Mais exemplos? http://bigocheatsheet.com/ :-)

Master theorem

Seja $T(n)$ o tempo de execução de um algoritmo cobre uma entrada com tamanho $n$ tal que $$T(n) = a\ T\left(\frac{n}{b}\right) + f(n)$$ em que $a > 0$ e $b > 1$. Podemos determinar um limite superior apertado para $T(n)$ nos seguintes casos:

1. se $f(n) = O(n^\alpha)$, com $\alpha < \log_b a$, então $T(n) = \Theta(n^{\log_b a})$;
2. se $f(n) = \Theta(n^\alpha \log^k n)$, com $\alpha = \log_b a$ e $k\geq 0$, então $T(n) = \Theta(n^{\log_b a}\log^{k+1} n)$;
3. se $f(n) = \Omega(n^\alpha)$, com $\alpha > \log_b a$, e se $f$ satisfaz $a f(n/b)\leq c f(n)$, para algum $c<1$ e $n$ suficientemente grande, então $T(n) = \Theta(f(n))$.