アルゴリズムの時間計算量と空間計算量

アルゴリズムの複雑さとは、アルゴリズムが実行可能プログラムに書き込まれた後、そのアルゴリズムを実行するために必要なリソースを指します。リソースには、時間リソースとメモリ リソースが含まれます。数学とコンピューティングの入門への応用。

アルゴリズムの時間計算量の定義: (推奨される学習: PHP ビデオ チュートリアル)

進行中アルゴリズム分析では、ステートメント実行の総数 T(n) は問題サイズ n の関数であり、n による T(n) の変化が分析され、T(n) の大きさのオーダーが決定されます。アルゴリズムの時間計算量、つまりアルゴリズムの時間測定値は、T(n) = O(f(n)) として記録されます。これは、問題サイズ n が増加するにつれて、アルゴリズムの実行時間の増加率が f(n) の増加率と同じになることを意味します。これは、アルゴリズムの漸近時間計算量 (時間計算量と呼ばれます) と呼ばれます。ここで、f(n) は問題サイズ n の関数です。

大文字の O() を使用して、アルゴリズムの時間計算量を反映します。これを Big O 表記法と呼びます。

さまざまなアルゴリズムでは、アルゴリズム内のステートメントの実行回数が一定であれば、時間計算量は O(1) になりますが、時間頻度が異なると時間計算量は同じになる場合もあります。たとえば、T(n)=n^2 3n 4 と T(n)=4n^2 2n 1 は周波数が異なりますが、時間計算量は同じで、どちらも O(n^2) です。

一般的な時間計算量を大きい順に並べると、次のとおりです。

定数次数 O(1)、対数次数 O(log2n) (底が 2 の n の対数、以下同じ) 、線形次数 O(n)、

線形対数次数 O(nlog2n)、二乗次数 O(n^2)、三次次数 O(n^3)、...、

k 乗次数 O(n^k)、指数次数 O(2^n)。問題サイズ n が増加し続けると、上記の時間計算量は増加し続け、アルゴリズムの実行効率は低下します。

アルゴリズム空間複雑度

時間計算量と同様に、空間複雑度は、コンピューター内でアルゴリズムが実行されるときに必要な記憶域の測定値を指します。

次のように記録されます:

S(n)=O(f(n))

アルゴリズムの実行中に必要な記憶域スペースには次のものがあります。 3 部分:

アルゴリズム プログラムが占有するスペース;

初期データ入力によって占有されるストレージ スペース;

アルゴリズムの実行中に必要な追加スペース。

多くの実際的な問題では、アルゴリズムが占有するストレージ容量を削減するために、通常、圧縮ストレージテクノロジが使用されます。

PHP 関連の技術記事の詳細については、PHP グラフィック チュートリアル 列にアクセスして学習してください。

以上がアルゴリズムの時間計算量と空間計算量の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。