L-нотация

L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как  для  стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом  представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиска в нём кратчайшего пути, или натуральное число в алгоритмах разложения его на простые сомножители. 

 определяется формулой

 ,

где  — положительная константа, а  — константа .

L-нотация используется в основном в вычислительной теории чисел для выражения сложности алгоритмов для трудных проблем теории чисел, например, алгоритмов решета разложения натуральных чисел на простые сомножители и методов вычисления дискретных логарифмов. Преимущество такой нотации заключается в упрощении анализа алгоритмов. 

Сомножитель  в  отражает доминирующую составляющую, а сомножитель  относится ко всему менее значительному. При этом, когда  равна 0,

 

является многочленом от ln n, в то время как при  равном 1,

 

является экспонентой от ln n (и, поэтому, полиномом от n). Если же  находится где-то между 0 и 1, то функция  субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная).

Примеры 
Многие алгоритмы разложения чисел на простые сомножители имеют субэкспоненциальную временну́ю сложность. Лучшим методом с точки зрения экономии вычислительных ресурсов является общий метод решета числового поля, который имеет оценку:

 

для .

Лучшим алгоритмом, до разработки решета числового поля, был метод квадратичного решета, который имеет оценку сложности:

 

Для задачи дискретного логарифмирования эллиптической кривой, самым быстрым общеприменимым алгоритмом является алгоритм больших и малых шагов - алгоритм Шенкса, имеющий асимптоматическую оценку времени работы равную квадратному корню от порядка группы n. В L-нотации это записывается:

 

Существование теста простоты AKS, который работает в полиномиальное время, означает, что сложность теста простоты должна быть не более

 

и доказано, что c не должно превышать 6.

История 
-нотация была определена в литературе в различном виде. Первым применил -нотацию Карл Померанс в его работе «Анализ и сравнение некоторых алгоритмов факторизации целых чисел».

Эта форма имела только один параметр ,  в формуле был константой . Померанс использовал букву  (или маленькую ) в этой и предыдущей статье для формул, содержащих много логарифмов.

Вышеприведенная формула, содержащая два параметра, была введена Арьеном Ленстрой и Хендриком Ленстрой в их статье «Алгоритмы в теории чисел», где нотация была использована при анализе дискретного логарифмирования алгоритма Копперсмита.
В настоящее время нотация является наиболее употребимой в литературе.

Руководство по прикладной криптографии определяет L-нотацию как:

 

Это не является стандартным определением.  предполагает, что время работы агента, выполняющего алгоритм, ограничено сверху. Однако, для разложения целого числа и дискретного логарифмирования -нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.

Примечания 

Теория алгоритмов
Теория сложности вычислений