L-merkintä

L - merkintä on asymptoottinen merkintä , joka on samanlainen kuin O - merkintä , joka onkirjoitettu äärettömyyteen pyrkiväksi . Kuten Big O , L - merkintätapaa käytetään yleensä approksimoimaantietyn algoritmin laskennallinen monimutkaisuus . Samallaedustaa jotakin algoritmin syöttötiedon parametria, suhteessa niiden kokoon: esimerkiksi syötegraafin kärkien ja reunojen lukumäärä algoritmeissa lyhimmän polun löytämiseksi siitä tai luonnollinen luku algoritmeja sen hajottamiseksi yksinkertaisiksi tekijöiksi . $L_{n}[\alpha ,c]$ $n$ $n$

$L_{n}[\alpha ,c]$ määräytyy kaavan mukaan

L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))

missä on positiivinen vakio ja on vakio . $c$ $\alpha$ $0\leq \alpha \leq 1$

L - merkintää käytetään ensisijaisesti laskennallisessa lukuteoriassa ilmaisemaan algoritmien monimutkaisuus lukuteorian koville ongelmille , kuten seulaalgoritmeille luonnollisten lukujen laskemiseksi alkutekijöiksi ja menetelmien diskreettien logaritmien laskentaan . Tämän merkinnän etuna on yksinkertaistaa algoritmien analysointia.

Tekijä heijastaa hallitsevaa komponenttia ja tekijä viittaa kaikkeen vähemmän merkittävään. Kuitenkin, kun se on 0, $e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $L_{n}[\alpha ,c]$ $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $\alpha$

{\displaystyle L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)))

on polynomi kohdassa ln n , kun taas kun se on 1, $\alpha$

{\displaystyle L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)))

on ln n :n eksponentti (ja siten n:n polynomi ) . Jos se on jossain välillä 0 ja 1, funktio on osaeksponentiaalinen, eli se kasvaa hitaammin kuin eksponentiaalinen funktio, jonka kanta on suurempi kuin 1 (tai superpolynomi). $\alpha$ $L_{n}[\alpha ,c]$

Esimerkkejä

Monilla algoritmeilla lukujen hajottamiseksi alkutekijöiksi on subeksponentiaalinen aikamonimutkaisuus. Paras menetelmä laskennallisten resurssien säästämisessä on yleislukukenttäseulamenetelmä , jolla on arvio:

L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3} }

varten . ${\displaystyle c=(64/9)^{(1/3)))$

Paras algoritmi ennen lukukenttäseulan kehittämistä oli neliöllinen seulamenetelmä , jonka monimutkaisuusarvio on:

L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2} }

Elliptisen käyrän diskreetin logaritmin ongelmaan nopein yleisesti soveltuva algoritmi on suurten ja pienten askelten algoritmi - Shanks-algoritmi , jonka oireeton ajoaikaestimaatti on yhtä suuri kuin ryhmän n kertaluvun neliöjuuri . L - merkinnöissä tämä kirjoitetaan:

{\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)))

AKS:n primaalisuustestin olemassaolo , joka suoritetaan polynomiajassa , tarkoittaa, että primaalisuustestin monimutkaisuuden tulee olla korkeintaan

{\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)))

ja on todistettu, että c ei saa olla suurempi kuin 6. [1]

Historia

$L$ -notaatiota on kirjallisuudessa määritelty eri tavoin. -notaatiota käytti ensimmäisenä Karl Pomerans työssään "Joidenkin kokonaislukufaktorointialgoritmien analyysi ja vertailu" [2] . $L$

Tällä lomakkeella oli vain yksi parametri , joka oli vakio kaavassa . Pomerans käytti kirjainta (tai pientä ) tässä ja edellisessä artikkelissa kaavoille, jotka sisälsivät monia logaritmeja. $c$ $\alpha$ $1/2$ $L$ $l$

Yllä olevan kaksi parametria sisältävän kaavan esittelivät Arjen Lenstra ja Hendrik Lenstra artikkelissaan "Algoritms in Number Theory" [3] , jossa merkintää käytettiin Coppersmithin algoritmin diskreetin logaritmin analysoinnissa . Tällä hetkellä merkintä on kirjallisuudessa eniten käytetty.

Applied Cryptography Manual määrittelee L -merkinnän [4] :

L_{n}[\alpha ,c]=O(e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}).

Tämä ei ole vakiomääritelmä. olettaa, että algoritmin suorittavan agentin käyntiaika on rajoitettu ylhäältä. Kuitenkin kokonaislukukerroin ja diskreetti logaritmi , arvioinnissa käytetty -notaatio ei ole yläraja, joten tällainen määritelmä ei ole täysin oikea. $O$ $L$

Muistiinpanot

↑ Hendirk W. Lenstra Jr. ja Carl Pomerance, Primaliteettitestaus Gaussin jaksoilla Arkistoitu 25. helmikuuta 2012 Wayback Machinessa , preprint, 2011.
↑ Carl Pomerance, Joidenkin kokonaislukulaskenta-algoritmien analyysi ja vertailu Arkistoitu 4. helmikuuta 2021 Wayback Machinessa , julkaisussa Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
↑ Arjen K. Lenstra ja Hendrik W. Lenstra, Jr, "Algoritms in Number Theory", julkaisussa Handbook of Theoretical Computer Science (osa A): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot ja Scott A. Vanstone. Handbook of Applied Cryptography Arkistoitu 7. maaliskuuta 2005 Wayback Machinessa . CRC Press, 1996. ISBN 0-8493-8523-7 .