Grande-O

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Mergefrom 2.svg
O artigo ou secção Notação Big-O deverá ser fundido aqui. (desde junho de 2012)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Cheque ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).
Exemplo da notação O-grande: f(x) ∈ O(g(x)) de forma que existem c > 0 (e.g., c = 1) e x0 (e.g., x0 = 5) tal que f(x) ≤ cg(x) sempre que x ≥ x0.

Na matemática, a notação O-grande descreve o comportamento limitante de uma função função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples. É membro de uma família maior de notações conhecida como notação Landau, notação Bachmann–Landau (nomeada dessa forma por conta de Edmund Landau e Paul Bachmann),[1] [2] ou notação assintótica. Em ciência da computação, o O-grande é usado para classificar algorítimos pela forma como eles respondem (ex., no tempo de processamento ou espaço de trabalho requerido) a mudanças no tamanho da entrada.[3] Na teoria analítica dos números, é usado para estimar o "erro cometido" quando se substitui o tamanho assintótico, ou o tamanho assintótico médio, de uma função aritmética, pelo valor, ou pelo valor médio, que ela recebe num argumento grande e finito. Um exemplo famoso é o problema de estimar o termo restante no teorema do número primo.

A notação O-grande caracteriza fuções de acordo com suas taxas de crescimento: funções diferente com as mesmas taxas de crescimento tem a mesma notação O-grande. A letra O é usada porque a taxa de crescimento de uma função também é referenciada como como a ordem de uma função. Uma descrição de uma função em termos de O-grande normalmente provê um limite superior na taxa de crescimento da função. Associada a notação O-grande existem várias outras notações, usando os símbolos o, Ω, ω, e Θ, para descrever outros tipos de relacionamento com taxas de crescimento assintóticas.

A notação O-grande é também usada por muitos campos para prover estimativas similares.

Definição Formal[editar | editar código-fonte]

Sejam f e g duas funções definidas no mesmo subconjunto dos números reais pode-se dizer que

se e somente se existe uma constante positiva M tal que para todo valor suficientemente grande de x, o valor absoluto de f(x) é no máximo M multiplicado pelo valor absoluto de g(x). Isto é, f(x) = O(g(x)) se e somente se existe um número real positivo M e um número real x0 tal que

Em muitos contextos, a premissa que estamos interessados, a taxa de crescimento quando a variável x tende ao infinito, é deixada implícita, e é possível representá-la de forma mais simples em, f(x) = O(g(x)).

A notação também pode ser usada para representar o comportamento de f perto de algum número real a (muitas vezes, a = 0): dizemos

se somente se existem números positivos δ e M tal que

Se g(x) são os valores não nulos de x que são suficientemente próximos a a, ambas essas definições podem ser unidas usando limite superior:

se somente se

Adicionalmente, a notação O(g(x)) também é usada para denotar o conjunto de todas as funções f(x) que satisfação a relação f(x)=O(g(x)). Nesse caso escrevemos

Exemplo[editar | editar código-fonte]

Numa utilização típica, a definição formal da notação O não é usada diretamente; ao invés disso, a notação O de uma função f é entregue pelas regras de simplificação a seguir:

  • Se f(x) é a soma de vários termos, o que possuir maior taxa de crescimento é mantido, e todos os outros são omitidos.
  • Se f(x) é um produto de diversos fatores, quaisquer constantes (termos do produto que não depente de x) são omitidos.

Por exemplo, seja f(x) = 6x4 − 2x3 + 5, e suponha que desejemos simplificar essa função, usando a notação O, para descrever o aumento da sua taxa de crescimento a medida que x se aproxima do infinito. Essa função é a soma de três termos: 6x4, −2x3, e 5. Desses três termos, o que possui maior taxa de crescimento é o que possui maior expoente em função de x, isto é, 6x4. Agora deve-se aplicar a segunda regra: 6x4 é um produto de 6 ex4 no qual o primeiro fator não depende de x. Omitir esse fator resulta na forma simplificada x4. Assim, dizemos que f(x) é um "o-grande" de (x4). Matematicamente, podemos escrever f(x) = O(x4). Pode-se confirmar esse cálculo usando a definição formal: seja f(x) = 6x4 − 2x3 + 5 e g(x) = x4. Aplicando a definição formal acima, a afirmação de que f(x) = O(x4) é equivalente a sua expansão,

