Grande-O
Na matemática, a notação O-grande descreve o comportamento limitante de uma 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, ou notação assintótica. Em ciência da computação, o O-grande é usado para classificar algoritmos pela forma como eles respondem a mudanças no tamanho da entrada. 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.
Imagem: Natalia Rivera from Bogota, Colombia · BY · Openverse
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:
Imagem: Gino Roncaglia from Roma, Italy · BY · Openverse
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: 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 e x4 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,
Imagem: .Capiro. · BY-NC-ND · Openverse
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
A notação O-grande é útil na análise de algoritmos por eficiência. Por exemplo, o tempo (ou o número de passos) que ele leva para resolver 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 algoritmo. Então a notação O-grande cobre o restante: podemos escrever tanto
Assintótico Infinitesimal
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, série 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.
Imagem: byb64 · BY-NC-SA · Openverse
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.
Imagem: Jody Art · BY-NC-ND · Openverse
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 f ( x → ) {\displaystyle f({\vec {x}})} e g ( x → ) {\displaystyle g({\vec {x}})} são duas funções definidas em um subconjunto de R n {\displaystyle \mathbb {R} ^{n}} . Nós dizemos que Equivalentemente, a condição em que x i ≥ M {\displaystyle x_{i}\geq M} para algum i {\displaystyle i} pode ser substituída pela condição em que ‖ x → ‖ ≥ M {\displaystyle \|{\vec {x}}\|\geq M} , onde ‖ x → ‖ {\displaystyle \|{\vec {x}}\|} denota a Distância de Chebyshev. Por exemplo, a sentença afirma que existem constantes C e M tal que Note que essa definição permite a todas as coordenadas de x → {\displaystyle {\vec {x}}} incrementar o infinito. Em particular, a sentença (i.e., ∃ C ∃ M ∀ n ∀ m … {\displaystyle \exists C\,\exists M\,\forall n\,\forall m\dots } ) é bem diferente de
Imagem: Sailko · BY · Openverse
Sinal de igualdade
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 é. 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)." 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. 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."
Outros operadores aritméticos
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, 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
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 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
Múltiplos usos
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 n → ∞ {\displaystyle n\to \infty } 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)
Imagem: byb64 · BY-NC-SA · Openverse
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. A sentença f ( n ) = O ( n ! ) {\displaystyle f(n)=O(n!)\,} é algumas vezes enfraquecida para f ( n ) = O ( n n ) {\displaystyle f(n)=O\left(n^{n}\right)} para derivar em fórmulas mais simples por complexidade assintótica. Para qualquer k > 0 {\displaystyle k>0} e c > 0 {\displaystyle c>0} , O ( n c ( log n ) k ) {\displaystyle O(n^{c}(\log n)^{k})} é um conjunto de O ( n c + ε ) {\displaystyle O(n^{c+\varepsilon })} para qualquer ε > 0 {\displaystyle \varepsilon >0} , então pode ser considerada como um polinomial com uma alta ordem.
Imagem: byb64 · BY-NC-SA · Openverse
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
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 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. 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 ∞).
Notação Omega-grande
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. Em 1914 G.H. Hardy e J.E. Littlewood introduziram o novo símbolo Ω {\displaystyle \Omega } , que é definido da seguinte forma: Assim f ( x ) = Ω ( g ( x ) ) {\displaystyle f(x)=\Omega (g(x))} é a negação de f ( x ) = o ( g ( x ) ) {\displaystyle f(x)=o(g(x))} .
Família de notações de Bachmann–Landau
f {\displaystyle f} não é dominada por g {\displaystyle g} assintoticamente f {\displaystyle f} é limitada por baixo por g {\displaystyle g} assintoticamente f ( n ) ≥ k ⋅ g ( n ) {\displaystyle f(n)\geq k\cdot g(n)} por infinitos valores de n e para algum k positivo f ( n ) ≥ k ⋅ g ( n ) {\displaystyle f(n)\geq k\cdot g(n)} para algum k positivo ∃ k > 0 ∀ n 0 ∃ n > n 0 f ( n ) ≥ k ⋅ g ( n ) {\displaystyle \exists k>0\;\forall n_{0}\;\exists n>n_{0}\;f(n)\geq k\cdot g(n)} ∃ k > 0 ∃ n 0 ∀ n > n 0 f ( n ) ≥ k ⋅ g ( n ) {\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)} k 1 ⋅ g ( n ) ≤ f ( n ) ≤ k 2 ⋅ g ( n ) {\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)}
Usos em ciência da computação
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). As afirmações equivalentes em português são respectivamente: Então apesar dessas 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. Neste caso, afirma-se o tempo que 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
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).
Imagem: AlexSlocker · BY-SA · Openverse
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).
Imagem: Francesco Bini · BY-SA · Openverse
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. O teórico dos números Edmund Landau a adotou, e foi assim inspirado a introduzir em 1909 a notação o; 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. O O-grande foi popularizado em ciência da computação por Donald Knuth, que reintroduziu as notações relacionadas Omega e Theta. Knuth também notou que a notação Omega foi introduzida por Hardy and Littlewood 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) 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 Ω R {\displaystyle \Omega _{R}} ("direita") e Ω L {\displaystyle \Omega _{L}} ("esquerda"), que foram introduzidos em 1918 por Hardy e Littlewood, e que foram precursores dos símbolos modernos Ω + {\displaystyle \Omega _{+}} ("não é menor que um o-pequeno de") e Ω − {\displaystyle \Omega _{-}} ("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".
