AlegsaOnline.com

Notação Big O

Autor: Leandro Alegsa

18-12-2020

Big O Notation é uma forma de comparar algoritmos. Ela os compara calculando quanta memória é necessária e quanto tempo leva para ser completada.

A Notação Big O é freqüentemente utilizada para identificar a complexidade de um problema, também conhecida como classe de complexidade do problema. O matemático Paul Bachmann (1837-1920) foi o primeiro a usar esta notação, na segunda edição de seu livro "Analytische Zahlentheorie", em 1896. Edmund Landau (1877-1938) tornou a notação popular. Por esta razão, quando as pessoas falam de um símbolo Landau, elas se referem a esta notação.

Big O Notation é nomeado após o termo "ordem da função", que se refere ao crescimento das funções. A Notação Big O é usada para encontrar o limite superior (a maior quantidade possível) da taxa de crescimento da função, o que significa que ela funciona o tempo mais longo que levará para transformar a entrada na saída. Isto significa que um algoritmo pode ser agrupado pelo tempo que pode levar em um cenário de pior caso, onde a rota mais longa será tomada a cada vez.

Big O é uma expressão que encontra o pior cenário de tempo de execução, mostrando quão eficiente é um algoritmo sem a necessidade de executar o programa em um computador. Isto também é útil, pois computadores diferentes podem ter hardware diferente e, portanto, precisar de diferentes quantidades de tempo para completá-lo. Como o Big O sempre assume o pior caso, ele pode mostrar uma medição consistente da velocidade: independentemente de seu hardware, O ( 1 ) {\\i1}displaystyle O(1)} $O(1)$ sempre vai completar mais rápido que O ( n ! ) {\i1}displaystyle O(n!)} $O(n!)$ porque eles têm diferentes níveis de eficiência.

Exemplos

Os exemplos a seguir utilizam todos códigos escritos em Python. Note que esta não é uma lista completa dos tipos Big O.

Constante

O ( 1 ) O(1)} $O(1)$ . Sempre leva a mesma quantidade de tempo independentemente da entrada. Por exemplo, pegue uma função que aceita um número inteiro (chamado x) e retorna o dobro de seu valor:

def duplo(x): devolver x * 2 #Retornar o valor de x vezes 2

Depois de aceitar a entrada, esta função sempre dará um passo para retornar uma saída. Ela é constante porque sempre levará o mesmo tempo, portanto é O ( 1 ) {\i1} $O(1)$ .

Linear

O ( n ) O(n)} $O(n)$ . Aumenta de acordo com o tamanho da entrada, representado por n estilo de exibição n . Vamos assumir que uma função aceita n, e retorna cada número de 1 a n:

def count(n): i = 1 #Criar um contador chamado "i" com um valor de 1 enquanto i <= n: #Enquanto i é menor ou igual a n impressão(i) #Imprimir o valor de i i i = i + 1 #Redefinir i como "o valor de i + 1".

Se introduzíssemos o valor de 5, isso produziria 1 , 2 , 3 , 4 , 5 {\i1,2,3,4,5}. $1,2,3,4,5$ , exigindo 5 laços para completar. Da mesma forma, se entrássemos 100, ela produziria 1 , 2 , 3...98 , 99 , 100 {\i1,2,3...98,99,100} $1,2,3...98,99,100$ , exigindo 100 loops para completar. Se a entrada for no estilo n (n ), então o tempo de execução do algoritmo é exatamente n (n ), portanto é O ( n ) no estilo O(n)} $O(n)$ .

Fatorial

O ( n ! ) O(n ! ) estilo de jogo O(n !) $O(n!)$ . Aumenta as quantidades fatoriais, o que significa que o tempo gasto aumenta maciçamente com a entrada. Por exemplo, digamos que desejamos visitar cinco cidades ao redor do mundo e queremos ver todos os pedidos possíveis (permutação). Um algoritmo que poderíamos escrever usando a biblioteca de iteróis de Python é o seguinte:

