L-нотація

L-нотація — асимптотична нотація, аналогічна до О-нотації, записується як ${\displaystyle L_{n}[\alpha ,c]}$ при ${\displaystyle n}$, що прямує до нескінченності. Подібно до O-нотації, L-нотація зазвичай застосовується для оцінки обчислювальної складності алгоритмів. При цьому ${\displaystyle n}$ є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, кількість вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага L-нотації над O-нотацією полягає в тому, що вона спрощує аналіз алгоритмів.

Нехай ${\displaystyle c>0}$, ${\displaystyle \alpha \in [0,1],}$ тоді

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$

Множник ${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ виражає домінуючу складову, а множник ${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ — другорядну, яка зростає повільніше.

При ${\displaystyle \alpha =0}$ ${\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}}$ є поліномом від ${\displaystyle \ln n}$.

При ${\displaystyle \alpha =1}$ ${\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}}$ є експонентою від ${\displaystyle \ln n}$ (і також поліномом від ${\displaystyle n}$).

При ${\displaystyle 0<\alpha <1}$ ${\displaystyle L_{n}[\alpha ,c]}$ є субекспоненційною, тобто росте повільніше, ніж експонента з основою, більшою за 1, але швидше за будь-який поліном від ${\displaystyle \ln n}$.

Першим застосував L-нотацію Карл Померанс^[en] у своїй праці «Аналіз та порівняння деяких алгоритмів факторизації цілих чисел»^[1]. Для алгоритмів, які він аналізував, нотація мала лише один параметр ${\displaystyle c}$, а ${\displaystyle \alpha }$ була константою, рівною ${\displaystyle 1/2}$. Померанс уживав літеру ${\displaystyle L}$ (або малу літеру ${\displaystyle l}$) у цій та попередніх статтях для формул, які містили багато логарифмів.

Формулу, яка містить два параметри, запровадили Ар’єн Ленстра^[en] та Хендрік Ленстра^[en] у своїй статті «Алгоритми в теорії чисел»^[2]. Таку нотацію вони застосували для аналізу алгоритму Копперсміта обчислення дискретного логарифма. Їхня форма нотації частіше трапляється в сучасній літературі.

У літературі з криптографії трапляється визначення L-нотації через O-велике:^[3]

${\displaystyle L_{n}[\alpha ,c]=O(e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}).}$

Це не стандартне визначення. O-нотація передбачає, що час роботи обмежений функцією зверху. Однак для алгоритмів, де зазвичай застосовується L-нотація (факторизація цілих чисел, дискретне логарифмування), функція не є верхньою межею, тому таке визначення не краще.

Багато алгоритмів факторизації цілих чисел загального призначення мають субекспоненційну часову складність. Асимтотично найшвидшим є метод решета числового поля з оцінкою складності:

${\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}$

при ${\displaystyle c=(64/9)^{1/3}\approx 1.923}$.

До розробки методу решета числового поля асимптотично найшвидшим був метод квадратичного решета з оцінкою:

${\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

Для задачі дискретного логарифма на еліптичній кривій, найшвидшим алгоритмом загального призначення є алгоритм великих і малих кроків^[en]: час роботи оцінюється як квадратний корінь від порядку групи ${\displaystyle n}$. У L-нотації це записується наступним чином:

${\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)}.\,}$

Тест простоти AKS потребує поліноміального часу. Це означає, що складність тесту простоти може бути не більшою за

${\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)},\,}$

доведено, що ${\displaystyle c}$ не перевищує 6.^[4]