L-нотация

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