para alguma escolha adequada de x0 e M e para todo x > x0. Para provar isso, seja x0 = 1 e M = 13. Então, para todo x > x0:

então

Utilização[editar | editar código-fonte]

A notação O-grande possui duas grandes áreas de aplicação. Em matemática, é comumente usada para descrever o quão perto uma série finita se aproxima de uma função, especialmente no caso de uma Série de Taylor truncada ou uma expansão assintótica. Em ciência da computação, é útil na análise de algoritmos. Em ambas aplicações, a função g(x) que aparece com o O(...) é tipicamente a mais simples possível, omitindo fatores constantes e termos de mais baixa ordem. Existem dois usos formalmente parecidos, mas visivelmente diferentes, dessa notação: comportamento assintótico no infinito e comportamento assintótico infinitesimal. Essa distinção é só na aplicação, mas não no princípio, porém, a definição formal de O-grande é a mesma para ambas as classes, mudando somente os limites para o argumento da função.

Assintótico no Infinito[editar | editar código-fonte]

A notação O-grande é útil na análise de algorítimos por eficiência. Por exemplo, o tempo (ou o número de passos) que ele leva para resolve um problema de tamanho n pode ser considerado T(n) = 4n2 − 2n + 2. Quando n cresce, o termo n2 vai dominar, de forma que os outros termos podem ser negligenciados — por exemplo quando n = 500, o termo 4n2 é 1000 vezes maior que o termo 2n. Ignorando este termo teria um efeito negligenciável sobre o valor da expressão para muitos propósitos. Além disso, os coeficientes se tornam irrelevantes se comparados a qualquer outra ordem de expressão, de forma que uma expressão contendo um termo n3 ou n4. Mesmo no caso de T (n) = 1.000.000n2, se U(n) = n3, este último será sempre superior ao primeiro n se torna maior do que 1,000,000 (T(1,000,000) = 1,000,0003= U(1,000,000)). Adicionalmente, o número de passos depende dos detalhes do modelo de máquina no qual o algoritmo roda, mas diferentes tipos de máquina normalmente variam de apenas um fator constante no número de passos necessários para executar o algorítmo. Então a notação O-grande cobre o restante: podemos escrever tanto

quanto

e dizer que o algoritmo possui complexidade de tempo na ordem de n2. Note que "=" não significa "é igual a" como na senso comum matemático, e sim um "é" mais coloquial, de forma que a segunda expressão é tecnicamente precisa (veja a discussão sobre o "Sinal de igualdade" abaixo) enquanto a primeira é considerada por alguns com um abuso de notação.[4]

Assintótico Infinitesimal[editar | editar código-fonte]

O-grande também pode ser usado para descrever o termo de erro numa aproximação a uma função matemática. Os termos mais significativos são escritos explicitamente, e então os termos menos significativos são resumidos a um único termo O-grande. Considere, por exemplo, serie exponencial e duas expressões dela que são válidas quando x é pequeno:

A segunda expressão (a que possui O(x3)) representa que o valor absoluto do erro ex − (1 + x + x2/2) é menor do que alguns tempos constantes |x3| quando x é suficientemente próximo de 0.

Propriedade[editar | editar código-fonte]

Se a função f puder ser escrita como uma soma finita de outras funções, então a que cresce mais rápido é que determina a ordem de f(n). Por exemplo

Em particular, se uma função pode ser delimitada por um polinômio em n, então quando n tende ao infinito, , pode-se desprezar os termos de baixa ordem do polinômio. Outra coisa a se considerar é que os conjuntos O(nc) e O(cn) são muito diferentes. Se c for maior que um, então o último cresce muito mais rápido. Uma função que cresce mais rápido que nc para qualquer c é chamada superpolinomial. Uma que cresce mais devagar que qualqrue função exponencial na forma cn é chamada subexponential. Um algoritmo pode requerer um tempo que seja ao mesmo tempo superpolinomial e subexponential; exemplos disso incluem os algoritmos mais rápidos para fatoração de inteiros e a função nlog n.

