L jelölés

Az L - jelölés az O - jelöléshez hasonló aszimptotikus jelölés , amely a végtelenre valóíródott. A Big O -hoz hasonlóan az L jelölést általábanegy adott algoritmus számítási bonyolultságának közelítésére használják . Ugyanakkor azalgoritmus bemeneti adatainak valamilyen, méretükkel arányos paraméterét reprezentálja: például a bemeneti gráf csúcsainak és éleinek számát a legrövidebb utat kereső algoritmusokban, vagy természetes számot algoritmusok egyszerű tényezőkre bontására . $L_{n}[\alpha ,c]$ $n$ $n$

$L_{n}[\alpha ,c]$ képlet határozza meg

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

ahol egy pozitív állandó és egy állandó . $c$ $\alpha$ $0\leq \alpha \leq 1$

Az L - jelölést elsősorban a számítási számelméletben használják a nehéz számelméleti problémák algoritmusainak összetettségének kifejezésére , például a természetes számokat prímtényezőkké alakító szitaalgoritmusokra és a diszkrét logaritmusok kiszámítására szolgáló módszerekre . Ennek a jelölésnek az az előnye, hogy leegyszerűsíti az algoritmusok elemzését.

A faktor a domináns komponenst tükrözi, a faktor pedig mindenre, ami kevésbé jelentős. Ha azonban 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)))

az ln n polinomja , míg ha egyenlő 1, $\alpha$

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

ln n kitevője (és ezért n polinomja ). Ha valahol 0 és 1 között van, akkor a függvény szubexponenciális, azaz lassabban növekszik, mint egy 1-nél nagyobb bázisú (vagy szuperpolinom) exponenciális függvény. $\alpha$ $L_{n}[\alpha ,c]$

Példák

Számos algoritmus a számokat prímtényezőkre bontja szubexponenciális időbonyolultsággal. A számítási erőforrások megtakarítása szempontjából a legjobb módszer az általános számmezőszita módszer , amelynek becslése:

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

számára . ${\displaystyle c=(64/9)^{(1/3)))$

A legjobb algoritmus a számmezőszita kifejlesztése előtt a kvadratikus szita módszer volt , amelynek bonyolultsági becslése a következő:

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

Az elliptikus görbe diszkrét logaritmusának problémájára a leggyorsabb általánosan alkalmazható algoritmus a nagy és kis lépések algoritmusa - a Shanks algoritmus , amelynek tünetmentes futási időbecslése megegyezik az n csoport sorrendjének négyzetgyökével . Az L - jelölésben ezt írják:

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

A polinomiális időben lefutó AKS primalitásteszt megléte azt jelenti, hogy a primalitásteszt összetettsége legfeljebb

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

és bebizonyosodott, hogy c nem haladhatja meg a 6 -ot . [1]

Történelem

$L$ -a jelölést a szakirodalom többféleképpen definiálta. A -jelölést először Karl Pomerans alkalmazta "Néhány egész faktorizációs algoritmus elemzése és összehasonlítása" [2] című munkájában . $L$

Ennek az űrlapnak csak egy paramétere volt , amely állandó volt a képletben . Pomerans ebben és az előző cikkben egy (vagy kis ) betűt használt a sok logaritmust tartalmazó képletekhez. $c$ $\alpha$ $1/2$ $L$ $l$

A fenti, két paramétert tartalmazó képletet Arjen Lenstra és Hendrik Lenstra vezette be "Algoritms in Number Theory" [3] című cikkében, ahol a jelölést a Coppersmith - algoritmus diszkrét logaritmusának elemzéséhez használták . Jelenleg ez a jelölés a leggyakrabban használt szakirodalom.

Az Alkalmazott kriptográfiai kézikönyv az L -jelölést a következőképpen határozza meg: [4] :

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

Ez nem szabványos meghatározás. feltételezi, hogy az algoritmust végrehajtó ügynök futási ideje felülről korlátos. Az egész faktorizáció és a diszkrét logaritmus esetében azonban az értékeléshez használt -jelölés nem felső korlát, így egy ilyen definíció nem teljesen helyes. $O$ $L$

Jegyzetek

↑ Hendirk W. Lenstra Jr. és Carl Pomerance, Primality teszting Gauss-periódusokkal Archiválva 2012. február 25-én a Wayback Machine -nél , preprint, 2011.
↑ Carl Pomerance, Néhány egészszámú faktorálási algoritmus elemzése és összehasonlítása Archivált : 2021. február 4., a Wayback Machine , In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
↑ Arjen K. Lenstra és Hendrik W. Lenstra, Jr, "Algoritms in Number Theory", Handbook of Theoretical Computer Science (A kötet): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot és Scott A. Vanstone. Alkalmazott kriptográfia kézikönyve archiválva 2005. március 7-én a Wayback Machine -nél . CRC Press, 1996. ISBN 0-8493-8523-7 .