Notação L – Wikipédia, a enciclopédia livre
A notação L é uma notação assintótica análoga à notação O grande, denotada como para uma variável limitada tendendo ao infinito. Como a notação O grande, geralmente é usada para transmitir aproximadamente a complexidade computacional de um algoritmo específico.
Definição
[editar | editar código-fonte]Ela está definida como
- onde c é uma constante positiva e é uma constante .
A notação L é usada principalmente na teoria computacional dos números, para expressar a complexidade de algoritmos para problemas difíceis da teoria dos números, por ex. peneiras para fatoração de inteiros e métodos para resolver logaritmos discretos. O benefício dessa notação é que ela simplifica a análise desses algoritmos.
expressa o termo dominante, e cuida de tudo menor.
Quando 0, então
é uma função polinomial de ln n;
Quando é 1, então
é uma função totalmente exponencial de ln n (e, portanto, polinomial em n).
Se estiver entre 0 e 1, a função é subexponencial de ln n (e superpolinomial).
Exemplos
[editar | editar código-fonte]Muitos algoritmos de fatoração de inteiros de propósito geral têm complexidades temporais subexponenciais. O melhor é a peneira de campo de número geral, que tem um tempo de execução esperado de
para . O melhor algoritmo antes da peneira de campo numérico era a peneira quadrática que tem tempo de execução
Para o problema de logaritmo discreto de curva elíptica, o algoritmo de propósito geral mais rápido é o algoritmo passo de bebê passo gigante, que tem um tempo de execução na ordem da raiz quadrada da ordem n. Em notação L, isso seria
A existência do teste de primalidade AKS, que é executado em tempo polinomial, significa que a complexidade de tempo para o teste de primalidade é conhecida como sendo no máximo
onde c foi provado ser no máximo 6.[1]
História
[editar | editar código-fonte]A notação L foi definida de várias formas na literatura. O primeiro uso dela veio de Carl Pomerance em seu artigo "Análise e comparação de alguns algoritmos de fatoração de inteiros".[2] Esta forma tinha apenas o parâmetro : o na fórmula era para os algoritmos que ele estava analisando. Pomerance estava usando a letra (ou minúscula ) neste trabalho e em trabalhos anteriores para fórmulas que envolviam muitos logaritmos.
A fórmula acima envolvendo dois parâmetros foi introduzida por Arjen Lenstra e Hendrik Lenstra em seu artigo sobre "algoritmos na teoria dos números".[3] Foi introduzido na análise de um algoritmo de logaritmo discreto de Coppersmith. Esta é a forma mais comumente usada na literatura hoje.
O manual de criptografia aplicada define a notação L com um grande em torno da fórmula apresentada neste artigo.[4] Esta não é a definição padrão. O grande sugere que o tempo de execução é um limite superior. No entanto, para os algoritmos de fatoração de inteiros e logaritmos discretos para os quais a notação L é comumente usada, o tempo de execução não é um limite superior, portanto, essa definição não é preferida.
Referências
[editar | editar código-fonte]- ↑ Hendrik W. Lenstra Jr. e Carl Pomerance, "Teste de primalidade com períodos gaussianoss", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
- ↑ Carl Pomerance, "Análise e comparação de alguns algoritmos de fatoração inteira", em métodos computacionais na teoria dos números mathematisch centrum, parte 1, páginas 89 à 139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf (em inglês).
- ↑ Arjen K. Lenstra e Hendrik W. Lenstra, Jr, "Algoritmos na teoria dos números", no manual de ciência da computação teórica (volume A): Algoritmos e complexidade, 1991 (em inglês).
- ↑ Alfred J. Menezes, Paul C. van Oorschot e Scott A. Vanstone. Manual de criptografia aplicada. CRC Press, 1996. ISBN 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/ (em inglês).