L符號是個類似大O符號的漸近符號,標記為
,多用於表示特定演算法的計算複雜性。
定義
L符號的定義如下:
![{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40715162d91a34daf9bcfed5f41d8e336417f803)
其中,c為一正實數,且
為一實數
。
L符號主要用於計算數論,表示困難數論問題之演算法的複雜性,如整數分解的篩法及離散對數的解法。L符號可簡化對這些演算法的分析,以
表示主要項,
則用以表示其他較小的項。
當
為0時,
![{\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f7d292b6129a9cbfb2d0cacc9bfd1b0a05959ad)
是個ln n的多項式函數;而當
為1時,
![{\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adf4c238d6a2edb4f96246252ca13523fc8353fa)
則會是ln n的指數函數(即n的多項式函數)。
當
介於0與1之間時,L符號為ln n的次指數(與超越多項數)函數。
例子
許多通用的整數分解演算法都具有次指數複雜度,其中目前已知最快的為普通數域篩選法,其時間複雜度估算為
![{\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fba4f613c49802383fab0422f391cc98bec823c3)
其中,
。在普通數域篩法出現前,最快的整數分析演算法為二元篩法(英语:Quadratic sieve),其時間複雜度估算為
![{\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db0fcb8338a8140b3ef7c098bed64903e9c3f214)
對橢圓曲線離散對數問題而言,目前已知最快的通用演算法為大步小步法(英语:Baby-step giant-step),其時間複雜估算為群階的開平方。以L符號表示為
![{\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)}.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b529316c3a0906d16002862b62245c0c5f20bce4)
目前已知最快測試一個數是否為質數的演算法為AKS質數測試,其時間複雜度為多項式時間,以L符號表示為
![{\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/424894391b43378ab257339922459690a6ec38f0)
其中,c已被證明至多為6[1]。
歷史
最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解演算法的分析與比較》(Analysis and comparison of some integer factoring algorithms)[2]。在此論文中,L符號的參數只有
,其中的
則因其所分析的演算法而設為
。
具有兩個參數的L符號則由阿爾揚·倫斯特拉(英语:Arjen Lenstra)及亨德里克·倫斯特拉在其論文《數論中的演算法》(Algorithms in Number Theory)[3]中首次引入,用以分析唐·科普斯密思(英语:Don Coppersmith)的離散對數演算法,為現在數學文獻中最常使用的形式。
參考資料
- ^ Hendrik W. Lenstra Jr.; Carl Pomerance. Primality testing with Gaussian periods (PDF). 2011 [2018-04-01]. (原始内容 (PDF)存档于2012-02-25).
- ^ Carl Pomerance. Analysis and comparison of some integer factoring algorithms (PDF). Computational Methods in Number Theory, Part 1. Mathematisch Centrum. 1982: 89–139 [2018-04-01]. (原始内容存档 (PDF)于2021-02-04).
- ^ Arjen K. Lenstra; Hendrik W. Lenstra, Jr. Algorithms in Number Theory. Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity. 1991.