Notação grande o na estrutura de dados: tudo para saber

A notação Big O em uma estrutura de dados é usada para determinar a eficiência de um algoritmo, a quantidade de tempo que leva para executar a função com o crescimento da entrada e quão bem a função é dimensionada. A medição dessa eficiência pode ser dividida em duas partes, a saber, a complexidade do espaço e a complexidade do tempo.

A notação Big O refere-se à notação matemática que atua como um fator limitante de qualquer função quando um argumento é mais propenso a se inclinar para um valor específico ou infinito. Pertence à categoria de notações matemáticas inventadas por Edmund Landau, Paul Bachmann e outros. Por isso, é chamado coletivamente de notação Bachmann-Landau ou notação assintótica.

De acordo com a dedução matemática, duas funções, f(n) eg(n) são definidas em um conjunto de números positivos ou reais que não são vinculados. Aqui, g(n) é estritamente positivo para todo grande valor de n. Pode ser escrito da seguinte forma:

f(n) = O(g(n)) em que n tende ao infinito (n → ∞)

No entanto, aqui, a suposição de n ao infinito não é definida exclusivamente, e a expressão acima pode, portanto, ser escrita como:

f(n) = O(g(n))

Aqui, f e g são as funções necessárias que começam de inteiros positivos a números reais que não são não-negativos.

Assim, valores grandes de n são denotados pelo Big O assintótico.

Propriedades da notação Big O na estrutura de dados

O algoritmo Big O na estrutura de dados tem algumas propriedades obrigatórias. As referidas propriedades essenciais da notação Big O são as seguintes:

• Função de soma:
  Se f(n) = f 1 (n) + f 2 (n) + — + f m (n) e f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  então O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Função logarítmica:
  Se f(n) = logan e g(n) = logbn,
  então O(f(n))=O(g(n))
• Multiplicação constante:
  Se f(n) = cg(n), então O(f(n)) = O(g(n)) em que c é uma constante diferente de zero.
• Função polinomial:
  Se f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  então O(f(n)) = O(nm).

Aprenda cursos de desenvolvimento de software online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Explore nossos cursos populares de engenharia de software

Aqui, ao endereçar o Big O, cada função de log aumenta de forma semelhante.

Importância da notação Big O na análise de algoritmos em tempo de execução

As complexidades do tempo de execução do pior caso do algoritmo são usadas para traçar comparações e calcular, especialmente no caso de analisar o desempenho de um algoritmo. A ordem de O(1), descrita como Constant Running Time, é o tempo de execução mais rápido do algoritmo – o tempo que o algoritmo leva é o mesmo para vários tamanhos de entrada. É importante notar que o tempo de execução ideal de um algoritmo é o tempo de execução constante, o que muito raramente é alcançado porque o tempo de execução do algoritmo depende do tamanho da entrada de n.

Por exemplo:

Como mencionado acima, o desempenho de tempo de execução de um algoritmo depende principalmente do tamanho de entrada de n. Vamos elucidar esse fato com alguns exemplos matemáticos para fazer a análise em tempo de execução de um algoritmo para vários tamanhos de n:

