C# - Notação Big O

Falaremos hoje da notação "Big O", ela não é exclusiva do C#, muito pelo contrário, pode e deve ser aplicado a qualquer tipo de algoritmo, mas como nossos exemplos serão com essa linguagem o classificamos dessa forma.

A notação big O é usada na análise de algoritmos para descrever a complexidade de um algoritmo. A ideia é fornecer uma maneira de comparar algoritmos permitindo que os desenvolvedores escolham o mais eficiente. É uma forma de descrever o limite superior da complexidade de tempo ou espaço de um algoritmo em relação ao tamanho da entrada.

A notação big O é denotada por "O(f(n))", onde "f(n)" é uma função que descreve o comportamento do algoritmo. A função "f(n)" geralmente é uma expressão matemática que envolve a entrada "n" (por exemplo, "n^2" ou "2^n").

Se o tempo de execução de um algoritmo é proporcional ao quadrado do tamanho da entrada, podemos dizer que sua complexidade de tempo é O(n^2). Isso significa que, à medida que o tamanho da entrada aumenta, o tempo de execução do algoritmo aumenta proporcionalmente ao quadrado do tamanho da entrada.

O(1)

Indica que a complexidade do algoritmo não varia com o tamanho da entrada. Isso ocorre quando o tempo de execução é constante, independentemente do tamanho da entrada. Por exemplo, acessar um elemento de uma matriz em C# é uma operação O(1).

Um exemplo comum de algoritmo com complexidade O(1) em C# é o acesso a um elemento de um array. Isso ocorre porque, em um array, cada elemento ocupa um espaço de memória contíguo e pode ser acessado diretamente através do seu índice.

  
    int[] myArray = {1, 2, 3, 4, 5}; // declaração e inicialização de um array
    int element = myArray[2]; // acesso ao terceiro elemento do array
    Console.WriteLine(element); // exibe o valor do terceiro elemento (3) no console    
  

Neste exemplo, o acesso ao terceiro elemento do array é feito diretamente através do seu índice (2). Independentemente do tamanho do array, a operação de acesso a um elemento é executada em tempo constante, o que significa que o algoritmo tem complexidade O(1).

O(n)

Significa que o tempo de execução do algoritmo aumenta linearmente com o tamanho da entrada. Por exemplo, percorrer uma lista encadeada em C# tem complexidade O(n).

Um exemplo comum de algoritmo com complexidade O(n) em C# é o loop "for". Isso ocorre porque o tempo de execução do loop é proporcional ao número de iterações que ele realiza, o que é diretamente proporcional ao tamanho da entrada:

  
    int[] myArray = {1, 2, 3, 4, 5}; // declaração e inicialização de um array
    for (int i = 0; i < myArray.Length; i++) // loop para percorrer todos os elementos do array
    {
        Console.WriteLine(myArray[i]); // exibe cada elemento no console
    }    
  

No exemplo, o loop "for" é executado para cada elemento do array, o que significa que o tempo de execução do loop aumenta linearmente com o tamanho da entrada (tamanho do array). Portanto, o algoritmo tem complexidade O(n).

Observe que, embora a operação de acesso a um elemento do array seja uma operação O(1), a execução do loop "for" faz com que a complexidade do algoritmo seja O(n), uma vez que o loop percorre todos os elementos do array.

O(n^2)

Diz que o tempo de execução do algoritmo aumenta quadráticamente com o tamanho da entrada. Por exemplo, percorrer uma matriz bidimensional em C# tem complexidade O(n^2).

Um exemplo comum de algoritmo com complexidade O(n^2) em C# é um loop "for" aninhado. Isso ocorre quando um loop "for" é executado dentro de outro loop "for", fazendo com que o tempo de execução aumente quadráticamente com o tamanho da entrada.

  
    int[,] myMatrix = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; // declaração e inicialização de uma matriz
    for (int i = 0; i < myMatrix.GetLength(0); i++) // loop para percorrer as linhas da matriz
    {
        for (int j = 0; j < myMatrix.GetLength(1); j++) // loop para percorrer as colunas da matriz
        {
            Console.WriteLine(myMatrix[i, j]); // exibe cada elemento da matriz no console
        }
    }    
  

No exemplo anterior, há dois loops "for" aninhados que percorrem todos os elementos de uma matriz. O primeiro loop percorre as linhas da matriz e o segundo loop percorre as colunas. Como cada elemento da matriz é visitado uma vez para cada linha e coluna, a complexidade do algoritmo é O(n^2).

Observe que, embora a operação de acesso a um elemento da matriz seja uma operação O(1), a execução dos loops aninhados faz com que a complexidade do algoritmo seja O(n^2), uma vez que o número de operações necessárias cresce quadráticamente com o tamanho da entrada.

O(log n)

Aqui sabemos que o tempo de execução do algoritmo aumenta de forma logarítmica com o tamanho da entrada. Por exemplo, pesquisar em uma árvore binária em C# tem complexidade O(log n).