Nós podemos ignorar quaisquer potências de n dentro de logaritmos. O conjunto O(log n) é exatamente o mesmo que O(log(nc)). Os logaritmos diferem apenas de um fator constante (já que log(nc) = c log n) e assim a notação O-grande ignora isso. Similarmente, logs with bases constantes diferente são equivalentes. Por outro lado, exponenciais com bases diferentes não são de mesma ordem. Por exemplo, 2n e 3n não são de mesma ordem.

Mudar unidades pode ou não afetar a ordem dos algoritmos resultantes. Mudar unidades é equivalente a multiplicar a variável apropriada por uma constante onde quer que ela apareça. Por exemplo, se um algoritmo roda na ordem de n2, substituir o n por cn significa que o algoritmo roda na ordem de c2n2, e a notação O-grande ignora a constante c2. Isso pode ser escrito como c2n2 = O(n2). Se, no entanto, um algoritmo roda na ordem de 2n, substituir n por cn nos dá 2cn = (2c)n. Isso não é equivalente a 2n em geral. Mudar variáveis também pode afetar a ordem do algoritmo resultante. Por exemplo, se o tempo de execução de um algoritmo for O(n) quando medido em termos do número n de dígitos de um número x na entrada, então o seu tempo de execução é O(log x) quando medido em relação ao próprio número x da entrada, porque n = O(log x).

Produto[editar | editar código-fonte]

Soma[editar | editar código-fonte]

Isso implica que , que significa que é um cone convexo.
Se f e g são funções positivas,

Multiplicação por uma constante[editar | editar código-fonte]

Seja k uma constante. Então:
se k é diferente de zero.

Múltiplas variáveis[editar | editar código-fonte]

O-grande (e o-pequeno, e Ω...) também pode ser usado com muitas variáveis. Para definir O-grande formalmente para múltiplas variáveis, suponha que e são duas funções definidas em um subconjunto de . Nós dizemos que

se somente se[5]

Equivalentemente, a condição em que para algum pode ser substituída pela condição em que , onde denota a Distância de Chebyshev. Por exemplo, a sentença

afirma que existem constantes C e M tal que

onde g(n,m) é definido por

Note que essa definição permite a todas as coordenadas de incrementar o infinito. Em particular, a sentença

(i.e., ) é bem diferente de

(i.e., ).

Essa não é a única generalização de O-grande para funções multi-variadas, e na prática, há alguma inconsistência na escolha da definição.[6]

Questões de notação[editar | editar código-fonte]

Sinal de igualdade[editar | editar código-fonte]

A afirmação "f(x) é O(g(x))" como definido acima é frequentemente escrita como f(x) = O(g(x)). Alguns consideram isso como sendo um abuso de notação, desde que o uso de sinais de igualdade poderiam levar a possíveis erros, ao passo que ela sugere uma simetria que a afirmação não carrega. Como de Bruijn disse, O(x) = O(x2) é verdade, porém O(x2) = O(x) não é.[7] Knuth descreve essas afirmações como "igualdades de caminho único", desde que os lados não podem ser revertidos, "nós poderíamos deduzir coisas ridículas como n = n2 das identidades n = O(n2) e n2 = O(n2)."[8] Por essas razões, seria mais preciso usar a notação de conjuntos e escrever f(x) ∈ O(g(x)), pensando em O(g(x)) como a classe de todas as funções h(x) tais que |h(x)| ≤ C|g(x)| para alguma constante C.[8] No entanto, o uso do sinal de igual é habitual. Knuth destacou que "os matemáticos costumam usar o sinal = como eles usam a palavra 'é' em Inglês: Aristóteles é um homem, mas um homem não é necessariamente Aristóteles."[9]

Outros operadores aritméticos[editar | editar código-fonte]

A notação O-grande também pode ser usada em conjunto com outros operadores aritméticos em equações mais complicadas. Por exemplo, h(x) + O(f(x)) denota a coleção de funções com crescimento de h(x) mais uma parte cujo crescimento é limitado ao de f(x). Assim,

expressa o mesmo que

