-
L符號
鎖定
- 中文名
- L符號
- 外文名
- L-notation
- 分 類
- 計算機複雜性
L符號定義
L符號的定義如下:
其中,c為一正實數,且
為一實數
。
當
為0時,
是個lnn的多項式函數;而當
為1時,
則會是lnn的指數函數(即n的多項式函數)。
L符號例子
其中,
。在普通數域篩法出現前,最快的整數分析算法為二元篩法,其時間複雜度估算為
對橢圓曲線離散對數問題而言,已知最快的通用算法為大步小步法,其時間複雜估算為羣階的開平方。以L符號表示為
已知最快測試一個數是否為質數的算法為AKS質數測試,其時間複雜度為多項式時間,以L符號表示為
其中,c已被證明至多為6
L符號歷史
最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解算法的分析與比較》(Analysis and comparison of some integer factoring algorithms)。在此論文中,L符號的參數只有
,其中的
則因其所分析的算法而設為
。
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:4次歷史版本
- 最近更新: piaopioashu