Значение слова l-нотация

"L"-нотация — это асимптотическая нотация, аналогичная О-нотации , записывается как L[α, c] для n (некоторого параметра задачи, например, числа вершин и рёбер графа при поиске на нём кратчайшего пути, или натуральное число , при разложении его на простые сомножители ) стремящимся к бесконечности . Подобно O-большому, эта нотация обычно используется для предварительной оценки вычислительной сложности конкретного алгоритма .

L[α, c] определяется формулой

L[α, c] = e,

где c — положительная константа, а α — константа 0 ≤ α ≤ 1.

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

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

L[0, c] = e = (lnn)

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

L[1, c] = e = n

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