tag:blogger.com,1999:blog-47703351840758409012024-03-13T04:33:16.090-03:00PROGRAMERODesenvolvimento e Tecnologia da InformaçãoEduardo Teixeirahttp://www.blogger.com/profile/07555342217742534840noreply@blogger.comBlogger25311tag:blogger.com,1999:blog-4770335184075840901.post-62743892703484593962023-04-03T17:12:00.000-03:002023-04-03T17:12:19.250-03:00C# - Notação Big O<p style="text-align: justify;">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.</p>
<p style="text-align: justify;">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.</p>
<p style="text-align: justify;">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").</p>
<p style="text-align: justify;">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.</p>
<h2 style="text-align: justify;">O(1)</h2>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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.</p>
<pre> <code>
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
</code>
</pre>
<p style="text-align: justify;">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).</p>
<h2 style="text-align: justify;">O(n)</h2>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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:</p>
<pre> <code>
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
}
</code>
</pre>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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.</p>
<h2 style="text-align: justify;">O(n^2)</h2>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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.</p>
<pre> <code>
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
}
}
</code>
</pre>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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.</p>
<h2 style="text-align: justify;">O(log n)</h2>
<p style="text-align: justify;">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).</p>
<div style="text-align: justify;"><div>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.</div></div>
<pre> <code>
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
</code>
</pre>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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).</p>
<h2 style="text-align: justify;">O(n log n)</h2>
<p style="text-align: justify;">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).</p>
<p style="text-align: justify;">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.</p>
<pre> <code>
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];
}
}
</code>
</pre>
<p style="text-align: justify;">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).</p><p style="text-align: justify;">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).</p><h2 style="text-align: justify;">Comparações</h2><p style="text-align: justify;">Fizemos uma pequena aplicação para demonstrar os resultados (que pode ser encontrada <a href="https://github.com/dunirvana/DotNetBigOApp/tree/master" target="_blank">aqui</a>) e o resultado foi o seguinte:</p>
<pre> <code>
| 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 |
</code>
</pre>
<p style="text-align: justify;">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.</p><h2 style="text-align: justify;">Conclusão</h2><p style="text-align: justify;">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.</p><p style="text-align: justify;"></p><ul><li><a href="https://en.wikipedia.org/wiki/Big_O_notation#:~:text=Big%20O%20notation%20is%20a%20mathematical%20notation%20that,others%2C%20collectively%20called%20Bachmann%E2%80%93Landau%20notation%20or%20asymptotic%20notation." target="_blank">Wikipédia</a></li><li><a href="https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation" target="_blank">Khan Academy</a></li></ul><p></p><p style="text-align: justify;"><br /></p><scribe-shadow id="crxjs-ext" style="height: 0px; left: 0px; overflow: visible; position: fixed; top: 0px; width: 0px; z-index: 2147483647;"></scribe-shadow>Eduardo Teixeirahttp://www.blogger.com/profile/07555342217742534840noreply@blogger.com0