[科普中國]-L符號

L符號是個類似大O符號的漸近符號，多用于表示特定算法的計算復雜性。

定義L符號的定義如下：

其中，c為一正實數(shù)，且 為一實數(shù) 。

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

當 為0時，

是個lnn的多項式函數(shù)；而當為1時，

則會是lnn的指數(shù)函數(shù)（即n的多項式函數(shù)）。

當介于0與1之間時，L符號為lnn的次指數(shù)（與超越多項數(shù)）函數(shù)。1

例子許多通用的整數(shù)分解算法都具有次指數(shù)復雜度，其中目前已知最快的為普通數(shù)域篩選法，其時間復雜度估算為

其中，。在普通數(shù)域篩法出現(xiàn)前，最快的整數(shù)分析算法為二元篩法，其時間復雜度估算為

對橢圓曲線離散對數(shù)問題而言，目前已知最快的通用算法為大步小步法，其時間復雜估算為群階的開平方。以L符號表示為

目前已知最快測試一個數(shù)是否為質(zhì)數(shù)的算法為AKS質(zhì)數(shù)測試，其時間復雜度為多項式時間，以L符號表示為

其中，c已被證明至多為6

歷史最早出現(xiàn)L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數(shù)分解算法的分析與比較》（Analysis and comparison of some integer factoring algorithms）。在此論文中，L符號的參數(shù)只有，其中的則因其所分析的算法而設(shè)為。

具有兩個參數(shù)的L符號則由阿爾揚·倫斯特拉及亨德里克·倫斯特拉在其論文《數(shù)論中的算法》（Algorithms in Number Theory）中首次引入，用以分析唐·科普斯密思的離散對數(shù)算法，為現(xiàn)在數(shù)學文獻中最常使用的形式。2

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學