Exemplo [editar | editar código-fonte]

Suponha que um algoritmo está sendo desenvolvido para operar num conjunto de n elementos. Seus desenvolvedores estão interessados em encontrar uma função T(n) que expresse quanto tempo o algoritmo vai levar para rodar (numa medida arbitrária de tempo) em termos do número de elementos no conjunto da entrada. O algoritmo funciona primeiro chamando uma sub-rotina que ordena os elementos no conjunto e então executa suas próprias operações. A ordenação tem uma complexidade de tempo conhecida de O(n2), e depois da sub-rotina, o algoritmo deve executar 55n3 + 2n + 10 passos adicionais antes de terminar. Assim a complexidade de tempo deram do algoritmo pode ser expressa como T(n) = 55n3 + O(n2). Aqui os termos 2n+10 estão submissos ao crescimento mais rápido O(n2). Novamente, essa utilização desconsidera alguns dos significados formais do símbolo "=", mas permite que se use a notação O-grande como uma espécie de marcador de posição conveniente.

Declaração de variáveis[editar | editar código-fonte]

Outra característica dessa notação, embora menos excepcional, é que os argumentos da função podem ter de ser inferidas a partir do contexto quando muitas variáveis estiverem envolvidas. Os dois lados direitos das notações O-grande a seguir possuem têm significados radicalmente diferentes

O primeiro caso indica que f(m) apresenta um crescimento polinomial, enquanto que o segundo assumindo m > 1, afirma que g(n) apresenta crescimento exponencial. Para evitar confusão, alguns autores[quem?] usam a notação

em detrimento da menos explícita

Múltiplos usos[editar | editar código-fonte]

Na forma mais complicada de usar, O(...) pode aparecer em diferentes lugares da equação, inclusive muitas vezes em cada um dos lados. Por exemplo, as seguintes equações são verdade para

O significado dessas afirmações é: para quaisquer funções que satisfaçam cada O(...) do lado esquerdo, existem algumas que satisfaçam O(...) do lado direito, de forma que substituindo todas essas funções na equação os dois lados são iguais. Por exemplo, a terceira equação acima significa que: "Para qualquer função f(n) = O(1), existe uma função g(n) =O(en) de forma que nf(n) = g(n)." Em termos da "notação de conjuntos" acima, o significado é que a classe de funções representada pelo lado esquerdo é um subconjunto da classe de funções representada pelo lado direito. Nesse uso, o "=" é um símbolo formal que, diferentemente do uso comum do "=", não é uma relação simétrica. Assim, por exemplo, nO(1) = O(en) não implica na afirmação falsa O(en) = nO(1)

Ordens das funções comuns[editar | editar código-fonte]

Aqui está uma lista das classes de funções que são comumente encontradas quando analisando a complexidade de tempo de execução de um algoritmo. Em cada caso, c é uma constante e n cresce sem limites. As funções de crescimento mais lento estão geralmente listadas primeiro.

Notação Nome Exemplo
constante Determinar se um número binário é par ou ímpar; Calcular ; Usar uma LUT de tamanho constante
duplamente logaritmica Número de comparações gasto para encontrar um item usando busca por interpolação em um array ordenado de valores distribuídos uniformemente
logarítmico Encontrar um item em uma matriz ordenada com uma busca binária ou uma árvore de busca balanceada, bem como todas as operações num heap binomial
polilogarítmico Ordenação de uma cadeia de matrizes pode ser resolvida em tempo polilogarítmico numa Máquina de acesso aleatório paralelo.
potencia fracional Busca em uma Árvore k-d
linear Encontrar um item em uma lista desordenada ou uma árvore mal-formada (pior caso) ou num array desordenado; adicionar dois inteiros com n bits por um circuito aritmético
n logaritmo iterado n Rodar uma triangulação de um simples polígono usando o algoritmo de Seidel, ou a prova do algoritmo de União-Busca. Perceba que
linearítmico, loglinear, ou quasilinear Rodar uma Transformada Rápida de Fourier; heapsort, quicksort (melhor caso e caso médio), ou merge sort
quadrático Multiplicar dois números de n digitos usando um algoritmo simples; bubble sort (pior caso, ou implementação ingênua), Shell sort, quicksort (pior caso), selection sort ou insertion sort
polinomial ou algébrico parsing de Gramáticas de árvores disjuntas; máximo isomofismo para grafos bipartidos

