L-нотація — асимптотична нотація, аналогічна до О-нотації, записується як при , що прямує до нескінченності. Подібно до O-нотації, L-нотація зазвичай застосовується для оцінки обчислювальної складності алгоритмів. При цьому є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, кількість вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага L-нотації над O-нотацією полягає в тому, що вона спрощує аналіз алгоритмів.
Визначення Нехай , тоді
Множник виражає домінуючу складову, а множник — другорядну, яка зростає повільніше.
При є поліномом від .
При є експонентою від (і також поліномом від ).
При є субекспоненційною, тобто росте повільніше, ніж експонента з основою, більшою за 1, але швидше за будь-який поліном від .
Історія Першим застосував L-нотацію у своїй праці «Аналіз та порівняння деяких алгоритмів факторизації цілих чисел». Для алгоритмів, які він аналізував, нотація мала лише один параметр , а була константою, рівною . Померанс уживав літеру (або малу літеру ) у цій та попередніх статтях для формул, які містили багато логарифмів.
Формулу, яка містить два параметри, запровадили та у своїй статті «Алгоритми в теорії чисел»Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.. Таку нотацію вони застосували для аналізу алгоритму Копперсміта обчислення дискретного логарифма. Їхня форма нотації частіше трапляється в сучасній літературі.
У літературі з криптографії трапляється визначення L-нотації через O-велике: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/.
Це не стандартне визначення. O-нотація передбачає, що час роботи обмежений функцією зверху. Однак для алгоритмів, де зазвичай застосовується L-нотація (факторизація цілих чисел, дискретне логарифмування), функція не є верхньою межею, тому таке визначення не краще.
Приклади Багато алгоритмів факторизації цілих чисел загального призначення мають субекспоненційну часову складність. Асимтотично найшвидшим є метод решета числового поля з оцінкою складності:
при .
До розробки методу решета числового поля асимптотично найшвидшим був метод квадратичного решета з оцінкою:
Для задачі дискретного логарифма на еліптичній кривій, найшвидшим алгоритмом загального призначення є : час роботи оцінюється як квадратний корінь від порядку групи . У L-нотації це записується наступним чином:
Тест простоти AKS потребує поліноміального часу. Це означає, що складність тесту простоти може бути не більшою за
доведено, що не перевищує 6.Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
Примітки