L-нотація
L-нотація — асимптотична нотація, аналогічна до О-нотації, записується як при , що прямує до нескінченності. Подібно до O-нотації, L-нотація зазвичай застосовується для оцінки обчислювальної складності алгоритмів. При цьому є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, кількість вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага L-нотації над O-нотацією полягає в тому, що вона спрощує аналіз алгоритмів.
Визначення
Нехай , тоді
Множник виражає домінуючу складову, а множник — другорядну, яка зростає повільніше.
При є поліномом від .
При є експонентою від (і також поліномом від ).
При є субекспоненційною, тобто росте повільніше, ніж експонента з основою, більшою за 1, але швидше за будь-який поліном від .
Історія
Першим застосував L-нотацію Карл Померанс[en] у своїй праці «Аналіз та порівняння деяких алгоритмів факторизації цілих чисел»[1]. Для алгоритмів, які він аналізував, нотація мала лише один параметр , а була константою, рівною . Померанс уживав літеру (або малу літеру ) у цій та попередніх статтях для формул, які містили багато логарифмів.
Формулу, яка містить два параметри, запровадили Ар’єн Ленстра[en] та Хендрік Ленстра[en] у своїй статті «Алгоритми в теорії чисел»[2]. Таку нотацію вони застосували для аналізу алгоритму Копперсміта обчислення дискретного логарифма. Їхня форма нотації частіше трапляється в сучасній літературі.
У літературі з криптографії трапляється визначення L-нотації через O-велике:[3]
Це не стандартне визначення. O-нотація передбачає, що час роботи обмежений функцією зверху. Однак для алгоритмів, де зазвичай застосовується L-нотація (факторизація цілих чисел, дискретне логарифмування), функція не є верхньою межею, тому таке визначення не краще.
Приклади
Багато алгоритмів факторизації цілих чисел загального призначення мають субекспоненційну часову складність. Асимтотично найшвидшим є метод решета числового поля з оцінкою складності:
при .
До розробки методу решета числового поля асимптотично найшвидшим був метод квадратичного решета з оцінкою:
Для задачі дискретного логарифма на еліптичній кривій, найшвидшим алгоритмом загального призначення є алгоритм великих і малих кроків[en]: час роботи оцінюється як квадратний корінь від порядку групи . У L-нотації це записується наступним чином:
Тест простоти AKS потребує поліноміального часу. Це означає, що складність тесту простоти може бути не більшою за
доведено, що не перевищує 6.[4]
Примітки
- ↑ Carl Pomerance. Analysis and comparison of some integer factoring algorithms. — 1982. — Т. Part 1. — С. 89-139.
- ↑ Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
- ↑ Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/.
- ↑ Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.