基本介紹
- 中文名:L符號
- 外文名:L-notation
- 分類:計算機複雜性
定義,例子,歷史,
定義
L符號的定義如下:
![](/img/6/333/bdc43ab78573ae8af486f81ec7e1.jpg)
其中,c為一正實數,且
為一實數
。
![](/img/9/12d/c23dc92775ecfa21605cf420fa1f.jpg)
![](/img/f/674/e22037e29f4b06e38807928e1b95.jpg)
當
為0時,![](/img/5/56c/8a1c2fd9196be0958470b366e8a1.jpg)
![](/img/a/aa3/8d85367fdd6393f644b84cd33588.jpg)
![](/img/5/56c/8a1c2fd9196be0958470b366e8a1.jpg)
是個lnn的多項式函式;而當
為1時,
![](/img/c/23e/2187299b6fd642ad3daa80ac9c8d.jpg)
![](/img/d/2dd/cae4f84e2ba5dad8fba54f4b5423.jpg)
則會是lnn的指數函式(即n的多項式函式)。
當
介於0與1之間時,L符號為lnn的次指數(與超越多項數)函式。
![](/img/1/ee3/423cefdbd14708a0eb3c52d45e62.jpg)
例子
許多通用的整數分解算法都具有次指數複雜度,其中目前已知最快的為普通數域篩選法,其時間複雜度估算為![](/img/d/a6d/3c9b8c8157b468559bab2601d6b9.jpg)
![](/img/d/a6d/3c9b8c8157b468559bab2601d6b9.jpg)
其中,
。在普通數域篩法出現前,最快的整數分析算法為二元篩法,其時間複雜度估算為
![](/img/3/215/4f7ce353c05e57bb53eb0dd53060.jpg)
![](/img/0/8e9/fb9a4c867f5ff92e79fb0cffbfd8.jpg)
對橢圓曲線離散對數問題而言,目前已知最快的通用算法為大步小步法,其時間複雜估算為群階的開平方。以L符號表示為
![](/img/a/bc8/491471ee1ffc4b1064cd88ff97a4.jpg)
目前已知最快測試一個數是否為質數的算法為AKS質數測試,其時間複雜度為多項式時間,以L符號表示為
![](/img/3/8be/fc6103ae4886d96ab0532f7e3924.jpg)
其中,c已被證明至多為6
歷史
最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解算法的分析與比較》(Analysis and comparison of some integer factoring algorithms)。在此論文中,L符號的參數只有
,其中的
則因其所分析的算法而設為
。
![](/img/c/3f1/9deaeb0ceb0f738cc6df143480b7.jpg)
![](/img/b/dbc/aec8470736ebd75d91bf536e911a.jpg)
![](/img/5/9e2/b0940d0ad588dd01f0b6fb0586b7.jpg)
具有兩個參數的L符號則由阿爾揚·倫斯特拉及亨德里克·倫斯特拉在其論文《數論中的算法》(Algorithms in Number Theory)中首次引入,用以分析唐·科普斯密思的離散對數算法,為現在數學文獻中最常使用的形式。