その他の漸近記法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/03 02:49 UTC 版)
O-記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。 Ω-記法とω-記法はそれぞれ、O-記法とo-記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は O(g) と Ω(g) を両方満たすことを意味する。 ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッドは今日のそれとは若干異なった意味に用いていたので、あわせてそれも記す。(以下の表の「HLの定義」の部分)。 今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のようにO-記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)はo(g)を満たさない事として定義していた。 両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。 記法意味インフォーマルな定義形式的定義 f ( n ) ∈ O ( g ( n ) ) {\displaystyle f(n)\in O(g(n))} f ( n ) = O ( g ( n ) ) {\displaystyle f(n)=O(g(n))} f ( n ) ⪯ g ( n ) {\displaystyle f(n)\preceq g(n)} f ( n ) ≪ g ( n ) {\displaystyle f(n)\ll g(n)} f {\displaystyle f} は漸近的に（定数倍を除いて） g {\displaystyle g} によって上からおさえられる ある正数 k に対して、十分大きい n で | f ( n ) | ≤ k ⋅ g ( n ) {\displaystyle |f(n)|\leq k\cdot g(n)} ∃ k > 0 ∃ n 0 ∀ n > n 0 | f ( n ) | ≤ k ⋅ | g ( n ) | {\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot |g(n)|} or ∃ k > 0 ∃ n 0 ∀ n > n 0 f ( n ) ≤ k ⋅ g ( n ) {\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\leq k\cdot g(n)} f ( n ) ∈ Ω ( g ( n ) ) {\displaystyle f(n)\in \Omega (g(n))} f ( n ) = Ω ( g ( n ) ) {\displaystyle f(n)=\Omega (g(n))} f ( n ) ⪰ g ( n ) {\displaystyle f(n)\succeq g(n)} f ( n ) ≫ g ( n ) {\displaystyle f(n)\gg g(n)} 2つの定義：HLの定義： f {\displaystyle f} は漸近的に g {\displaystyle g} によって支配されない 今日の定義： f {\displaystyle f} は漸近的に g {\displaystyle g} によって下からおさえられる HLの定義：無限に多くの n の値とある正数 k に対して | f ( n ) | ≥ k ⋅ g ( n ) {\displaystyle |f(n)|\geq k\cdot g(n)} 今日の定義： ある正数 k に対して、十分大きい n で | f ( n ) | ≥ k ⋅ g ( n ) {\displaystyle |f(n)|\geq k\cdot g(n)} HLの定義： ∃ k > 0 ∀ n 0 ∃ n > n 0 f ( n ) ≥ k ⋅ g ( n ) {\displaystyle \exists k>0\;\forall n_{0}\;\exists n>n_{0}\;f(n)\geq k\cdot g(n)} 今日の定義： ∃ k > 0 ∃ n 0 ∀ n > n 0 f ( n ) ≥ k ⋅ g ( n ) {\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)} f ( n ) ∈ Θ ( g ( n ) ) {\displaystyle f(n)\in \Theta (g(n))} f ( n ) = Θ ( g ( n ) ) {\displaystyle f(n)=\Theta (g(n))} f ( n ) ≍ g ( n ) {\displaystyle f(n)\asymp g(n)} f {\displaystyle f} は漸近的に g {\displaystyle g} によって上と下両方からおさえられる ある正数 k1, k2 に対して、十分大きい n で k 1 ⋅ g ( n ) ≤ | f ( n ) | ≤ k 2 ⋅ g ( n ) {\displaystyle k_{1}\cdot g(n)\leq |f(n)|\leq k_{2}\cdot g(n)} ∃ k 1 > 0 ∃ k 2 > 0 ∃ n 0 ∀ n > n 0 {\displaystyle \exists k_{1}>0\;\exists k_{2}>0\;\exists n_{0}\;\forall n>n_{0}} k 1 ⋅ g ( n ) ≤ f ( n ) ≤ k 2 ⋅ g ( n ) {\displaystyle k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)} f ( n ) ∈ o ( g ( n ) ) {\displaystyle f(n)\in o(g(n))} f ( n ) = o ( g ( n ) ) {\displaystyle f(n)=o(g(n))} f ( n ) ≺ g ( n ) {\displaystyle f(n)\prec g(n)} f {\displaystyle f} は漸近的に g {\displaystyle g} によって支配される 任意の正数 k {\displaystyle k} を固定するごとに、十分大きい n を取ると | f ( n ) | ≤ k ⋅ | g ( n ) | {\displaystyle |f(n)|\leq k\cdot |g(n)|} ∀ k > 0 ∃ n 0 ∀ n > n 0 | f ( n ) | ≤ k ⋅ | g ( n ) | {\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot |g(n)|} f ( n ) ∈ ω ( g ( n ) ) {\displaystyle f(n)\in \omega (g(n))} f ( n ) = ω ( g ( n ) ) {\displaystyle f(n)=\omega (g(n))} f ( n ) ≻ g ( n ) {\displaystyle f(n)\succ g(n)} f {\displaystyle f} は漸近的に g {\displaystyle g} を支配する 任意の正数 k {\displaystyle k} を固定するごとに、十分大きい n を取ると | f ( n ) | ≥ k ⋅ | g ( n ) | {\displaystyle |f(n)|\geq k\cdot |g(n)|} ∀ k > 0 ∃ n 0 ∀ n > n 0 | f ( n ) | ≥ k ⋅ | g ( n ) | {\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\ |f(n)|\geq k\cdot |g(n)|} f ( n ) ∼ g ( n ) {\displaystyle f(n)\sim g(n)\!} f {\displaystyle f} は漸近的に g {\displaystyle g} に等しい f ( n ) / g ( n ) → 1 {\displaystyle f(n)/g(n)\to 1} ∀ ε > 0 ∃ n 0 ∀ n > n 0 | f ( n ) g ( n ) − 1 | < ε {\displaystyle \forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\left|{f(n) \over g(n)}-1\right|<\varepsilon } また、計算機科学では f ( n ) = O ~ ( g ( n ) ) {\displaystyle f(n)={\tilde {O}}(g(n))} を ∃ k s.t. f ( n ) = O ( g ( n ) log k ( g ( n ) ) {\displaystyle \exists k\quad {\text{ s.t. }}\quad f(n)=O(g(n)\log ^{k}(g(n))} の意味で用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは logk(n) が任意の定数 k と正の定数 ε に対して常にo(nε) となるからである。
※この「その他の漸近記法」の解説は、「ランダウの記号」の解説の一部です。
「その他の漸近記法」を含む「ランダウの記号」の記事については、「ランダウの記号」の概要を参照ください。
- その他の漸近記法のページへのリンク
