L-нотация
L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как <math>L_n[\alpha,c]</math> для <math>n</math> стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом <math>n</math> представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиске в нём кратчайшего пути, или натуральное число в алгоритмах разложении его на простые сомножители.
<math>L_n[\alpha,c]</math> определяется формулой
- <math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>,
где <math>c</math> — положительная константа, а <math>\alpha</math> — константа <math>0 \leq \alpha \leq 1</math>.
L-нотация используется в основном в вычислительной теории чисел для выражения сложности алгоритмов для трудных проблем теории чисел, например, алгоритмов решета разложения натуральных чисел на простые сомножители и методов вычисления дискретных логарифмов. Преимущество такой нотации заключается в упрощении анализа алгоритмов.
Сомножитель <math>e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> в <math>L_n[\alpha,c]</math> отражает доминирующую составляющую, а сомножитель <math>e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> относится ко всему менее значительному. При этом, когда <math>\alpha</math> равна 0,
- <math>L_n[0, c] = e^{(c + o(1)) \ln\ln n} = (\ln n)^{c + o(1)}</math>
является многочленом от ln n, в то время как при <math>\alpha</math> равна 1,
- <math>L_n[1, c] = e^{(c + o(1)) \ln n} = n^{c + o(1)}</math>
является экспонентой от ln n (и, поэтому, полиномом от n). Если же <math>\alpha</math> находится где-то между 0 и 1, то функция <math>L_n[\alpha,c]</math> субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная).
Примеры
Многие алгоритмы разложения чисел на простые сомножители имеют субэкспоненциальную временну́ю сложность. Лучшим методом с точки зрения экономии вычислительных ресурсов является общий метод решета числового поля, который имеет оценку:
- <math>L_n[1/3, c] = e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}</math>
для <math> c = (64/9)^{(1/3)}</math>.
Лучшим алгоритмом, до разработки решета числового поля, был метод квадратичного решета, который имеет оценку сложности:
- <math>L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}</math>
Для задачи дискретного логарифмирования эллиптической кривой, самым быстрым общеприменимым алгоритмом является алгоритм больших и малых шагов - алгоритм Шенкса, имеющий асимптоматическую оценку времени работы равную квадратному корню от порядка группы n. В L-нотации это записывается:
- <math>L_n[1, 1/2] = n^{1/2+o(1)}</math>
Существование теста простоты AKS, который работает в полиномиальное время, означает, что сложность теста простоты должна быть не более
- <math>L_n[0, c] = (\ln n)^{c+o(1)}</math>
и доказано, что c не должно превышать 6.[1]
История
<math>L</math>-нотация была определена в литературе в различном виде. Первым применил <math>L</math>-нотацию Карл Померанс в его работе «Анализ и сравнение некоторых алгоритмов факторизации целых чисел»[2].
Эта форма имела только один параметр <math>c</math>, <math>\alpha</math> в формуле был константой <math>1/2</math>. Померанс использовал букву <math>L</math> (или маленькую <math>l</math>) в этой и предыдущей статье для формул, содержащих много логарифмов.
Вышеприведенная формула, содержащая два параметра, была введена Арьеном Ленстрой и Хендриком Ленстрой[en] в их статье «Алгоритмы в теории чисел»[3], где нотация была использована при анализе дискретного логарифмирования алгоритма Копперсмита. В настоящее время нотация является наиболее употребимой в литературе.
Руководство по прикладной криптографии определяет L-нотацию как[4]:
- <math>L_n[\alpha,c]=O(e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}).</math>
Это не является стандартным определением. <math>O</math> предполагает, что время работы агента, выполняющего алгоритм, ограничено сверху. Однако, для разложения целого числа и дискретного логарифмирования <math>L</math>-нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.
Напишите отзыв о статье "L-нотация"
Примечания
- ↑ Hendirk W. Lenstra Jr. and Carl Pomerance, [www.math.dartmouth.edu/~carlp/aks041411.pdf Primality testing with Gaussian periods], preprint, 2011.
- ↑ Carl Pomerance, [www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf Analysis and comparison of some integer factoring algorithms], 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. [www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography]. CRC Press, 1996. ISBN 0-8493-8523-7.
Отрывок, характеризующий L-нотация
Жест этот был так не похож на всегдашнее спокойствие княжны, страх, выразившийся на лице князя Василья, был так несвойствен его важности, что Пьер, остановившись, вопросительно, через очки, посмотрел на свою руководительницу.Анна Михайловна не выразила удивления, она только слегка улыбнулась и вздохнула, как будто показывая, что всего этого она ожидала.
– Soyez homme, mon ami, c'est moi qui veillerai a vos interets, [Будьте мужчиною, друг мой, я же стану блюсти за вашими интересами.] – сказала она в ответ на его взгляд и еще скорее пошла по коридору.
Пьер не понимал, в чем дело, и еще меньше, что значило veiller a vos interets, [блюсти ваши интересы,] но он понимал, что всё это так должно быть. Коридором они вышли в полуосвещенную залу, примыкавшую к приемной графа. Это была одна из тех холодных и роскошных комнат, которые знал Пьер с парадного крыльца. Но и в этой комнате, посередине, стояла пустая ванна и была пролита вода по ковру. Навстречу им вышли на цыпочках, не обращая на них внимания, слуга и причетник с кадилом. Они вошли в знакомую Пьеру приемную с двумя итальянскими окнами, выходом в зимний сад, с большим бюстом и во весь рост портретом Екатерины. Все те же люди, почти в тех же положениях, сидели, перешептываясь, в приемной. Все, смолкнув, оглянулись на вошедшую Анну Михайловну, с ее исплаканным, бледным лицом, и на толстого, большого Пьера, который, опустив голову, покорно следовал за нею.
На лице Анны Михайловны выразилось сознание того, что решительная минута наступила; она, с приемами деловой петербургской дамы, вошла в комнату, не отпуская от себя Пьера, еще смелее, чем утром. Она чувствовала, что так как она ведет за собою того, кого желал видеть умирающий, то прием ее был обеспечен. Быстрым взглядом оглядев всех, бывших в комнате, и заметив графова духовника, она, не то что согнувшись, но сделавшись вдруг меньше ростом, мелкою иноходью подплыла к духовнику и почтительно приняла благословение одного, потом другого духовного лица.
– Слава Богу, что успели, – сказала она духовному лицу, – мы все, родные, так боялись. Вот этот молодой человек – сын графа, – прибавила она тише. – Ужасная минута!
Проговорив эти слова, она подошла к доктору.
– Cher docteur, – сказала она ему, – ce jeune homme est le fils du comte… y a t il de l'espoir? [этот молодой человек – сын графа… Есть ли надежда?]
Доктор молча, быстрым движением возвел кверху глаза и плечи. Анна Михайловна точно таким же движением возвела плечи и глаза, почти закрыв их, вздохнула и отошла от доктора к Пьеру. Она особенно почтительно и нежно грустно обратилась к Пьеру.
– Ayez confiance en Sa misericorde, [Доверьтесь Его милосердию,] – сказала она ему, указав ему диванчик, чтобы сесть подождать ее, сама неслышно направилась к двери, на которую все смотрели, и вслед за чуть слышным звуком этой двери скрылась за нею.
Пьер, решившись во всем повиноваться своей руководительнице, направился к диванчику, который она ему указала. Как только Анна Михайловна скрылась, он заметил, что взгляды всех, бывших в комнате, больше чем с любопытством и с участием устремились на него. Он заметил, что все перешептывались, указывая на него глазами, как будто со страхом и даже с подобострастием. Ему оказывали уважение, какого прежде никогда не оказывали: неизвестная ему дама, которая говорила с духовными лицами, встала с своего места и предложила ему сесть, адъютант поднял уроненную Пьером перчатку и подал ему; доктора почтительно замолкли, когда он проходил мимо их, и посторонились, чтобы дать ему место. Пьер хотел сначала сесть на другое место, чтобы не стеснять даму, хотел сам поднять перчатку и обойти докторов, которые вовсе и не стояли на дороге; но он вдруг почувствовал, что это было бы неприлично, он почувствовал, что он в нынешнюю ночь есть лицо, которое обязано совершить какой то страшный и ожидаемый всеми обряд, и что поэтому он должен был принимать от всех услуги. Он принял молча перчатку от адъютанта, сел на место дамы, положив свои большие руки на симметрично выставленные колени, в наивной позе египетской статуи, и решил про себя, что всё это так именно должно быть и что ему в нынешний вечер, для того чтобы не потеряться и не наделать глупостей, не следует действовать по своим соображениям, а надобно предоставить себя вполне на волю тех, которые руководили им.
Не прошло и двух минут, как князь Василий, в своем кафтане с тремя звездами, величественно, высоко неся голову, вошел в комнату. Он казался похудевшим с утра; глаза его были больше обыкновенного, когда он оглянул комнату и увидал Пьера. Он подошел к нему, взял руку (чего он прежде никогда не делал) и потянул ее книзу, как будто он хотел испытать, крепко ли она держится.
