L符號

L 符號是一个類似大 O 符號的漸漸符號，標記做講 $ L _ { n } [\ alpha , c] $，加用表示特定演算法的計算複雜性。

定義

L 符號的定義如下：

$ L _ { n } [\ alpha , c]=e ^ { ( c + o ( 一 ) ) ( \ ln n ) ^ { \ alpha } ( \ ln \ ln n ) ^ { 一-\ alpha } } $

其中，_ c _ 為一正實數，而且 $ \ alpha $ 為一實數 $ 零 \ leq \ alpha \ leq 一 $。

L 符號主要用於計算數論，表示困難數論問題之演算法的複雜性，如整數分解的篩法佮離散對數的解法。L 符號會當簡省對遮的演算法的分析，以 $ e ^ { c ( \ ln n ) ^ { \ alpha } ( \ ln \ ln n ) ^ { 一-\ alpha } } $ 表示主要項，$ e ^ { o ( 一 ) ( \ ln n ) ^ { \ alpha } ( \ ln \ ln n ) ^ { 一-\ alpha } } $ 著愛用表示其他較細項的物件。

當 $ \ alpha $ 為零時，

$ L _ { n } [\ alpha , c]=L _ { n } [零 , c]=e ^ { ( c + o ( 一 ) ) \ ln \ ln n }=( \ ln n ) ^ { c + o ( 一 ) } \ , $

是個 ln _ n _ 的多項式函數；啊若當 $ \ alpha $ 為一時，

$ L _ { n } [\ alpha , c]=L _ { n } [一 , c]=e ^ { ( c + o ( 一 ) ) \ ln n }=n ^ { c + o ( 一 ) } \ , $

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

當 $ \ alpha $ 介於零與一之間，L 符號做 ln _ n _ 的指數（佮超越濟項數）函數。

例

真濟通用的整數分解演算法攏有改指數複雜度，其中目前已經知影上緊的為普通數域篩選法，其時間複雜度估算講

$ L _ { n } [三分之一 , c]=e ^ { ( c + o ( 一 ) ) ( \ ln n ) ^ { 三分之一 } ( \ ln \ ln n ) ^ { 三分之二 } } $

其中，$ c=( 九分之六十四 ) ^ { 三分之一 } \ approx 一孵九二三 $。佇普通數簿篩法出現進前，上緊的整數分析演算法共二元篩法，其時間複雜度估算講

$ L _ { n } [二分之一 , 一]=e ^ { ( 一 + o ( 一 ) ) ( \ ln n ) ^ { 二分之一 } ( \ ln \ ln n ) ^ { 二分之一 } } . \ , $

對雞卵行曲線離散對數問題來講，目前已經知上緊的通用演算法為大步小步法，時間複雜估算講是群階的開平方。以 L 符號表示為

$ L _ { n } [一 , 二分之一]=n ^ { 二分之一 + o ( 一 ) } . \ , $

目前已經知影上緊試一个數敢是欲質數的演算法替 AKS 質數測試，所以其時間複雜度做真濟項式時間，以 L 符號表示為

$ L _ { n } [零 , c]=( \ ln n ) ^ { c + o ( 一 ) } \ , $

其中，_ c _ 已經予人證明到濟為六。

歷史

上早出現 L 符號的文獻為卡爾 ・ 帕梅朗斯所對的論文《一寡仔整數分解演的算法的分析佮較》（Analysis and comparison of some integer factoring algorithms）。 在此論文中，L 符號的參數只有 $ c $，內底的 $ \ alpha $ 著因為所分析的演算法來設 $ 二分之一 $。

有兩个參數的 L 符號是由阿爾揚 ・ 倫斯特拉佮亨德里克 ・ 倫斯特拉佇其論文《數論中的演算法》（Algorithms in Number Theory）中第一擺引入，用分析唐 ・ 科普斯密思的離散著數演算法，為這馬數學文獻上捷使用的形式。