notação L ou sub-exponencial Fatorar um número usando o crivo quadrático ou campo de número de peneira geral
exponencial Encontrar a solução exata para o Problema do cacheiro viajante usando programação dinâmica; Determinar se duas afirmações lógicas são equivalentes usando busca por força bruta
fatorial Encontrar a solução exata para o Problema do cacheiro viajante usando busca por força bruta; gerar todas as permutações irrestritas de um poset; encontrar um determinante com expansão por menores; enumerar todas as partições de um conjunto

A sentença é algumas vezes enfraquecida para para derivar em fórmulas mais simples por complexidade assintótica. Para qualquer e , é um conjunto de para qualquer , então pode ser considerada como um polinomial com uma alta ordem.

Notações assintóticas relacionadas[editar | editar código-fonte]

O-grande é a notação assintótica mais utilizada para comparação de funções, porém em muitos casos pode ser substituída por Theta-grande Θ para limites mais apertados. Aqui nós definiremos algumas notações relacionadas em termos de O-grande, avançando até a família de notações de Bachmann-Landau, da qual a notação O-grande pertence.

Notação o-pequeno[editar | editar código-fonte]

Disambig grey.svg Nota: o-pequeno redireciona para este artigo. Para o jogador de beisebol, veja Omar Vizquel.

A sentença informal "f(x) é o-pequeno de g(x)" é escrita formalmente como f(x) = o(g(x)), ou, na notação de conjuntos, f(x) ∈ o(g(x)). Intuitivamente, isso significa que g(x) cresce muito mais rápido que f(x), ou similarmente, que o crescimento de f(x) não é nada comparado ao de g(x). Ela assume que f e g são duas funções de uma variável. Formalmente, f(n) = o(g(n)) (ou f(n) ∈ o(g(n))) quando n → ∞ significa que para toda constante positiva ε existe uma constante N tal que

[8]

Note que a diferença entre a definição formal da notação O-grande, e a definição de o-pequeno: enquanto a primeira deve ser verdade para pelo menos uma constante M a segunda deve se verificar para todas as constantes positivas ε, mesmo as pequenas.[4] Dessa maneira, a notação o-pequeno faz uma afirmação mais forte que a da notação O-grande: toda função que é o-pequeno de g também é O-grande de g, mas nem toda função que é O-grande de g também é o-pequeno de g (por exemplo a própria g não é, a menos que ela seja identicamente zero perto de ∞).

Se g(x) é não nula, ou pelo menos se torna não nula a partir de certo ponto, a relação f(x) = o(g(x)) é equivalente a

Por exemplo,

A notação o-pequeno é comum na matemática, porém mais rara em ciência da computação. Em ciência da computação a variável (e o valor da função) é frequentemente um número natural. Na matemática, a variável e o valor da função não frequentemente números reais. As propriedades a seguir (expressadas na mais recente notação da teoria dos conjuntos) pode ser útil:

  • para todo
  • (e assim a propriedades acima são aplicadas na maioria das combinações de o e O).

Assim como na notação O-grande, a afirmação " é " é comumente escrita como , o que alguns consideram um abuso de notação.

Notação Omega-grande[editar | editar código-fonte]

Há duas definições muito generalizadas e incompatíveis da afirmação

onde a é um número real, ∞, ou −∞, onde f e g são funções reais definidas numa vizinhança de a, e onde g é positiva nessa vizinhança.

A primeira (cronologicamente) é usada na teoria analítica dos números, e a segunda na teoria da complexidade computacional. Quando os dois assuntos se encontram, a situação frequentemente leva a confusão.

A definição de Hardy–Littlewood[editar | editar código-fonte]

Em 1914 G.H. Hardy e J.E. Littlewood introduziram o novo símbolo ,[10] que é definido da seguinte forma:

.

Assim é a negação de .

Em 1916 os mesmos autores introduziram os dois novos símbolos e ,[11] definidos assim:

