跳至內容

L符號

維基百科,自由的百科全書

L符號是個類似大O符號漸近符號,標記為,多用於表示特定演算法計算複雜性

定義

L符號的定義如下:

其中,c為一正實數,且為一實數

L符號主要用於計算數論,表示困難數論問題之演算法的複雜性,如整數分解的篩法及離散對數的解法。L符號可簡化對這些演算法的分析,以表示主要項,則用以表示其他較小的項。

為0時,

是個ln n多項式函數;而當為1時,

則會是ln n指數函數(即n的多項式函數)。

介於0與1之間時,L符號為ln n次指數(與超越多項數)函數。

例子

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

其中,。在普通數域篩法出現前,最快的整數分析演算法為二元篩法英語Quadratic sieve,其時間複雜度估算為

橢圓曲線離散對數問題而言,目前已知最快的通用演算法為大步小步法英語Baby-step giant-step,其時間複雜估算為群階的開平方。以L符號表示為

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

其中,c已被證明至多為6[1]

歷史

最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解演算法的分析與比較》(Analysis and comparison of some integer factoring algorithms)[2]。在此論文中,L符號的參數只有,其中的則因其所分析的演算法而設為

具有兩個參數的L符號則由阿爾揚·倫斯特拉英語Arjen Lenstra亨德里克·倫斯特拉在其論文《數論中的演算法》(Algorithms in Number Theory)[3]中首次引入,用以分析唐·科普斯密思英語Don Coppersmith離散對數演算法,為現在數學文獻中最常使用的形式。

參考資料

  1. ^ Hendrik W. Lenstra Jr.; Carl Pomerance. Primality testing with Gaussian periods (PDF). 2011 [2018-04-01]. (原始內容 (PDF)存檔於2012-02-25). 
  2. ^ 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). 
  3. ^ Arjen K. Lenstra; Hendrik W. Lenstra, Jr. Algorithms in Number Theory. Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity. 1991.