二次成長

数学では、関数またはシーケンスの値が関数の引数またはシーケンスの位置の2乗に比例する場合、その関数またはシーケンスは2次増加を示すと言われます。「2次増加」は、より一般的には「引数またはシーケンスの位置が無限大（大シータ表記、）に向かうにつれて、極限での2次増加」を意味します。^{[1]これは、連続的（}実数値関数、実数変数）または離散的（実数シーケンス、つまり整数または自然数変数の実数値関数）の両方で定義できます。 $f(x)=\Theta (x^{2})$

例

二次成長の例には次のものがあります。

任意の二次多項式。
三角数などの特定の整数列。番目の三角数は、およそという値を持ちます。 $n$ $n(n+1)/2$ $n^{2}/2$

実変数の実関数の場合、2 次増加は2 次導関数が定数 (つまり、3 次導関数が 0) であることと同等であり、したがって 2 次増加の関数はまさに 2 次多項式です。これは、これらが3 次導関数演算子の核であるためです。同様に、シーケンス (整数または自然数変数の実関数) の場合、2 次増加は 2 次差分が定数 (3 次差分が 0) であることと同等であり、^[2]したがって 2 次増加のシーケンスも 2 次多項式です。実際、2 次増加の整数値シーケンスは、0 番目、1 番目、および 2 番目の二項係数が整数値である多項式です。係数は、テイラー多項式(連続の場合) またはニュートン多項式(離散の場合)を取ることで決定できます。 $D^{3}$

アルゴリズムの例には以下が含まれます。

挿入ソートなどの特定のアルゴリズムで最悪の場合にかかる時間を入力長の関数として表したもの。^[3]
ブリーダーのような空間充填セルオートマトンパターン内の生存セルの数は、パターンがシミュレートされる時間ステップの数の関数として表される。^[4]
メトカーフの法則は、通信ネットワークの価値はユーザー数の関数として2乗的に増加するというものです。^[5]

参照

指数関数的成長

参考文献

^ ムーア、クリストファー、メルテンス、ステファン（2011）、計算の性質、オックスフォード大学出版局、p. 22、ISBN 9780191620805。
^ カルマン、ダン（1997）、初等数学モデル：秩序の豊富さと混沌の一瞥、ケンブリッジ大学出版局、p. 81、ISBN 9780883857076。
^ Estivill-Castro, Vladimir (1999)、「ソートと順序統計」、Atallah, Mikhail J. (編)、『アルゴリズムと計算理論ハンドブック』、フロリダ州ボカラトン: CRC、pp. 3-1–3-25、MR 1797171。
^ グリフェス、デイビッド、ヒッカーソン、ディーン (2003)、「無理密度を持つ 2 次元セルラーオートマトン結晶」、セルラーオートマトンの新しい構成、セントフェデラルインスティテュートスタディーズサイエンスコンプレックス、ニューヨーク: オックスフォード大学出版局、pp. 79–91、MR 2079729特に 81 ページを参照してください。「ブリーダーとは、2 番目のオブジェクトのコピーを一定のストリームとして作成し、各コピーが 3 番目のオブジェクトのストリームを作成することによって、2 乗的に成長するパターンです。」
^ ロルフス、ジェフリー H. (2003)、「3.3 メトカーフの法則」、ハイテク産業におけるバンドワゴン効果、MIT プレス、pp. 29–30、ISBN 9780262681384。

[1] ムーア、クリストファー、メルテンス、ステファン（2011）、計算の性質、オックスフォード大学出版局、p. 22、ISBN 9780191620805。

[2] カルマン、ダン（1997）、初等数学モデル：秩序の豊富さと混沌の一瞥、ケンブリッジ大学出版局、p. 81、ISBN 9780883857076。

[3] Estivill-Castro, Vladimir (1999)、「ソートと順序統計」、Atallah, Mikhail J. (編)、『アルゴリズムと計算理論ハンドブック』、フロリダ州ボカラトン: CRC、pp. 3-1–3-25、MR 1797171。

[4] グリフェス、デイビッド、ヒッカーソン、ディーン (2003)、「無理密度を持つ 2 次元セルラーオートマトン結晶」、セルラーオートマトンの新しい構成、セントフェデラルインスティテュートスタディーズサイエンスコンプレックス、ニューヨーク: オックスフォード大学出版局、pp. 79–91、MR 2079729特に 81 ページを参照してください。「ブリーダーとは、2 番目のオブジェクトのコピーを一定のストリームとして作成し、各コピーが 3 番目のオブジェクトのストリームを作成することによって、2 乗的に成長するパターンです。」

[5] ロルフス、ジェフリー H. (2003)、「3.3 メトカーフの法則」、ハイテク産業におけるバンドワゴン効果、MIT プレス、pp. 29–30、ISBN 9780262681384。