查看“︁L符號”︁的源代码

'''L符號'''是個類似[[大O符號]]的[[漸近分析|漸近]]符號，標記為<math>L_n[\alpha,c]</math>，多用於表示特定[[演算法]]的[[計算複雜性理論|計算複雜性]]。

== 定義 ==
L符號的定義如下：

:<math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>

其中，''c''為一正實數，且<math>\alpha</math>為一實數<math>0 \leq \alpha \leq 1</math>。

L符號主要用於[[計算數論]]，表示困難[[數論]]問題之演算法的複雜性，如[[整數分解]]的篩法及[[離散對數]]的解法。L符號可簡化對這些演算法的分析，以<math>e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>表示主要項，<math>e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>則用以表示其他較小的項。

當<math>\alpha</math>為0時，

:<math>L_n[\alpha,c] = L_n[0, c] = e^{(c + o(1)) \ln\ln n} = (\ln n)^{c + o(1)}\,</math>

是個ln&nbsp;''n''的[[多項式函數]]；而當<math>\alpha</math>為1時，

:<math>L_n[\alpha,c] = L_n[1, c] = e^{(c + o(1)) \ln n} = n^{c + o(1)}\,</math>

則會是ln&nbsp;''n''的[[指數函數]]（即''n''的多項式函數）。

當<math>\alpha</math>介於0與1之間時，L符號為ln&nbsp;''n''的[[时间复杂度#次指數時間|次指數]]（與[[时间复杂度#超越多项式时间|超越多項數]]）函數。

==例子==
許多通用的[[整數分解]]演算法都具有次指數複雜度，其中目前已知最快的為[[普通數域篩選法]]，其時間複雜度估算為

:<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} \approx 1.923</math>。在普通數域篩法出現前，最快的整數分析演算法為{{le|二元篩法|Quadratic sieve}}，其時間複雜度估算為

:<math>L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,</math>

對[[橢圓曲線]][[離散對數]]問題而言，目前已知最快的通用演算法為{{le|大步小步法|Baby-step giant-step}}，其時間複雜估算為[[階 (群論)|群階]]的開平方。以L符號表示為

:<math>L_n[1, 1/2] = n^{1/2+o(1)}.\,</math>

目前已知最快測試一個數是否為[[質數]]的演算法為[[AKS質數測試]]，其時間複雜度為[[多項式時間]]，以L符號表示為

:<math>L_n[0, c] = (\ln n)^{c+o(1)}\,</math>

其中，''c''已被證明至多為6<ref>{{cite web|author=Hendrik W. Lenstra Jr.|author2=Carl Pomerance|title=Primality testing with Gaussian periods|year=2011|url=http://www.math.dartmouth.edu/~carlp/aks041411.pdf|access-date=2018-04-01|archive-url=https://web.archive.org/web/20120225052810/http://www.math.dartmouth.edu/~carlp/aks041411.pdf|archive-date=2012-02-25|dead-url=yes}}</ref>。

==歷史==

最早出現L符號的文獻為[[卡爾·帕梅朗斯]]所著的論文《一些整數分解演算法的分析與比較》（Analysis and comparison of some integer factoring algorithms）<ref>{{cite book|author=Carl Pomerance|chapter=Analysis and comparison of some integer factoring algorithms|publisher=Mathematisch Centrum|title=Computational Methods in Number Theory, Part 1|pages=89-139|year=1982|chapter-url=http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf|access-date=2018-04-01|archive-date=2021-02-04|archive-url=https://web.archive.org/web/20210204004053/https://math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf|dead-url=no}}</ref>。在此論文中，L符號的參數只有<math>c</math>，其中的<math>\alpha</math>則因其所分析的演算法而設為<math>1/2</math>。

具有兩個參數的L符號則由{{le|阿爾揚·倫斯特拉|Arjen Lenstra}}及[[亨德里克·倫斯特拉]]在其論文《數論中的演算法》（Algorithms in Number Theory）<ref>{{cite book|author=Arjen K. Lenstra|author2=Hendrik W. Lenstra, Jr|chapter=Algorithms in Number Theory|title=Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity|year=1991}}</ref>中首次引入，用以分析{{le|唐·科普斯密思|Don Coppersmith}}的[[離散對數]]演算法，為現在數學文獻中最常使用的形式。

==參考資料==
{{Reflist}}

[[分類:漸近分析]]
[[分類:計算複雜性理論]]