記法の問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/03 02:49 UTC 版)
上で定義された f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。 この記法の濫用は、等号の両辺にO -記法が登場した際に問題となり、例えばx →∞のとき、 O ( x ) = O ( x 2 ) {\displaystyle O(x)=O(x^{2})} であるが、 O ( x 2 ) ≠ O ( x ) {\displaystyle O(x^{2})\neq O(x)} である。 すなわち、両辺にO -記法が登場した場合には、直観的には十分大きなx で左辺/右辺が定数未満になる事を意味する。 こうした記法上の問題を回避する為に、 f ∈ O ( g ) {\displaystyle f\in O(g)} ないし、 f ( x ) ≤ O ( g ( x ) ) {\displaystyle f(x)\leq O(g(x))} と書く流儀もあるが、一般的ではない。前者の場合、「O(g)」 は g の定数倍によって押さえられる関数全体からなる集合であるとみなしていることになる。 より複雑な使い方としては、O( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は n → ∞ で正しい内容を記述している。 ( n + 1 ) 2 = n 2 + O ( n ) , ( n + O ( n 1 / 2 ) ) ( n + O ( log n ) ) 2 = n 3 + O ( n 5 / 2 ) , n O ( 1 ) = O ( e n ) . {\displaystyle {\begin{aligned}&(n+1)^{2}=n^{2}+O(n),\\&(n+O(n^{1/2}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2}),\\&n^{O(1)}=O(e^{n}).\end{aligned}}} これらの式の意味は、次のように解釈する： 左辺の O() を満たす「任意の」関数に対して、右辺の O() を満たす「ある」関数を適切に選べば、それらの関数を代入した等式の両辺が等しいようにできる。 例えば三つの目の式は、 任意の関数 f(n) = O(1) に対し、g(n) = O(en) を満たすgを適切に選べば n f ( n ) ≤ g ( n ) {\displaystyle n^{f(n)}\leq g(n)} が成立する 事を意味する。 二つの目の式のように左辺に複数のO()がある場合は、それらすべてに対して上述のルールを適応する。したがって二つの目の式は、 任意の関数 f 1 ( n ) = O ( n 1 / 2 ) {\displaystyle f_{1}(n)=O(n^{1/2})\,} 、 f 2 ( n ) = O ( O ( log n ) ) {\displaystyle f_{2}(n)=O(O(\log \,n))\,} に対し、 g ( n ) = O ( n 5 / 2 ) {\displaystyle g(n)=O(n^{5/2})\,} を満たすgを適切に選べば ( n + f 1 ( n ) ) ( n + f 2 ( n ) ) 2 ≤ n 3 + g ( n ) {\displaystyle (n+f_{1}(n))(n+f_{2}(n))^{2}\leq n^{3}+g(n)} が成立する 事を意味する。
※この「記法の問題」の解説は、「ランダウの記号」の解説の一部です。
「記法の問題」を含む「ランダウの記号」の記事については、「ランダウの記号」の概要を参照ください。
- 記法の問題のページへのリンク
