[科普中國]-L符號(hào)

L符號(hào)是個(gè)類似大O符號(hào)的漸近符號(hào)，多用于表示特定算法的計(jì)算復(fù)雜性。

定義L符號(hào)的定義如下：

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

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

當(dāng) 為0時(shí)，

是個(gè)lnn的多項(xiàng)式函數(shù)；而當(dāng)為1時(shí)，

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

當(dāng)介于0與1之間時(shí)，L符號(hào)為lnn的次指數(shù)（與超越多項(xiàng)數(shù)）函數(shù)。1

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

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

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

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

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

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

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

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

李嘉騫 - 博士 - 同濟(jì)大學(xué)