L zápis

L - notace je asymptotická notace podobná O-notaci , psána jakopro inklinaci k nekonečnu . Stejně jako velký O se zápis L obvykle používá k přiblížení výpočetní složitosti konkrétního algoritmu . Zároveňpředstavuje nějaký parametr vstupních dat algoritmu, úměrný jejich velikosti: například počet vrcholů a hran ve vstupním grafu v algoritmech pro nalezení nejkratší cesty v něm nebo přirozené číslo v algoritmy pro jeho rozklad na jednoduché faktory . $L_{n}[\alpha ,c]$ $n$ $n$

$L_{n}[\alpha ,c]$ je určeno vzorcem

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

kde je kladná konstanta a je konstanta . $C$ $\alpha$ $0\leq \alpha \leq 1$

L -notace se používá především ve výpočetní teorii čísel k vyjádření složitosti algoritmů pro těžké problémy v teorii čísel , jako jsou sítové algoritmy pro rozklad přirozených čísel na prvočísla a metody pro výpočet diskrétních logaritmů . Výhodou tohoto zápisu je zjednodušení analýzy algoritmů.

Faktor v odráží dominantní složku a faktor se týká všeho méně významného. Když je však 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)))

je polynom v ln , zatímco když je roven 1, $\alpha$

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

je exponent ln n (a tedy polynom n ). Pokud je někde mezi 0 a 1, pak je funkce sub- exponenciální, to znamená, že roste pomaleji než exponenciální funkce se základem větším než 1 (nebo super-polynomiální). $\alpha$ $L_{n}[\alpha ,c]$

Příklady

Mnoho algoritmů pro rozklad čísel na prvočinitele má subexponenciální časovou složitost. Nejlepší metodou, pokud jde o úsporu výpočetních zdrojů, je obecná metoda číselného síta , která má odhad:

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

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

Nejlepším algoritmem před vývojem síta číselného pole byla metoda kvadratického síta , která má odhad složitosti:

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

Pro problém diskrétního logaritmu eliptické křivky je nejrychlejším obecně použitelným algoritmem algoritmus velkých a malých kroků - Shanksův algoritmus , který má asymptomatický odhad doby běhu rovný druhé odmocnině řádu grupy n . V L -notaci se to píše:

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

Existence testu primality AKS , který běží v polynomiálním čase , znamená , že složitost testu primality musí být maximálně

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

a je dokázáno, že c nesmí překročit 6. [1]

Historie

$L$ -notace byla v literatuře definována různými způsoby. -notaci poprvé použil Karl Pomerans ve své práci "Analýza a srovnání některých algoritmů faktorizace celého čísla" [2] . $L$

Tento formulář měl pouze jeden parametr , který byl konstantou ve vzorci . Pomerans používal písmeno (nebo malé ) v tomto a předchozím článku pro vzorce obsahující mnoho logaritmů. $C$ $\alpha$ $1/2$ $L$ $l$

Výše uvedený vzorec obsahující dva parametry zavedli Arjen Lenstra a Hendrik Lenstra ve svém článku "Algorithms in Number Theory" [3] , kde byl zápis použit při analýze diskrétního logaritmu Coppersmithova algoritmu . V současnosti je v literatuře nejpoužívanější notace.

Manuál aplikované kryptografie definuje L -notaci jako [4] :

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

Toto není standardní definice. předpokládá, že doba běhu agenta provádějícího algoritmus je omezena shora. Pro faktorizaci celého čísla a diskrétní logaritmus však -notace použitá pro vyhodnocení není horní hranicí, takže taková definice není zcela správná. $Ó$ $L$

Poznámky

↑ Hendirk W. Lenstra Jr. a Carl Pomerance, Testování primality s Gaussovými periodami Archivováno 25. února 2012 na Wayback Machine , předtisk, 2011.
↑ Carl Pomerance, Analýza a srovnání některých algoritmů faktoringu celých čísel Archivováno 4. února 2021 na Wayback Machine , In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
↑ Arjen K. Lenstra a Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", v Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot a Scott A. Vanstone. Handbook of Applied Cryptography Archived 7. března 2005 na Wayback Machine . CRC Press, 1996. ISBN 0-8493-8523-7 .