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.