Grande-O
A notação O-grande é uma ferramenta matemática essencial para descrever o comportamento assintótico de funções, ou seja, como elas se comportam quando seus argumentos se tornam muito grandes ou se aproximam de um valor específico. Parte da família de notações de Landau, ela é amplamente utilizada em ciência da computação para classificar algoritmos com base em sua resposta a mudanças no tamanho da entrada. Na teoria analítica dos números, ajuda a estimar o "erro" ao aproximar funções aritméticas por seus valores assintóticos. Um exemplo notável é sua aplicação na estimativa do termo restante no teorema do número primo.
Pontos-chave
- A notação O-grande descreve o comportamento limitante de funções, especialmente em relação a argumentos grandes ou próximos a um valor.
- É uma das notações Landau, também conhecidas como notações Bachmann–Landau ou assintóticas.
- Em ciência da computação, classifica algoritmos pela sua eficiência em relação ao tamanho da entrada.
- Na teoria analítica dos números, estima o erro em aproximações assintóticas de funções.
- A notação f(x) = O(g(x)) significa que f(x) é no máximo M vezes g(x) para x suficientemente grande, onde M é uma constante positiva.
Imagem: Natalia Rivera from Bogota, Colombia · BY · Openverse
A notação O-grande, f(x) = O(g(x)), é definida formalmente para descrever o limite superior do crescimento de uma função f em relação a outra função g. Isso significa que existe uma constante positiva M e um valor x0 tal que, para todo x maior que x0, o valor absoluto de f(x) é menor ou igual a M vezes o valor absoluto de g(x). A premissa de que estamos interessados na taxa de crescimento quando x tende ao infinito é frequentemente implícita. A notação também pode ser usada para descrever o comportamento de f perto de um número real 'a', onde existem constantes positivas δ e M tais que, para x suficientemente próximo de 'a', o valor absoluto de f(x) é no máximo M vezes o valor absoluto de g(x).
Imagem: Gino Roncaglia from Roma, Italy · BY · Openverse
Na prática, a definição formal da notação O-grande raramente é usada diretamente. Em vez disso, aplicam-se regras de simplificação para determinar a notação O de uma função. Por exemplo, para a função f(x) = 6x⁴ − 2x³ + 5, que é a soma de três termos, o termo com a maior taxa de crescimento é 6x⁴, pois possui o maior expoente de x. Ao omitir o fator constante (6), a forma simplificada se torna x⁴. Assim, dizemos que f(x) é um 'O-grande' de (x⁴), ou matematicamente, f(x) = O(x⁴). Este cálculo pode ser confirmado pela definição formal, onde para f(x) = 6x⁴ − 2x³ + 5 e g(x) = x⁴, a afirmação f(x) = O(x⁴) é equivalente à sua expansão formal.
Imagem: .Capiro. · BY-NC-ND · Openverse
A notação O-grande tem duas grandes áreas de aplicação: na matemática, para descrever a proximidade de uma série finita a uma função (como em séries de Taylor truncadas), e em ciência da computação, para analisar a eficiência de algoritmos. Em ambas as áreas, a função g(x) dentro de O(...) é geralmente a mais simples possível, sem fatores constantes ou termos de baixa ordem. Existem dois usos formalmente semelhantes, mas contextualmente diferentes: comportamento assintótico no infinito e comportamento assintótico infinitesimal, com a distinção ocorrendo apenas na aplicação, não no princípio formal da definição.
Comportamento Assintótico no Infinito
A notação O-grande é crucial na análise de algoritmos para avaliar sua eficiência. Por exemplo, se o tempo de execução de um algoritmo para um problema de tamanho 'n' é T(n) = 4n² − 2n + 2, à medida que 'n' cresce, o termo n² dominará. Os outros termos podem ser negligenciados, pois seu impacto se torna insignificante. Coeficientes constantes também se tornam irrelevantes em comparação com ordens de expressão maiores. Por exemplo, se T(n) = 1.000.000n², mas U(n) = n³, U(n) será superior a T(n) para n > 1.000.000. Além disso, a notação O-grande abstrai as variações de desempenho entre diferentes máquinas, que geralmente diferem apenas por um fator constante no número de passos. Assim, podemos expressar a complexidade como T(n) = O(n²).
Comportamento Assintótico Infinitesimal
A notação O-grande também é empregada para descrever o termo de erro em aproximações de funções matemáticas. Os termos mais significativos são explicitamente escritos, e os termos menos significativos são resumidos em um único termo O-grande. Por exemplo, na série exponencial, eˣ = 1 + x + x²/2 + O(x³), para x pequeno. A notação O(x³) indica que o valor absoluto do erro (eˣ − (1 + x + x²/2)) é menor do que uma constante vezes |x³| quando x está suficientemente próximo de 0.
Imagem: byb64 · BY-NC-SA · Openverse
Quando uma função f é uma soma finita de outras funções, a que cresce mais rapidamente determina a ordem de f(n). Por exemplo, O(n²) + O(n³) = O(n³). Se uma função pode ser limitada por um polinômio em n, termos de baixa ordem podem ser desprezados quando n tende ao infinito. É importante notar que O(nᶜ) e O(cⁿ) são muito diferentes; se c > 1, cⁿ cresce muito mais rápido. Funções que crescem mais rápido que nᶜ para qualquer c são superpolinomiais, e as que crescem mais devagar que cⁿ são subexponenciais. Algoritmos podem ser superpolinomiais e subexponenciais, como os mais rápidos para fatoração de inteiros. Potências de n dentro de logaritmos podem ser ignoradas, pois O(log n) é o mesmo que O(log(nᶜ)), já que log(nᶜ) = c log n, e a notação O-grande ignora fatores constantes. Similarmente, logaritmos com bases diferentes são equivalentes. No entanto, exponenciais com bases diferentes não são da mesma ordem (ex: 2ⁿ e 3ⁿ).
Imagem: byb64 · BY-NC-SA · Openverse
A notação O-grande (e o-pequeno, Ω) pode ser estendida para funções com múltiplas variáveis. Formalmente, para funções f(x⃗) e g(x⃗) definidas em um subconjunto de ℝⁿ, dizemos que f(x⃗) = O(g(x⃗)) se existirem constantes positivas M e um vetor x⃗₀ tal que, para todos os x⃗ onde cada coordenada xᵢ ≥ x₀ᵢ, o valor absoluto de f(x⃗) é menor ou igual a M vezes o valor absoluto de g(x⃗). Alternativamente, a condição pode ser substituída por ||x⃗|| ≥ M, onde ||x⃗|| é a distância de Chebyshev. Essa definição permite que todas as coordenadas de x⃗ tendam ao infinito. É crucial notar que a ordem dos quantificadores (∃ C ∃ M ∀ n ∀ m … versus ∃ C ∀ n ∃ M ∀ m …) faz uma diferença significativa no significado da afirmação.
Imagem: Sailko · BY · Openverse
A forma como a notação O-grande é escrita e interpretada levanta algumas questões importantes, especialmente em relação ao uso do sinal de igualdade e sua combinação com outros operadores aritméticos. Essas convenções, embora úteis, podem ser consideradas um 'abuso de notação' por alguns matemáticos.
O Uso do Sinal de Igualdade
A expressão "f(x) é O(g(x))" é frequentemente escrita como f(x) = O(g(x)). Alguns consideram isso um abuso de notação, pois o sinal de igualdade sugere uma simetria que não existe (O(x) = O(x²) é verdadeiro, mas O(x²) = O(x) não é). Knuth chama isso de "igualdades de caminho único", alertando para deduções ridículas se a simetria fosse assumida. Seria mais preciso usar a notação de conjuntos, escrevendo f(x) ∈ O(g(x)), onde O(g(x)) representa a classe de funções h(x) tais que |h(x)| ≤ C|g(x)| para alguma constante C. No entanto, o uso do sinal de igual é habitual, como Knuth observou, "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."
Combinação com Outros Operadores Aritméticos
A notação O-grande pode ser combinada com outros operadores aritméticos em equações mais complexas. Por exemplo, h(x) + O(f(x)) denota a coleção de funções que crescem como h(x) mais uma parte cujo crescimento é limitado por f(x). Assim, h(x) + O(f(x)) = O(g(x)) significa que para qualquer função k(x) ∈ O(f(x)), a função h(x) + k(x) ∈ O(g(x)). Isso é útil na análise de algoritmos. Se um algoritmo tem uma sub-rotina de ordenação com complexidade O(n²) e depois executa 55n³ + 2n + 10 passos adicionais, sua complexidade total pode ser expressa como T(n) = 55n³ + O(n²). Aqui, os termos 2n+10 são subsumidos pelo crescimento mais rápido O(n²). Essa utilização também desconsidera alguns significados formais do símbolo "=", mas serve como um marcador de posição conveniente.
Declaração Explícita de Variáveis
Em contextos com múltiplas variáveis, os argumentos da função na notação O-grande podem precisar ser inferidos do contexto. Por exemplo, O(m) e O(n) podem ter significados radicalmente diferentes. O(m) pode indicar crescimento polinomial em 'm', enquanto O(n) (assumindo n > 1) pode indicar crescimento exponencial em 'n'. Para evitar confusão, alguns autores usam notações mais explícitas, como O(f(n)) ou O(f(n, m)).
Múltiplos Usos em Equações
Em sua forma mais complexa, a notação O(...) pode aparecer em vários lugares de uma equação, inclusive em ambos os lados. Por exemplo, O(1) = O(eⁿ) para n → ∞. O significado dessas afirmações é que para quaisquer funções que satisfaçam cada O(...) no lado esquerdo, existem algumas que satisfazem O(...) no lado direito, de modo que, ao substituir todas essas funções na equação, os dois lados são iguais. Em termos de notação de conjuntos, isso significa 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 não é uma relação simétrica, ao contrário do uso comum do "=". Assim, nO(1) = O(eⁿ) não implica na afirmação falsa O(eⁿ) = nO(1).
Imagem: Jody Art · BY-NC-ND · Openverse
Esta seção lista classes de funções frequentemente encontradas na análise da complexidade de tempo de execução de algoritmos, organizadas geralmente da mais lenta para a mais rápida. Em todos os casos, 'c' é uma constante e 'n' cresce indefinidamente. A afirmação f(n) = O(n!) é às vezes simplificada para f(n) = O(nⁿ) para derivar fórmulas de complexidade assintótica mais simples. Para quaisquer k > 0 e c > 0, O(nᶜ(log n)ᵏ) é um subconjunto de O(nᶜ⁺ᵋ) para qualquer ε > 0, podendo ser considerado um polinômio de ordem ligeiramente superior.
Imagem: Francesco Bini · BY-SA · Openverse
Embora a notação O-grande seja a mais comum para comparar funções assintoticamente, em muitos casos, a notação Theta-grande (Θ) pode oferecer limites mais precisos. Esta seção define outras notações relacionadas que fazem parte da família de notações de Bachmann-Landau.
Notação o-pequeno (o)
A notação o-pequeno, f(x) = o(g(x)), significa intuitivamente que g(x) cresce muito mais rápido que f(x), ou que o crescimento de f(x) é insignificante comparado ao de g(x). Formalmente, f(n) = o(g(n)) quando n → ∞ significa que para toda constante positiva ε, existe uma constante N tal que |f(n)| ≤ ε|g(n)| para todo n > N. A diferença crucial para a notação O-grande é que o-pequeno deve ser verdadeiro para *todas* as constantes positivas ε, mesmo as muito pequenas, enquanto O-grande exige que seja verdadeiro para *pelo menos uma* constante M. Assim, o-pequeno faz uma afirmação mais forte: toda função que é o-pequeno de g também é O-grande de g, mas o inverso não é sempre verdadeiro (a própria g não é o-pequeno de g, a menos que seja identicamente zero perto do infinito).
Notação Omega-grande (Ω)
Existem duas definições generalizadas e incompatíveis para a afirmação f(x) = Ω(g(x)). A primeira, cronologicamente, é usada na teoria analítica dos números, e a segunda, na teoria da complexidade computacional. Essa dualidade frequentemente causa confusão. Em 1914, G.H. Hardy e J.E. Littlewood introduziram o símbolo Ω, definido como a negação de f(x) = o(g(x)). Isso significa que f(x) = Ω(g(x)) se e somente se o limite superior de |f(x)/g(x)| quando x tende a 'a' é maior que zero. A definição de Knuth, que é mais comum em ciência da computação, define f(n) = Ω(g(n)) se existirem constantes positivas C e N₀ tais que |f(n)| ≥ C|g(n)| para todo n > N₀.
Família de Notações de Bachmann–Landau
A família de notações de Bachmann–Landau inclui várias formas de descrever o comportamento assintótico de funções: - f = o(g): f é dominada por g assintoticamente (f cresce muito mais devagar que g). - f = O(g): f é limitada por cima por g assintoticamente (f cresce no máximo tão rápido quanto g). - f = ω(g): f domina g assintoticamente (f cresce muito mais rápido que g). - f = Ω(g): f é limitada por baixo por g assintoticamente (f cresce no mínimo tão rápido quanto g). - f = Θ(g): f é limitada por cima e por baixo por g assintoticamente (f e g crescem na mesma taxa). Essas notações descrevem diferentes tipos de relações de crescimento entre funções, com definições formais que envolvem limites e constantes para valores suficientemente grandes da variável.
Usos em Ciência da Computação
Em ciência da computação, a notação O-grande é frequentemente usada de forma um tanto informal para descrever um limite assintótico apertado, mesmo quando a notação Theta-grande (Θ) seria mais precisa. Por exemplo, para T(n) = 73n³ + 22n² + 58, todas as afirmações T(n) = O(n⁴), T(n) = O(n³), e T(n) = Θ(n³) são consideradas corretas. No entanto, os limites mais apertados (O(n³) e Θ(n³)) são fortemente preferíveis aos limites mais frouxos (O(n⁴)), pois fornecem mais informação. Embora Θ(n³) seja o mais informativo, em alguns campos, O(n³) é mais comum, especialmente quando os desenvolvedores de um algoritmo querem apenas indicar um limite superior assintótico para o tempo de execução, sem fazer uma afirmação explícita sobre o limite inferior.
Extensão da Notação de Bachmann–Landau: O-suave (Õ)
Uma extensão da notação de Bachmann–Landau, às vezes usada em ciência da computação, é a notação O-suave (Õ), lida como 'O-til'. f(n) = Õ(g(n)) é uma abreviação para f(n) = O(g(n) logᵏ g(n)) para algum k. Essencialmente, ela é a notação O-grande que ignora fatores logarítmicos. Isso ocorre porque os efeitos da taxa de crescimento de funções super-logarítmicas são geralmente mais importantes para prever o desempenho em grandes entradas do que os efeitos de alta granularidade contribuídos por fatores logarítmicos. Essa notação é útil para evitar discussões excessivamente rigorosas sobre taxas de crescimento que podem ser consideradas muito restritivas para os assuntos em questão, já que logᵏ n é sempre o(nᵋ) para qualquer constante k e qualquer ε > 0.
Imagem: AlexSlocker · BY-SA · Openverse
A notação O-grande pode ser generalizada para funções com valores em qualquer espaço vetorial normalizado, substituindo valores absolutos por normas. F e G não precisam tomar seus valores no mesmo espaço. Também é possível generalizar para funções G que tomam valores em qualquer grupo topológico. O 'processo de limitação' x→x₀ pode ser generalizado pela introdução de um filtro arbitrário, aplicável a sequências generalizadas direcionadas f e g. A notação o-pequeno pode ser usada para definir derivadas e diferenciabilidade em espaços bastante gerais, bem como a equivalência (assintótica) de funções, que é uma relação de equivalência e uma noção mais restritiva que a relação 'f é Θ(g)'. Por exemplo, 2x é Θ(x), mas 2x − x não é o(x).
Imagem: byb64 · BY-NC-SA · Openverse
O símbolo O foi introduzido em 1894 por Paul Bachmann em seu livro 'Analytische Zahlentheorie'. Edmund Landau o adotou e, em 1909, introduziu a notação o, o que levou a ambas serem conhecidas como símbolos de Landau. Essas notações foram aplicadas em matemática na década de 1950 para análise assintótica. Em ciência da computação, Donald Knuth popularizou o O-grande e reintroduziu as notações relacionadas Omega (Ω) e Theta (Θ). Knuth notou que Hardy e Littlewood já haviam introduzido Omega com um significado diferente ('≠o', ou 'não é um o de') e propôs a definição atual. A definição original de Hardy e Littlewood ainda é usada na teoria dos números. Landau também utilizou em 1924 os símbolos Ωᵣ ('direita') e Ωₗ ('esquerda'), introduzidos em 1918 por Hardy e Littlewood, precursores dos símbolos modernos Ω₊ ('não é menor que um o-pequeno de') e Ω₋ ('não é maior que um o-pequeno de'). Por isso, os símbolos Omega (em seus significados originais) são às vezes referenciados como 'símbolos de Landau'.
