L-нотація

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

Визначення

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

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

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

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

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

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

Історія

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

доведено, що $c$ не перевищує 6.