27 de janeiro de 2024
Como medir a eficiência de um algoritmo?
Algoritmos
Introdução
Um algoritmo é qualquer tipo de instrução que recebe uma amostra de entrada de dados (input), faz uma sequência de passo a passo e retorna um ou mais valores (output). Há algoritmos para incontáveis casos de uso: desde ordenação de listas, busca do melhor caminho em um GPS, e até mesmo para determinar a movimentação de um braço robótico em uma linha de montagem.
A velocidade de um algoritmo pode não fazer diferença em aplicações simples, principalmente quando está lidando com poucas entradas de dados. Porém, um algoritmo lento pode ser um pesadelo quando esse número de dados aumenta. E é justamente esse aspecto que é importante ao analisar um algoritmo. “O que acontece com o tempo de execução conforme o número de amostras aumenta?”
Não é necessário especificar o tempo exato de execução. Isso seria tão difícil quanto irrelevante. Cada computador têm uma velocidade de processamento diferente, e que até pode mudar dependendo de fatores externos, como a temperatura. Dessa forma, na prática, isso não importa.
Notação Assintótica BigO
A mais comum unidade de medida para o desempenho de um algoritmo é a notação BigO. Ela nos diz qual a ordem de grandeza que o tempo de execução ou memória requerida cresce em relação ao tamanho do input, em seu pior caso.
Como só nos interessa a ordem de grandeza, no caso de n³ + n² + 3n + 5 fica apenas n³, pois é o mais significante na equação. Constantes como o 5 são ignoradas por serem irrelevantes em grandes conjuntos de dados e os outros termos são menos dominantes no resultado que n³.
Crucial frisar que BigO é a análise no pior caso de execução. É uma unidade pessimista, podemos dizer assim. Por exemplo, se vamos achar BigO para um algoritmo que busca um específico valor em uma lista, percorrendo-a do começo ao fim, temos que imaginar o pior caso: o item estar no final. Para uma quantidade n de itens na lista, se o item está no final, o algoritmo teve que percorrer por todos os itens, ou seja, a ordem de grandeza é proporcional ao tamanho da lista n. Dizemos então que o tempo de execução do algoritmo é O(n).
Existem outras notações, como para o melhor caso (notação ômega) ou para o “caso intermediário” (notação theta), mas são menos utilizadas. E tem uma boa razão para usar BigO em detrimento a qualquer outra notação: se trabalhamos com o pior caso, temos certeza que pior que isso não fica. Então podemos ficar despreocupados com o “caso real” de execução.
Ordens de grandeza mais comuns
- O(1): Tempo constante. Demora sempre o mesmo tempo de execução, que pode não ser necessariamente 1 execução. Por exemplo: verificar se o primeiro elemento de uma lista é um valor específico, ou verificar se um número é ímpar ou par.
- O(log n): Tempo logaritmo. Geralmente um algoritmo que divide seu input recursivamente em duas partes, como a busca binária. É um tempo excelente de execução.
- O(n): Tempo linear. Quando é necessário iterar sobre uma lista. Por exemplo, a função “.map()” do JavaScript.
- O(n log n): Para cada item da lista, fazer uma divisão recursiva, mais uma operação final que "resolve" suas partes. É o caso do algoritmo Quicksort.
- O(n²): Tempo quadrático. Para cada item, reiterar sobre a lista, como o caso de dois laços ‘for’ aninhados. Um exemplo é o Bubblesort.
- O(2^n): Exponencial. Um tempo péssimo de execução. Por exemplo, o cálculo do número de Fibonacci.
- O(n!): Um dos piores casos que pode acontecer. Se o input for uma lista de 5 itens, haverá 5! operações (5 x 4 x 3 x 2 x 1). Essa ordem de grandeza está muito associada ao problema do caixeiro viajante.
Assim, podemos dizer que os tempos de execução, quando o número de inputs tende-se ao infinito é: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).
E, na prática?
Na prática, precisamos observar cada linha de execução do algoritmo e fazer os seguintes passos:
- Analisar a complexidade de tempo da linha. Ignore os tempos constantes.
- Se utilizar métodos de bibliotecas externas, ou até mesmo da própria linguagem de programação, procure saber qual o seu tempo de execução.
- Utilize o termo de maior grandeza.
Exemplo 1
Printar na tela cada item de um array:
1void print_array(int array[], int length) {
2 for (int i = 0; i < length; i++) { // O(n)
3 printf("%d ", array[i]); // O(1)
4 }
5}Percorrer todos os itens na segunda linha “custa” O(n). Enquanto printar um elemento de uma posição específica tem um tempo constante O(1). Ignoramos tempos constantes e temos o resultado O(n), um tempo linear, mediano.
Exemplo 2
Algoritmo InsertionSort para ordenar uma lista:
1int* insetion_sort(int numbers[], int length){
2 for (int i = 0; i < length; i++) // O(n)
3 {
4 int key = numbers[i]; // O(1)
5 int j = i - 1; // O(1)
6 while(j >= 0 && numbers[j] > key) { // O(n)
7 numbers[j + 1] = numbers[j]; // O(1)
8 j = j - 1; // O(1)
9 }
10 numbers[j + 1] = key; // O(1)
11}
12return numbers; // O(1)
13};Ao ignorar constantes, temos dois loops aninhados que iteram (em seu pior caso) sobre toda a lista:
1int* insetion_sort(int numbers[], int length){
2 for (int i = 0; i < length; i++) // O(n)
3 {
4 int key = numbers[i];
5 int j = i - 1;
6 while(j >= 0 && numbers[j] > key) { // O(n)
7 numbers[j + 1] = numbers[j];
8 j = j - 1;
9 }
10 numbers[j + 1] = key;
11}
12return numbers;
13};Como são duas iterações aninhadas, temos que multiplicar O(n) x O(n), que resulta em uma complexidade de tempo de O(n²) em seu pior caso. Não muito eficiente para grandes entradas de dados.
Exemplo 3
Algoritmo MergeSort, porém já vamos ignorar os tempos constantes.
1void *merge(int numbers[], int begin, int mid, int end)
2{
3 int left_size = mid - begin + 1;
4 int right_size = end - mid;
5
6 int left[left_size], right[right_size];
7
8 for (size_t i = 0; i < left_size; i++) // O(n)
9 {
10 left[i] = numbers[begin + i];
11 };
12
13 for (size_t i = 0; i < right_size; i++) // O(n)
14 {
15 right[i] = numbers[mid + i + 1];
16 };
17
18 int i = 0;
19 int j = 0;
20 int k = begin;
21
22 while (j < left_size && i < right_size) // O(n)
23 {
24 if (left[j] <= right[i])
25 {
26 numbers[k] = left[j];
27 j++;
28 }
29 else
30 {
31 numbers[k] = right[i];
32 i++;
33 }
34 k++;
35 }
36
37 while (j < left_size) // O(n)
38 {
39 numbers[k] = left[j];
40 j++;
41 k++;
42 }
43
44 while (i < right_size) // O(n)
45 {
46 numbers[k] = right[i];
47 i++;
48 k++;
49 }
50}
51
52void *merge_sort(int numbers[], int begin, int end)
53{
54 if (begin < end)
55 {
56 int mid = begin + (end - begin) / 2;
57 merge_sort(numbers, begin, mid); // O(n log n)
58 merge_sort(numbers, mid + 1, end); // O(n log n)
59
60 merge(numbers, begin, mid, end); // O(n)
61 }
62}Esse algoritmo usa a estratégia dividir e conquistar. No momento da divisão, cada metade do algoritmo é dividida recursivamente em 2, caracterizando um comportamento de O(log n) - com log de base 2, como comumente é usado na ciência da computação. Já na conquista (agrupamento), é sempre tomado um tempo linear O(n) e como isso faz parte da recursão, dizemos que MergeSort possui uma complexidade de tempo de O(n * log n). Isso é relativamente um excelente tempo de execução, ainda que em seu pior cenário de execução.
Em resumo
- Revise linha por linha para encontrar possíveis recursões sobre o input de dados. Tome cuidado com loops aninhados.
- Pesquise sobre os métodos da linguagem de programação e bibliotecas externas.
- Mantenha o termo de maior peso.
- Beba água.
Referência
Fonte da imagem: Big O Cheat Sheet – Time Complexity Chart (freecodecamp.org)