Um exemplo comum de algoritmo com complexidade O(log n) em C# é a busca binária em uma estrutura de dados ordenada, como um array ou uma árvore de busca binária. Isso ocorre porque a busca binária é um algoritmo que divide o conjunto de dados pela metade a cada iteração, reduzindo drasticamente o número de elementos a serem verificados em cada passo.

  
    int[] myArray = {1, 3, 5, 7, 9}; // declaração e inicialização de um array ordenado
    int target = 7; // valor que deseja-se buscar no array
    int min = 0; // índice do primeiro elemento do array
    int max = myArray.Length - 1; // índice do último elemento do array
    while (min <= max) // loop para buscar o elemento no array
    {
        int mid = (min + max) / 2; // índice do elemento central do array
        
        if (myArray[mid] == target) // se o elemento central for igual ao valor buscado, retorna o índice
        {
            return mid;
        }
        else if (myArray[mid] < target) // se o elemento central for menor que o valor buscado, atualiza o índice mínimo
        {
            min = mid + 1;
        }
        else // se o elemento central for maior que o valor buscado, atualiza o índice máximo
        {
            max = mid - 1;
        }
    }
    return -1; // valor não encontrado no array    
  

Neste exemplo, a busca binária é realizada em um array ordenado. O algoritmo divide o array pela metade a cada iteração, reduzindo o número de elementos a serem verificados pela metade em cada passo. Como o número de iterações necessárias para encontrar o valor buscado é proporcional a log2(n), onde n é o tamanho do array, a complexidade do algoritmo é O(log n).

Observe que a operação de acesso a um elemento do array é uma operação O(1), mas o número de acessos necessários para encontrar o valor buscado é reduzido pela metade a cada iteração, fazendo com que a complexidade do algoritmo seja O(log n).

O(n log n)

Já essa notação indica que o tempo de execução do algoritmo aumenta de forma logarítmica com o tamanho da entrada, mas também é multiplicado pelo tamanho da entrada. Por exemplo, ordenar uma lista em C# usando o algoritmo Merge Sort tem complexidade O(n log n).

Um exemplo comum de algoritmo com complexidade O(n log n) em C# é o algoritmo de ordenação Merge Sort. Isso ocorre porque o Merge Sort é um algoritmo de divisão e conquista que divide repetidamente uma lista em duas metades iguais, classifica as duas metades recursivamente e, em seguida, mescla as duas listas classificadas.

  
    public static void MergeSort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;
            MergeSort(array, left, mid);
            MergeSort(array, mid + 1, right);
            Merge(array, left, mid, right);
        }
    }
    
    public static void Merge(int[] array, int left, int mid, int right)
    {
        int[] temp = new int[array.Length];
        int i, j, k;
    
        i = left;
        j = mid + 1;
        k = left;
    
        while (i <= mid && j <= right)
        {
            if (array[i] <= array[j])
            {
                temp[k] = array[i];
                i++;
            }
            else
            {
                temp[k] = array[j];
                j++;
            }
            k++;
        }
    
        while (i <= mid)
        {
            temp[k] = array[i];
            i++;
            k++;
        }
    
        while (j <= right)
        {
            temp[k] = array[j];
            j++;
            k++;
        }
    
        for (int x = left; x <= right; x++)
        {
            array[x] = temp[x];
        }
    }    
  

Neste exemplo, o Merge Sort é implementado como uma função recursiva que divide a lista pela metade e, em seguida, chama a função recursivamente para classificar as duas metades. A lista é mesclada usando uma função auxiliar "Merge" que mescla duas listas classificadas em uma lista classificada única. Como o Merge Sort divide a lista em duas metades iguais a cada iteração e realiza um Merge de duas listas classificadas em cada iteração, a complexidade do algoritmo é O(n log n).

Observe que a operação de acesso a um elemento do array é uma operação O(1), mas o número de operações necessárias para classificar o array aumenta proporcionalmente a n log(n), onde n é o tamanho do array, fazendo com que a complexidade do algoritmo seja O(n log n).

Comparações

Fizemos uma pequena aplicação para demonstrar os resultados (que pode ser encontrada aqui) e o resultado foi o seguinte:

  
    | Method |          Mean |       Error |        StdDev |        Median |   Gen0 | Allocated |
    |------- |--------------:|------------:|--------------:|--------------:|-------:|----------:|
    |     O1 |     0.6339 ns |   0.0478 ns |     0.0976 ns |     0.6100 ns |      - |         - |
    |     On |    23.2548 ns |   0.5029 ns |     0.9569 ns |    23.2540 ns |      - |         - |
    |    On2 |    98.2505 ns |   4.8567 ns |    13.6188 ns |    93.5666 ns | 0.0381 |      80 B |
    |  OlogN |    14.0612 ns |   0.7780 ns |     2.2447 ns |    13.5068 ns | 0.0229 |      48 B |
    | OnLogN | 4,211.1712 ns | 341.2722 ns | 1,006.2488 ns | 4,359.2834 ns | 3.0518 |    6384 B |
  

O mais rápido é o "O(1)" já que ele acessa de forma direta o que estamos buscando, "O(n)" aqui executou rapidamente porém se comparado com "O(log n)" (ambos estão usando os mesmos dados) podemos identificar de forma clara quem é o mais eficaz, já o "O(n^2)" se mostrou bem ineficiente enquanto o "O(n log n)" absurdamente pior que os demais.

Conclusão

A análise Big O pode ajudar a determinar a melhor solução para um problema específico, bem como identificar gargalos de desempenho em um código existente.

• Wikipédia
• Khan Academy