時間的計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/04 02:12 UTC 版)
AKSアルゴリズムの時間的計算量は高々 O ~ ( log ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} である。 PRIMES is in P の初版では、このアルゴリズムは O ~ ( log ( n ) 12 ) {\displaystyle {\tilde {O}}(\log(n)^{12})} のアルゴリズムとして提示された。その後の改訂を経て、現在では O ~ ( log ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} であることが証明されている。しかし、実際には O ~ ( log ( n ) 6 ) {\displaystyle {\tilde {O}}(\log(n)^{6})} であろうと考えられている。また、現在の証明は篩理論の高度な結果によっているが、初歩的な代数学の知識だけでも O ~ ( log ( n ) 10.5 ) {\displaystyle {\tilde {O}}(\log(n)^{10.5})} であることは証明できる。 ただし、記法 O ~ {\displaystyle {\tilde {O}}} は、次のように定義される。 f ( x ) = O ~ ( g ( x ) ) ⇔ f ( x ) = O ( g ( x ) ⋅ P o l y ( log g ( x ) ) ) {\displaystyle f(x)={\tilde {O}}(g(x))\Leftrightarrow f(x)=O(g(x)\cdot \mathrm {Poly} (\log g(x)))} 即ち、記号 O ~ {\displaystyle {\tilde {O}}} はランダウの記号 O を少しだけ弱めたものである。 f ( x ) = O ~ ( g ( x ) ) {\displaystyle f(x)={\tilde {O}}(g(x))} ならば、任意の ϵ > 0 {\displaystyle \epsilon >0} について f ( x ) = O ( g ( x ) 1 + ϵ ) {\displaystyle f(x)=O\left(g(x)^{1+\epsilon }\right)} が成立する（逆は成り立たない）。
※この「時間的計算量」の解説は、「AKS素数判定法」の解説の一部です。
「時間的計算量」を含む「AKS素数判定法」の記事については、「AKS素数判定法」の概要を参照ください。
- 時間的計算量のページへのリンク
