L符號

L符號是個類似大O符號的漸近符號，標記為L_n[\alpha,c]，多用於表示特定演算法的計算複雜性。

定義
L符號的定義如下：

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

其中，c為一正實數，且\alpha為一實數0 \leq \alpha \leq 1。

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

當\alpha為0時，

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

是個ln n的多項式函數；而當\alpha為1時，

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

則會是ln n的指數函數（即n的多項式函數）。

當\alpha介於0與1之間時，L符號為ln n的次指數（與超越多項數）函數。

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

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

其中， c = (64/9)^{1/3} \approx 1.923。在普通數域篩法出現前，最快的整數分析演算法為，其時間複雜度估算為

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

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

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

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

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

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

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

具有兩個參數的L符號則由及亨德里克·倫斯特拉在其論文《數論中的演算法》（Algorithms in Number Theory）中首次引入，用以分析的離散對數演算法，為現在數學文獻中最常使用的形式。

參考資料
漸近分析
計算複雜性理論