import itertools #Importar as cidades da biblioteca itertools = ['Londres', 'Paris', 'Berlim', 'Amsterdã', 'Roma'] #Uma série de nossas cidades escolhidas defutations(cidades): #Importar um conjunto de cidades como entrada: para i em itertools. permutações(cidades): #Para cada permutação de nossos itens (atribuída à variável "i") impressão(i) #Esaída i

Este algoritmo calculará cada permutação única de nossas cidades e depois a produzirá. Exemplos de saída incluirão:

('Londres', 'Paris', 'Berlim', 'Amsterdã', 'Roma') ('Londres', 'Paris', 'Berlim', 'Roma', 'Amsterdã') ('Londres', 'Paris', 'Amsterdã', 'Berlim', 'Roma') ... ('Roma', 'Amsterdã', 'Paris', 'Berlim', 'Londres') ('Roma', 'Amsterdã', 'Berlim', 'Londres', 'Paris') ('Roma', 'Amsterdã', 'Berlim', 'Paris', 'Londres')

Aqui nossa lista de entradas tem 5 itens, e para cada seleção nossas opções restantes diminuem em 1. Em outras palavras, nossas 5 entradas escolhem 5 × 4 × 3 × 2 × 1 {\i1} itens (ou 5! {\i1} itens no estilo de exibição 5 vezes 4 vezes 3 vezes 2 vezes 1} $5\times 4\times 3\times 2\times 1$ itens (ou 5! $5!$ {\i1} no estilo de exibição 5! Se a nossa entrada é n {\i1}displaystyle n} cidades longas, então o número de saídas é n ! $n!$ em outras palavras, assumindo que passamos por todas as permutações que precisaremos O ( n ! ) O(n ! ) estilo de exibição O(n !)} $O(n!)$ loops para completá-lo.

Notação Little-o

Uma versão mais rígida do Big O é little-o. A diferença entre Big O e little-o é que o little-o é um limite superior rígido: enquanto o O ( n ) {\\i1} $O(n)$ significa que o tempo de conclusão aumentará ao máximo com base no tamanho da entrada, o o ( n ) {\i} $o(n)$ significa que o tempo de conclusão será geralmente inferior a esta quantidade de tempo. Em outras palavras, o Big O assume que cada ciclo tomará o caminho mais longo e o processo o mais longo possível, enquanto o pouco-o é mais realista sobre os tempos reais de execução; se o número de ciclos for baseado no lançamento de um dado de 6 lados, o Big O sempre assumirá que um 6 é lançado, enquanto que o pouco-o fator de probabilidade igual de outros números serem lançados.

Perguntas e Respostas

P: O que é a notação Big O?

R: A notação Big O é uma maneira de comparar taxas de crescimento de diferentes funções, muitas vezes usada para comparar a eficiência de diferentes algoritmos, calculando quanto tempo e memória leva para completar. Ela também pode ser usada para identificar quão complexo é um problema.

P: Quem foi o primeiro a usar essa notação?

R: O matemático Paul Bachmann (1837-1920) foi o primeiro a usar essa notação em seu livro "Analytische Zahlentheorie" em 1896.

P: O que significa Big O?

R: Big O significa "ordem da função", que se refere à taxa de crescimento das funções.

P: Como o Big O é usado?

R: A notação Big O é usada para encontrar um limite superior (a maior quantidade possível) na taxa de crescimento da função, o que significa que ela funciona o tempo mais longo que levará para transformar uma entrada em uma saída. Isso significa que os algoritmos podem ser agrupados por quanto tempo eles levam nos piores cenários, onde o caminho mais longo será tomado a cada vez.

P: O que são símbolos Landau?

R: Os símbolos Landau se referem à notação Big O, cujo nome vem de Edmund Landau (1877-1938), que tornou essa notação popular.

P: Por que o Big O é útil?

R: O Big O nos permite medir a velocidade sem ter que rodar programas em computadores, já que ele sempre assume os piores cenários, tornando-o consistente independentemente das diferenças de hardware entre computadores. Ele também mostra como um algoritmo é eficiente sem ter que rodá-lo realmente em um computador.