L-нотация
L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как для
определяется формулой
- ,
где — положительная константа, а — константа .
L-нотация используется в основном в вычислительной теории чисел для выражения сложности алгоритмов для трудных проблем теории чисел, например, алгоритмов решета разложения натуральных чисел на простые сомножители и методов вычисления дискретных логарифмов. Преимущество такой нотации заключается в упрощении анализа алгоритмов.
Сомножитель в отражает доминирующую составляющую, а сомножитель относится ко всему менее значительному. При этом, когда равна 0,
является многочленом от ln n, в то время как при равном 1,
является экспонентой от ln n (и, поэтому, полиномом от n). Если же находится где-то между 0 и 1, то функция субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная).
Примеры
Многие алгоритмы разложения чисел на простые сомножители имеют субэкспоненциальную временну́ю сложность. Лучшим методом с точки зрения экономии вычислительных ресурсов является общий метод решета числового поля, который имеет оценку:
для .
Лучшим алгоритмом, до разработки решета числового поля, был метод квадратичного решета, который имеет оценку сложности:
Для задачи
Существование теста простоты AKS, который работает в полиномиальное время, означает, что сложность теста простоты должна быть не более
и доказано, что c не должно превышать 6.[1]
История
-нотация была определена в литературе в различном виде. Первым применил -нотацию Карл Померанс в его работе «Анализ и сравнение некоторых алгоритмов факторизации целых чисел»[2].
Эта форма имела только один параметр , в формуле был константой . Померанс использовал букву (или маленькую ) в этой и предыдущей статье для формул, содержащих много логарифмов.
Вышеприведенная формула, содержащая два параметра, была введена
Руководство по прикладной криптографии определяет L-нотацию как[4]:
Это не является стандартным определением. предполагает, что время работы агента, выполняющего алгоритм, ограничено сверху. Однако, для разложения целого числа и дискретного логарифмирования -нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.
Примечания
- ↑ Hendirk W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods Архивная копия от 25 февраля 2012 на Wayback Machine, preprint, 2011.
- ↑ Carl Pomerance, Analysis and comparison of some integer factoring algorithms Архивная копия от 4 февраля 2021 на Wayback Machine, In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
- ↑ Arjen K. Lenstra and Hendrik W. Lenstra, Jr, «Algorithms in Number Theory», in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1990.
- ↑ Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography Архивная копия от 7 марта 2005 на Wayback Machine. CRC Press, 1996. ISBN 0-8493-8523-7.