• n = 20
  log(20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• n = 10
  log(10) = 1;
  10 = 10;
  10 log(10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

O desempenho de tempo de execução de um algoritmo é calculado de forma semelhante.

Aqui estão alguns outros exemplos algorítmicos de análise de tempo de execução –

• Quando se trata de Pesquisa Linear, a complexidade do tempo de execução é O(n).
• A complexidade do tempo de execução é O(log n) para pesquisa binária.
• Para Selection Sort, Bubble Sort, Bucket Sort, Insertion Sort, a complexidade do tempo de execução é O(n^c).
• Quando se trata de algoritmos exponenciais, como a Torre de Hanói, a complexidade do tempo de execução é O(c^n).
• Para Merge SortSort e Heap Sort, a complexidade do tempo de execução é O(n log n).

Como o Big O analisa a complexidade do espaço?

Determinar a complexidade de espaço e tempo de execução para um algoritmo é uma etapa essencial. Isso ocorre porque podemos determinar o tempo de execução que um algoritmo leva analisando o desempenho de tempo de execução do algoritmo e o espaço de memória que o algoritmo está ocupando por meio da análise da complexidade do espaço do algoritmo. Portanto, para medir a complexidade espacial de um algoritmo, devemos comparar o desempenho da complexidade espacial do pior caso do algoritmo.

Para determinar a complexidade do espaço de um algoritmo, devemos seguir estas duas tarefas –

Tarefa 1: É vital implementar o programa para um algoritmo específico.

Tarefa 2: É essencial saber o tamanho da entrada n para determinar a memória que cada item conterá.

Essas duas tarefas essenciais precisam ser realizadas antes de calcular a complexidade do espaço para um algoritmo.

Exemplos de Algoritmos de Complexidade Espacial

Existem muitos exemplos de algoritmos com complexidade espacial, alguns dos quais foram citados abaixo para melhor compreensão desse tipo de algoritmo:

• Para classificação por bolha, pesquisa linear, classificação por seleção, classificação por inserção, classificação por heap e pesquisa binária, a complexidade do espaço é O(1) .
• A complexidade do espaço é O(n+k) quando se trata de radix sort .
• A complexidade do espaço é O(n) para SortSort rápida.
• A complexidade do espaço é O(log n) para ordenação por mesclagem.

Exemplo de notação O grande em C

É um fato que a notação Big O é usada principalmente em Ciência da Computação para determinar a complexidade ou desempenho de um algoritmo. Essa notação nos fornece a capacidade de classificar o comportamento dos algoritmos com base no crescimento do espaço de memória ou nos requisitos de tempo de execução quando a extensão dos dados de entrada se torna grande. Ele não foi projetado para prever o uso real da memória ou o tempo de execução, mas para comparar algoritmos e, em seguida, selecionar o melhor entre eles para o trabalho. Não é específico da linguagem, mas também é implementado em C.

Abaixo, você encontrará o algoritmo de ordenação por seleção em C, onde a complexidade do pior caso (notação Big O) do algoritmo foi calculada: -

for(int i=0; i<n; i++)

{

int min = i;

for(int j=i; j<n; j++)

{

if(matriz[j]<matriz[min])

min=j;

}

int temp = array[i];

matriz[i] = matriz[min];

array[min] = temp;

}

Para analisar o algoritmo:

• Já pode ser denotado que o alcance do laço for externo é i < n , o que indica que a ordem do laço é O(n).
• Em seguida, podemos identificar que também é O(n) como j < n para o laço for interno.
• A constante é ignorada, mesmo que a eficiência média seja encontrada n/2 para uma constante c. Então, a ordem é O(n).
• Depois de multiplicar a ordem do loop interno e do loop externo, a complexidade de tempo de execução alcançada é O(n^2).

Outros algoritmos em C podem ser facilmente implementados, onde as complexidades podem ser facilmente analisadas e determinadas de forma semelhante.

Uso da notação O grande

Existem duas áreas principais onde a notação Big O é aplicada: -

• Matemática : A notação Big O é bastante usada no campo da matemática para descrever como uma série finita se aproxima de uma função, especialmente quando se trata de casos de expansão assintótica ou série de Taylor truncada.
• Ciência da computação: É um fato bem estabelecido que a notação Big O é usada principalmente no campo da ciência da computação devido à sua utilidade na análise de algoritmos

No entanto, em ambas as aplicações, a função g ( x ) que aparece dentro de O (·) é frequentemente escolhida para ser possivelmente a mais simples se os termos de ordem inferior e os fatores constantes forem omitidos.

Existem dois outros usos dessa notação que são formalmente próximos, mas relativamente diferentes. Eles são:-

• Assintótico infinito
• Assintótico infinitesimal.

No entanto, esta distinção não é, em princípio, aplicável apenas com a definição formal para o “Big O” sendo exatamente a mesma para ambos os casos. A única diferença são os limites para o argumento da função.

Leia nossos artigos populares relacionados ao desenvolvimento de software

Conclusão

Em conclusão, podemos dizer que o Big Data desempenha um papel integral nas estruturas de dados, e ter um conhecimento profundo e abrangente sobre a notação Big O é um excelente conjunto de habilidades para se possuir. Está em alta demanda no setor de trabalho e pode ser potencialmente uma ótima opção para uma carreira. O Programa Avançado de Certificação em Big Data do upGrad lhe dará a alavancagem que você precisa para impulsionar sua carreira. Ele apresentará as principais habilidades profissionais, como Processamento de dados com PySpark, Data Warehousing, MapReduce, Processamento de Big Data na Nuvem AWS, Processamento em tempo real, etc.