Introdução à Análise de Algoritmos

Análise de Algoritmos

Uma das principais preocupações que vamos ter em IAED (para passar os malfadados testes com time limit exceeded) é como reduzir o runtime do nosso programa. Durante esta secção, vamos procurar arranjar maneiras de defini-lo (usando notação assintótica) em função do tamanho do input que usamos. Ainda assim, e antes de começar com definições mais teóricas, podemos pensar em pontos fracos habituais de programas que podemos melhorar.

Observemos o trecho de código abaixo: temos duas funções que fazem exatamente o mesmo: transformam toda uma cadeia de caracteres na sua versão lower case. Diferem na condição de ciclo do seu loop. Na função de acima, strlen(s) é calculada em todas as iterações: sendo que a implementação da mesma consiste em iterar pela string até ao fim, podemos perceber como tal poderá levar a maiores tempos de execução da mesma. A função de baixa é inegavelmente mais eficiente (podem experimentar correr ambos os trechos localmente para testarem vocês mesmos), e a única diferença é guardar o comprimento da string numa variável, efetivamente eliminando cálculos desnecessários!

/* 17 segundos para percorrer 1 milhão de caracteres */
void lower(char s[]) {
    int i;
    for (i = 0; i < strlen(s); i++) { /* sempre a calular o tamanho da string */
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
    }
}

/* 0.01 segundos para percorrer 1 milhão de caracteres */
void lower(char s[]) {
    int i, len = strlen(s); /* tamanho definido no inicio da função */
    for (i = 0; i < len; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
    }
}

Crescimento de Funções

A complexidade de um algoritmo, seja ela temporal ou espacial, está associada a um crescimento da função que a define (em função do seu input). As funções de crescimento com que mais tipicamente nos vamos deparar serão:

$1$ - O número de instruções de um programa/o espaço ocupado por um programa é um número constante e/ou limitado.

$\log{n}$ - O número de instruções de um programa/o espaço ocupado por um programa é logarítmico: dividimos continuamente o input ao meio (como na pesquisa binária, por exemplo).

$n$ - O número de instruções de um programa/o espaço ocupado por um programa é linear: existe algum tipo de processamento para cada elemento de entrada.

$n\log{n}$ - O número de instruções de um programa/o espaço ocupado por um programa está associado, tipicamente, à resolução de um conjunto de sub-problemas. As sub-soluções são por norma posteriormente combinadas (temos o exemplo do merge sort, que vamos abordar no futuro, como exemplo clássico).

$n^2$ - O número de instruções de um programa/o espaço ocupado por um programa é quadrático. Quando a dimensão da entrada duplica, o tempo aumenta em 4 vezes.

$2^n$ - O número de instruções de um programa/o espaço ocupado por um programa é exponencial. Quando a dimensão da entrada duplica, o tempo aumenta para o quadrado!

Pegando novamente no exemplo indicado mais acima, podemos finalmente perceber (em termos mais formais) o que está a acontecer: o trecho de cima tem complexidade temporal quadrática, já que strlen(s), uma operação linear, é executada uma vez por cada iteração do for, linear também. O trecho de baixo é, claro, linear!

/* 17 segundos para percorrer 1 milhão de caracteres */
void lower(char s[]) {
    int i;
    for (i = 0; i < strlen(s); i++) { /* sempre a calular o tamanho da string */
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
    }
}

/* 0.01 segundos para percorrer 1 milhão de caracteres */
void lower(char s[]) {
    int i, len = strlen(s); /* tamanho definido no inicio da função */
    for (i = 0; i < len; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= ('A' - 'a');
        }
    }
}

Notação Assimptótica

A notação assimptótica permite estabelecer taxas de crescimento dos tempo de execução dos algoritmos em função dos tamanhos das entradas (input). Aqui, as constantes multiplicativas e aditivas são irrelevantes: tanto um algoritmo que leva $n$ a correr como um que leva $4n$ a correr são lineares - perde-se o rigor, mas este acaba por não ser relevante para determinar o comportamento assimptótico do algoritmo.

• A notação $O$ (Ó grande) corresponde ao limite assimptótico superior. Permite aferir a complexidade no pior caso.
• A notação $\Omega$ (Ómega) corresponde ao limite assimptótico inferior. Permite aferir a complexidade no melhor caso.
• A notação $\Theta$ (Téta) corresponde ao limite assimptótico apertado. Corresponde às situações em que os melhor e pior casos têm a mesma complexidade.

Transpondo estas definições para exemplos práticos, podemos pensar nos problemas de pesquisa de elementos num vetor vs imprimir todos os valores presentes num vetor.

O primeiro problema tem melhor caso $1$, constante, caso o valor a procurar se encontre logo na primeira posição/o vetor esteja vazio: $\Omega(1)$. Tem, por outro lado, $O(n)$ como pior caso, já que pode ser preciso percorrer o vetor todo para o fazer. O segundo problema, contudo, tem melhor e pior casos com igual número de operações, linear: não podemos imprimir todos os valores de um vetor sem o percorrer completamente, $\Theta(n)$.