A notação L é uma notação assintótica análoga à notação Big O, denotada como para uma variável tendendo ao infinito. Assim como a notação Big O, ela é geralmente usada para transmitir de forma aproximada a taxa de crescimento de uma função, como a complexidade computacional de um algoritmo específico.
Definição É definida como:
onde é uma constante positiva e é uma constante no intervalo .
A notação L é usada principalmente na teoria computacional dos números para expressar a complexidade de algoritmos voltados a problemas difíceis da teoria dos números, como crivos para fatoração de inteiros e métodos para resolver logaritmos discretos. O benefício desta notação é que ela simplifica a análise desses algoritmos. O termo expressa o termo dominante, enquanto o termo engloba os fatores de menor ordem.
Quando :
é uma função polilogarítmica (uma função polinomial de ).
Quando :
é uma função exponencial completa de (e, portanto, polinomial em ).
Se estiver entre e , a função é subexponencial em relação a (e superpolinomial).
Exemplos Muitos algoritmos de fatoração de inteiros de propósito geral possuem complexidade temporal subexponencial. O mais eficiente conhecido é o Crivo do corpo de números generalizado, que possui tempo de execução esperado de:
para .
Antes do crivo do corpo de números generalizado, o algoritmo mais rápido era o Crivo quadrático, com tempo de execução:
O terceiro método de fatoração mais rápido conhecido é a Fatoração por curva elíptica de Lenstra, cujo tempo de execução é:
Para o problema do logaritmo discreto em curva elíptica, o algoritmo de propósito geral mais rápido é o Algoritmo passo de bebê, passo de gigante, que possui tempo de execução da ordem da raiz quadrada da ordem do grupo . Em notação L, isso corresponde a:
A existência do teste de primalidade AKS, executado em tempo polinomial, demonstra que a complexidade de tempo para o teste de primalidade é limitada superiormente por:
onde demonstrou-se que .Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
História
A notação L foi definida sob diferentes formas na literatura. O primeiro uso partiu de Carl Pomerance em seu artigo "Analysis and comparison of some integer factoring algorithms".Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf Essa versão utilizava apenas o parâmetro , enquanto o parâmetro na fórmula assumia o valor fixo de para os algoritmos analisados. Pomerance vinha empregando a letra (ou minúscula ) em trabalhos anteriores para fórmulas com múltiplos logaritmos.
A fórmula com dois parâmetros foi introduzida por Arjen Lenstra e Hendrik Lenstra no artigo "Algorithms in Number Theory".Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991. O formato surgiu durante a análise de um algoritmo para logaritmo discreto proposto por Don Coppersmith, tornando-se a representação padrão na literatura moderna.
O Handbook of Applied Cryptography define a notação L adicionando uma notação Big O () em torno da fórmula.Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. . http://www.cacr.math.uwaterloo.ca/hac/. Essa variação não constitui a definição padrão; a inclusão do Big O indicaria que o tempo de execução é estritamente um limite superior. No entanto, para os algoritmos de fatoração de inteiros e logaritmo discreto aos quais a notação é aplicada, o tempo representa uma estimativa precisa do tempo esperado, motivo pelo qual essa forma não é a preferida.
Referências
Categoria:Análise assintótica Categoria:Teoria da complexidade computacional