Em matemática , mais precisamente em análise , a comparação assintótica é um método que consiste em estudar a taxa de crescimento de uma função na vizinhança de um ponto ou no infinito, comparando-a com a de outra função considerada mais "Simples". Isso é frequentemente escolhido em uma escala de referência , geralmente contendo pelo menos certas funções assim chamadas elementares , em particular as somas e produtos de polinômios , exponenciais e logaritmos . As notações correspondentes são usadas em particular na física e na ciência da computação , por exemplo, para descrever a complexidade de certos algoritmos . Eles também são usados na teoria analítica dos números para avaliar com precisão o erro cometido ao substituir uma função irregular, como a contagem de números primos , por uma função da escala escolhida.
O método foi introduzido pelo trabalho de Paul du Bois-Reymond de 1872; para facilitar os cálculos e a apresentação dos resultados, várias notações foram desenvolvidas, em particular por Bachmann (1894), Landau (1909), Hardy (1910), Hardy e Littlewood (1914 e 1916) e Vinogradov ( c. 1930).
Vamos f e g seja as funções reais definidas pelas fórmulas
Por um estudo das duas funções, sabemos que g assume valores tão grandes quanto queremos na vizinhança do infinito, enquanto f só pode assumir valores entre 1 e 3. O quociente g dividido por f au vizinhança do infinito continua aumentando e não é limitado. Nesse contexto, podemos dizer que f é desprezível na frente de g , ou que g é preponderante na frente de f , na vizinhança do infinito, escrevemos (notação de Landau):
ou (notação de Hardy, obsoleta)
A notação de Hardy permite encadear as relações de preponderância, por exemplo:
Definição formal quando a função g não desaparecePara definir formalmente essa propriedade, consideramos o comportamento do quociente .
É
Vamos f e g seja duas funções da variável real x . Assumimos que g não desaparece em uma vizinhança de a . Dizemos que f é desprezível na frente de g , ou que g é preponderante na frente de f em a , e notamos , quando
Se o contexto for claro, não se especifica o campo de estudo e se nota :, até . No entanto, a notação é sempre associado a um lugar um eo bairro de este lugar: ser insignificante é um conceito locais .
Nesta notação Landau (às vezes também ), o símbolo é o pequeno o . A notação equivalente de Hardy é . Hoje usamos exclusivamente a notação Landau.
PropriedadesPor abuso de linguagem, realiza-se “operações” no “o minúsculo” , ou seja, nos desprezíveis. Na verdade, podemos dizer que:
Qualquer um .
Vamos f e g seja duas funções da variável real x . Assumimos que g não desaparece em uma vizinhança de a . Dizemos que f é equivalente a g em um , ou que g é equivalente a f em um , e denotamos
, quando .Exemplo
A grande notação O de Landau denota o caráter dominado de uma função sobre a outra.
Normalmente, como Paul Bachmann que introduziu este símbolo em 1894, usamos a letra maiúscula O (do Ordnung alemão , "ordem"). Foi muito mais tarde (1976), por analogia com o símbolo omega maiúsculo Ω (veja abaixo), que Donald Knuth propôs renomear o símbolo O com o nome da letra omicron maiúscula, sendo este último raramente desenhado dessa forma. diferente de O. Em ambos os casos, o símbolo usado é diferente do símbolo 0 (zero)
Definição formalVamos f e g seja duas funções da variável real x . Dizemos que f é dominado por g em + ∞ , ou que g domina f em + ∞ , e denotamos (notação de Bachmann, 1894, ou Landau, 1909)
ou (notação de Hardy, 1910, obsoleto)
ou novamente (notação de Vinogradov, 1930)
quando existem constantes N e C tais que
Intuitivamente, isso significa que f não cresce mais rápido do que g .
Da mesma forma, se a é um número real, escrevemos
se houver constantes d > 0 e C tais que
ExemplosEm 1914, Hardy e Littlewood introduziram o novo símbolo Ω definido como segue:
.O funções f e g são assumidos como definido, e g positiva, numa vizinhança de infinito. Assim é a negação de .
Em 1916, os mesmos autores introduziram os dois novos símbolos Ω R e Ω L , definidos da seguinte forma:
; .Como antes, as funções f e g são assumidos como definido, e g positiva, numa vizinhança de infinito. Assim, é a negação de , e a negação de .
Ao contrário do que DE Knuth afirmaria mais tarde , Edmund Landau também usou esses três símbolos em 1924.
Essas notações de Hardy e Littlewood são protótipos que, depois de Landau, parecem nunca ter sido usados como tal: Ω R tornou-se Ω + e Ω L tornou-se Ω - .
Esses três símbolos são agora comumente usados na teoria analítica dos números , bem como para significar que as condições e ambas foram satisfeitas.
É claro que em cada uma dessas definições podemos substituir ∞ por –∞ ou por um número real.
Nós temos
e mais precisamente,
Nós temos
e mais precisamente,
Contudo,
É importante ressaltar o fato de que a escrita
tem duas definições incompatíveis em matemática, ambas muito difundidas, uma em teoria analítica dos números , que acabamos de apresentar, a outra em teoria da complexidade dos algoritmos . Quando essas duas disciplinas se encontram, é provável que essa situação crie uma grande confusão.
Em 1976, Knuth publicou um artigo cujo objetivo principal era justificar o uso do mesmo símbolo Ω para descrever uma propriedade diferente da descrita por Hardy e Littlewood. Ele tenta convencer o leitor de que a definição de Hardy e Littlewood quase nunca é usada (o que, mesmo em 1976, já estava errado há 25 anos). Ele chega a afirmar que Landau nunca o usou (o que também é falso). Ele sente imperativamente a necessidade de outra noção ( “ Para todas as aplicações que vi até agora na ciência da computação, um requisito mais forte [...] é muito mais apropriado ” ), e decidiu que o uso do símbolo Ω deve ser reservado para descrever isto. Ele está fortemente chateado com a antiga definição ( “ Infelizmente, Hardy e Littlewood não definiram Ω ( f ( n )) como eu queria ” ).
Ele, portanto, corre o risco de criar confusão e define
.Em matemática, muitas vezes é importante ficar de olho no termo de erro de uma aproximação. Esta notação é particularmente usada ao lidar com desenvolvimentos limitados e cálculos de equivalentes. Por exemplo, a expansão da função exponencial para a ordem 2 também pode ser escrita:
expressar o fato de que o erro, a diferença , é desprezível antes de quando tende a 0.
Deve-se notar que o número de operandos neste tipo de escrita deve ser limitado por uma constante que não depende da variável: por exemplo, a afirmação é obviamente falsa se as reticências ocultam um número de termos que não são limitados quando x varia.
Aqui está uma lista de categorias de funções comumente usadas na análise. A variável (observada aqui n ) tende a + ∞ e c é uma constante real arbitrária. Quando c é uma constante maior que 1, as funções aparecem nesta lista em ordem crescente de magnitude.
Avaliação | tamanho no máximo | |
O (1) | módulo aumentado por uma constante | |
O (log ( n )) | logarítmico | |
O ((log ( n )) c ) | ( polilogarítmico se c for inteiro positivo) | |
O ( n ) | linear | |
O ( n log ( n )) | às vezes chamado de " linear " | |
O ( n log c (n) ) | às vezes chamado de " quase linear " | |
O ( n 2 ) | quadrático | |
S ( n c ) | ( polinômio se c for inteiro positivo) | |
O ( c n ) | ( exponencial se c for positivo, às vezes " geométrico ") | |
O ( n! ) | fatorial |
O ( n c ) e O ( c n ) são muito diferentes. O último permite um crescimento muito mais rápido, e isso para qualquer constante c > 1. Uma função que aumenta mais rápido do que qualquer polinômio é considerada superpolinomial . Uma função que cresce mais lentamente do que qualquer exponencial é considerada subexponencial . Existem funções superpolinomiais e subexponenciais, como a função n log ( n ) .
Observe também que O (log n ) é exatamente igual a O (log ( n c )), uma vez que esses dois logaritmos são múltiplos um do outro por um fator constante e que a notação grande O “ignora” as constantes multiplicativas. Da mesma forma, os logaritmos em diferentes bases constantes são equivalentes.
A lista anterior é útil devido à seguinte propriedade: se uma função f é uma soma de funções , e se uma das funções da soma cresce mais rápido do que as outras, então ela determina a ordem de crescimento de f ( n ).
Exemplo:
se f ( n ) = 10 log ( n ) + 5 (log ( n )) 3 + 7 n + 3 n 2 + 6 n 3 ,Essa notação também pode ser usada com funções de várias variáveis:
Escrevendo : | quando |
corresponde à proposição: |
Para alguns, essa notação abusa do símbolo de igualdade, pois parece violar o axioma da igualdade : "coisas iguais são iguais entre si" (em outras palavras, com esta notação, igualdade n 'é mais uma equivalência relação ). Mas também podemos considerar que na escrita
a notação "= O" designa um único operador, em cuja escrita o sinal "=" não tem existência própria independente (e em particular não designa uma relação de equivalência). Nesse caso, não há mais abuso de classificação, mas obviamente ainda há risco de confusão. Também é possível definir O ( g ( x )) como um conjunto de funções, cujos elementos são todas funções que não crescem mais rápido do que g , e usar notações de conjunto para indicar se uma determinada função é um elemento do conjunto, portanto definiram. Por exemplo :
Ambos os acordos são comumente usados, mas o primeiro (e mais antigo) é até o início do XXI th mais frequentemente encontrados século. Para evitar esse problema, usamos (com a mesma freqüência) a notação Vinogradov (veja abaixo).
Outro problema é que é necessário indicar claramente a variável contra a qual o comportamento assintótico é examinado. Uma afirmação como não tem o mesmo significado dependendo se é seguida por “quando ” ou, por exemplo, por “(para qualquer fixo) quando ”.
Avaliação | Sobrenome | Descrição informal | Quando , de uma certa posição ... | Definição rigorosa |
---|---|---|---|---|
ou
|
Grand O (Grand Omicron) |
A função | f | é limitado pela função | g | assintoticamente, exceto |
para a k > 0 | |
ou
|
Omega Grande |
Duas definições:
Na teoria dos números: |
Na teoria dos números: para a k > 0 |
Na teoria dos números:
|
Na teoria do algoritmo:
f é subestimado por g (até um fator) |
Na teoria do algoritmo:
para a k > 0 |
Na teoria do algoritmo:
|
||
da ordem de; Grande teta |
f é dominado e sujeito a g assintoticamente |
para a k 1 > 0 e a k 2 > 0 |
|
|
ou
|
O pequeno | f é insignificante na frente de g assintoticamente | , qualquer que seja > 0 (fixo). | |
Omega Pequeno | f domina g assintoticamente | para todos k > 0 | ||
equivalente a | f é aproximadamente igual ag assintoticamente | , qualquer que seja > 0 (fixo). |
Depois de grand-O, as notações Θ e Ω são as mais usadas em ciência da computação; o minúsculo é comum na matemática, mas mais raro na ciência da computação. O ω é pouco utilizado.
Outra notação às vezes usada na ciência da computação é Õ ( soft-O em inglês) que significa big-o até um fator polilogarítmico.
Na teoria dos números, a notação f ( x ) g ( x ) tem o mesmo significado que f ( x ) = Θ ( g ( x )) (que não é usado).
As notações de Landau em homenagem ao matemático alemão especializado em teoria dos números Edmund Landau que usou o símbolo O , originalmente introduzido por Paul Bachmann , e foi inspirado a inventar o símbolo o . Ele só usou o símbolo Ω em um artigo em 1924, para significar ≠ o ; esta notação foi introduzida (com o mesmo significado) em 1914 por GH Hardy e JE Littlewood; Desde então, Ω é comumente usado na teoria dos números, mas exclusivamente neste mesmo sentido, e nunca no primeiro sentido mostrado na tabela acima. No mesmo artigo, Landau usa os símbolos Ω R e Ω L , também devido a Hardy e Littlewood, (e desde então denotado Ω + e Ω - ) para significar , respectivamente . Claro, ele também usa a notação ∼, mas nunca ω ou Θ.
As notações de Hardy et , introduzidas por GH Hardy em seu tratado de Ordens do Infinito de 1910 , desempenham o mesmo papel que as de Landau para a comparação assintótica de funções.
Na notação Landau, podemos defini-los da seguinte forma:
e
As classificações de Hardy estão desatualizadas. Hardy abandonou rapidamente suas próprias classificações; ele usa as notações de Landau em todos os seus artigos (quase 400!) e em seus livros, exceto em seu tratado de 1910 e em 3 artigos (1910-1913). Podemos notar que se Hardy introduziu em seu tratado de 1910 alguns outros símbolos para a comparação assintótica de funções, ele nunca definiu ou usou a notação (ou ), que devemos a Vinogradov.
O teórico dos números russo Ivan Matveyevich Vinogradov introduziu na década de 1930 a notação que leva seu nome,
.A notação ≪ de Vinogradov é comumente usada na teoria dos números em vez de O ; às vezes, até as duas notações são usadas alternadamente no mesmo artigo.
Em 1982, Carl Pomerance introduziu uma nova notação para abreviar as funções complexas envolvidas no estudo assintótico da complexidade dos algoritmos . Assim, por exemplo, uma função f pertence à classe se tivermos ; o exponencial “separa” as funções o suficiente para que não seja possível reduzir essa notação à forma, por exemplo.
As classificações de Landau, em particular, levam a abusos de classificação muito frequentes, como escrita ou pior ; esta segunda notação deve ser lida usando uma linguagem definida: chamando o conjunto de funções desprezíveis em relação a e o conjunto de diferenças de duas funções de , isso significa que . De maneira mais geral, esse abuso de notação equivale a considerar a notação (ou , etc.) como representando uma classe de funções e como um significado que pertence a essa classe.
(pt) Big-O Cheat Sheet , um site que lista uma classificação de complexidades algorítmicas por domínio.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">