;
.

Como sendo a negação de , e a negação de .

Contrariando a última afirmação de D.E. Knuth,[12] Edmund Landau fez uso desses três símbolos, com o mesmo significado, em 1924.[13]

Esses símbolos de Hardy-Littlewood são protótipos, que depois de Landau não foram mais usadas exatamente assim.

se tornou , e se tornou .

Esses três símbolos , assim como (significando que e são ambos satisfeitos), são usados atualmente na teoria analítica dos números.[14]

Exemplos simples[editar | editar código-fonte]

Temos

e de forma mais precisa

Temos

e de forma mais precisa

porém

A definição de Knuth[editar | editar código-fonte]

Em 1976 Donald Knuth publicou um artigo para justificar o seu uso do símbolo para descrever uma propriedade mais forte. Knuth escreveu: "Para todas as aplicações que eu já vi em ciência da computação, um requisito mais forte […] é mais apropriado". Ele definiu que

com o seguinte comentário: "Apesar de eu ter alterado a definição de Hardy e Littlewood de , eu sinto que isso está justificado porque a definição deles não está de forma alguma sendo usada em larga escala, e porque existem outras maneiras de dizer o que eles querem dizer nos comparativamente raros casos nos quais a definição deles se aplica".[12] Contudo, a definição Hardy–Littlewood havia sido utilizada por pelo menos 25 anos. [15]

Família de notações de Bachmann–Landau[editar | editar código-fonte]

Notação Nome Ideia intuitiva Definição informal: para um suficientemente grande... Definição formal
O-grande; Omicron-grande[12] é limitada superiormente por (até no máximo um fator constante) assintoticamente for some positive k
Omega-grande  :

Teoria dos números:

não é dominada por assintoticamente

Teoria da complexidade:

é limitada por baixo por assintoticamente

Teoria dos números:

por infinitos valores de n e para algum k positivo

Teoria da complexidade:

para algum k positivo

Teoria dos números:

Teoria da complexidade:

Theta-grande é limitada por cima e por baixo por assintoticamente para algum k1 e algum k2 positivos

o-pequeno é dominado por assintoticamente , para todo número positivo
Omega-pequeno domina assintoticamente , para todo número positivo
Na ordem de é igual a assintoticamente


Além da notação O-grande, as notações Theta-grande e Omega-grande são as duas mais frequentemente utilizadas em ciência da computação; a notação omega-pequeno ω é ocasionalmente usado em ciência da computação.

Além da notação O-grande, as notações o-pequeno, Ω-grande e são as três mais comumente usadas na teoria dos números; a notação omega-pequeno ω nunca é usada na teoria dos números.

Usos em ciência da computação[editar | editar código-fonte]

Para obter mais detalhes sobre este tópico, veja Análise de algoritmos.

Informalmente, especialmente em ciência da computação, a notação O-grande muitas vezes é permitida a ser um tanto abusada para descrever um limite assintótico apertado, quando usando a notação Theta-grande Θ poderia ser mais factualmente apropriada num dado contexto. [carece de fontes?] Por exemplo, quando consideramos uma função T(n) = 73n3 + 22n2 + 58, todos as afirmações a seguir são geralmente aceitas, mas limites mais apertados (i.e., números 2 e 3 abaixo) são fortemente preferíveis no lugar de limites mais frouxos (i.e., número 1 abaixo).

  1. T(n) = O(n100)
  2. T(n) = O(n3)
  3. T(n) = Θ(n3)

As afirmações equivalentes em português são respectivamente:

  1. T(n) não cresce assintoticamente mais rápido que n100
  2. T(n) não cresce assintoticamente mais rápido que n3
  3. T(n) não cresce assintoticamente tão rápido quanto n3.

Então apesar dessas essas três afirmações serem verdade, cada uma delas contem progressivamente mais informação. Em alguns campos, contudo, a notação O-grande (número 2 nas listas acima) seria mais comumente utilizada que a notação Theta-grande (itens número 3 nas listas acima). Por exemplo, se T(n) representa o tempo corrente de um algoritmo recém desenvolvido para entrada de tamanho n, os desenvolvedores e usuários do algoritmo podem estar mais inclinados a colocar um limite superior assintótico em quando tempo ele vai levar para rodar sem fazer uma afirmação explícita sobre o limite inferior assintótico.

Extensão da notação de Bachmann–Landau[editar | editar código-fonte]

Outra notação que às vezes é utilizada em ciência da computação é Õ (lê-se O-suave): f(n) = Õ(g(n)) é uma abreviação para f(n) = O(g(n) logk g(n)) para algum k. Essencialmente, ela é a notação O-grande, ignorando fatores logarítmicos porque os efeitos da taxa de crescimento de algumas outras funções super-logarítmicas indicam uma taxa de crescimento explosiva para parâmetros de entrada de grande-porte que é mais importante para prever má performance que os efeitos de alta-granularidade contribuídos pelo(s) fator(es) de crescimento logarítmico. Essa notação é comumente usada para prevenir as "picuinhas" sobre taxas de crescimento que são definidas como limitadas rigorosamente demais para os assuntos discutidos (uma vez que logk n é sempre o(nε) para qualquer constante k e qualquer ε > 0).

Também a notação L, definida como

é conveniente para funções que estão entre polinomial e exponencial em termos de .

Generalizações e usos relacionados[editar | editar código-fonte]

A generalização de funções com valores em qualquer espaço vetorial normalizado é direta (substituindo valores absolutos por normas), onde f e g precisam não tomar seus valores no mesmo espaço. Uma generalização a funções g tomando valores em qualquer grupo topológico também é possível.

O "processo de limitação" x→xo também pode ser generalizado pela introdução de um filtro arbitrário, i.e. para sequências generalizadas direcionadas f e g. A notação o pode ser usada para definir derivadas e diferenciabilidade em espaços bastante gerais, e também equivalência (assintótica) de funções,

que é uma relação de equivalência e uma noção mais restritiva que o relacionamento "f é Θ(g)" acima. (Ele é reduzido a lim f / g = 1 se f e g são funções valoradas com reais positivos.) Por exemplo, 2x é Θ(x), mas 2x − x não é o(x).

História (notações de Bachmann–Landau, Hardy, e Vinogradov)[editar | editar código-fonte]

O símbolo O foi primeiramente introduzido pelo teórico dos números Paul Bachmann em 1894, no segundo volume do seu livro Analytische Zahlentheorie ("teoria analítica dos números"), o primeiro volume deste (que ainda não continha a notação O-grande) foi publicado em 1892.[16] O teórico dos números Edmund Landau a adotou, e foi assim inspirado a introduzir em 1909 a notação o;[17] de maneira que ambos são chamados agora de símbolos de Landau. Essas notações foram usadas em matemática aplicada na década de 1950 para análise assintótica.[18] O O-grande foi popularizado em ciência da computação por Donald Knuth, que reintroduziu as notações relacionadas Omega e Theta.[12] Knuth também notou que a notação Omega foi introduzida por Hardy and Littlewood[10] sob um significado diferente "≠o" (i.e. "não é um o de"), e propôs a definição acima. A definição original de Hardy e Littlewood (que também foi usada em um artigo de Landau[13] ) ainda é usada na teoria dos números (onde a definição de Knuth nunca é usada). De fato, Landau também usou em 1924, no artigo mencionado anteriormente, os símbolos ("direita") e ("esquerda"), que foram introduzidos em 1918 por Hardy e Littlewood,[11] e que foram precursores dos símbolos modernos ("não é menor que um o-pequeno de") e ("não é maior que um o-pequeno de"). Assim os símbolos Omega (com seus significados originais) são às vezes referenciados como "símbolos de Landau".

Também, Landau nunca usou os símbolos Theta-grande e omega-pequeno.

Os símbolos de Hardy foram (em termos da notação O moderna)

  e  

(Hardy, no entanto, nunca definiu ou usou a notação , nem , como algumas vezes foi reportado). Também deveria ser percebido que Hardy introduziu os símbolos e (assim como alguns outros símbolos) em seu folheto de 1910, "Ordens do Infinito", e faz uso deles em três artigos (1910–1913). Em seus quase 400 artigos e livros remanescentes ele consistentemente usa os símbolos de Landau O e o.

A notaçãode Hardy não é mais usada. Por outro lado, na década de 1930, [19] o teórico dos números russo Ivan Matveyevich Vinogradov introduziu sua notação , que foi gradualmente mais usada na teoria dos números no lugar da notação . Temos que

e frequentemente ambas as notações são usadas no mesmo artigo.

O O-grande originalmente significava "ordem de" ("Ordnung", Bachmann 1894), e é uma letra latina. Nem Bachmann nem Landau a chamavam de "Omicron". O símbolo foi posteriormente em 1976 visto por Knuth como um omicron maiúsculo,[12] provavelmente em referência a sua definição do símbolo Omega. O dígito zero não deve ser usado.

Veja também[editar | editar código-fonte]

Referências e Notas[editar | editar código-fonte]

  1. Homayoon Beigi (9 December 2011). Fundamentals of Speaker Recognition Springer [S.l.] p. 777. ISBN 978-0-387-77592-0. 
  2. Mark H. Holmes (5 December 2012). Introduction to Perturbation Methods Springer [S.l.] pp. 4–. ISBN 978-1-4614-5477-9. 
  3. Mohr, Austin. «Quantum Computing in Complexity Theory and Theory of Computation» (PDF). p. 2. Consultado em 7 June 2014. 
  4. a b Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition
  5. Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introduction to Algorithms Third ed. MIT [S.l.] p. 53. 
  6. Howell, Rodney. «On Asymptotic Notation with Multiple Variables» (PDF). Consultado em 2015-04-23. 
  7. N. G. de Bruijn (1958). Asymptotic Methods in Analysis (Amsterdam: North-Holland). pp. 5–7. ISBN 978-0-486-64221-5. 
  8. a b c Ronald Graham, Donald Knuth, and Oren Patashnik (1994). 0-201-55802-5 Concrete Mathematics Verifique |url= (Ajuda) 2 ed. (Reading, Massachusetts: Addison–Wesley). p. 446. ISBN 978-0-201-55802-9. 
  9. Donald Knuth (June–July 1998). «Teach Calculus with Big O» (PDF). Notices of the American Mathematical Society [S.l.: s.n.] 45 (6): 687.  (Unabridged version)
  10. a b G. H. Hardy and J. E. Littlewood, "Some problems of Diophantine approximation", Acta Mathematica 37 (1914), p. 225
  11. a b G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, vol. 41, 1916.
  12. a b c d e Donald Knuth. "Big Omicron and big Omega and big Theta", SIGACT News, Apr.-June 1976, 18-24.
  13. a b E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150.
  14. Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.
  15. E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
  16. Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6, p. 25
  17. Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig 1909, p.883.
  18. Erdelyi, A. (1956). Asymptotic Expansions [S.l.: s.n.] ISBN 978-0486603186. 
  19. See for instance "A new estimate for G(n) in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249-253. Translated in English in: Selected works / Ivan Matveevič Vinogradov ; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.

Leitura complementar[editar | editar código-fonte]

  • Paul Bachmann. Die Analytische Zahlentheorie. Zahlentheorie. pt. 2 Leipzig: B. G. Teubner, 1894.
  • Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen. 2 vols. Leipzig: B. G. Teubner, 1909.
  • G. H. Hardy. Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond, 1910.
  • Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison–Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp. 107–123.
  • Paul Vitanyi, Lambert Meertens, Big Omega versus the wild functions, Bull. European Association Theoret. Comput. Sci. (EATCS) 22(1984), 14-19. Also: ACM-SIGACT News, 16:4(1984) 56-59.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation, pp. 41–50.
  • Michael Sipser (1997). Introduction to the Theory of Computation PWS Publishing [S.l.] ISBN 0-534-94728-X.  Pages 226–228 of section 7.1: Measuring complexity.
  • Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
  • Paul E. Black, "big-O notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
  • Paul E. Black, "little-o notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
  • Paul E. Black, "Ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
  • Paul E. Black, "ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
  • Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.

Links externos[editar | editar código-fonte]

Wikilivros
O wikilivro Data Structures tem uma página sobre Big-O Notation