Java の時間計算量と空間計算量の分析例

1. アルゴリズム効率

アルゴリズム効率分析は 2 つのタイプに分けられます: 1 つ目は時間効率、2 つ目はスペース効率です。時間効率は時間計算量と呼ばれ、空間効率は空間計算量と呼ばれます。時間計算量は主にアルゴリズムの実行速度を測定し、空間計算量は主にアルゴリズムに必要な追加スペースを測定します。コンピューター開発の初期には、コンピューターの記憶容量は非常に小さかったです。そのため、私たちは空間の複雑さを非常に重視しています。しかし、コンピュータ産業の急速な発展により、コンピュータの記憶容量は非常に高いレベルに達しました。したがって、アルゴリズムの空間の複雑さに特別な注意を払う必要はなくなりました。

2. 時間計算量

1. 時間計算量の概念

アルゴリズムにかかる時間は、そのステートメントの実行回数に比例します。実行回数はアルゴリズムの時間計算量です。つまり、コードを取得してコードの時間計算量を確認すると、主に、コード内で最も多く実行されたステートメントを含むコードが何回実行されたかが分かります。

2. Big の漸近表現

画像分析を見てください:

N の値がどんどん大きくなると、 2N と 10 の合計値は無視できます。

実際、時間計算量を計算するとき、正確な実行数を計算する必要はなく、おおよその実行数のみを計算する必要があるため、ここでは Big O の漸近表現を使用します。

Big O 記法: 関数の漸近的な動作を記述するために使用される数学記号です。

1. 実行時のすべての加法定数を定数 1 に置き換えます。

2. 修正された実行時間関数では、最上位の項のみが保持されます。

3. 最上位の項が存在し、それが 1 でない場合は、この項に乗じた定数を削除します。結果はビッグオーオーダー。

上記のことから、Big O の漸近表現は結果にほとんど影響を与えない項目を削除し、実行回数を簡潔かつ明確に表現していることがわかります。

さらに、一部のアルゴリズムの時間計算量には最良の場合、平均的な場合、および最悪の場合があります。

最悪の場合: 任意の入力サイズに対する最大実行数 (上限)

平均的なケース: 任意の入力サイズに対する予想される実行数

最良のケース: 任意の入力サイズに対する最小実行数 (下限)

例: データ x## を検索します。長さ N の配列内

#最良のケース: 1 回検出されました

最悪のケース: N 回検出されました

平均的なケース: N/2 回検出されました

実際には実践では、一般的な状況がアルゴリズムの最悪の動作状況であることに注意してください。そのため、配列内のデータの検索の時間計算量は O(N)

計算時間の計算量

例 1:

基本演算は 2N 10 回実行され、ビッグ O 次法を導出することにより、時間計算量は O(N)

であることがわかります。例 2:

基本操作は M N 回実行され、未知数 M と N が 2 つあり、時間計算量は O(N M)

例 3 :

基本演算を 100 回実行し、ビッグ O 次法を導出することにより、時間計算量は O(1)

例 4:バブルソートの時間計算量の計算

#基本演算は良くて N 回、悪くても (N*(N-1))/2 回実行されます。ビッグ O 次法の時間計算量は、一般に最悪の時間計算量は O( N^2

例 5: 二分探索の時間計算量

基本的な演算はよくて1回、悪くてもO(logN)回、時間 計算量はO(logN) ps:logNとは、アルゴリズム解析において底が2で対数がNという意味です。 lgN と書きます (logN の計算方法を折り紙探索で説明することをお勧めします) (二分探索のため、不適切な値の半分が削除されるたびに、1 つの半分の後に残った値は n/2 になります。残りの値は 2 つの半分の後の値です: n/2/2 = n/4)

例 6: 階乗再帰の時間計算量を計算します

再帰の時間計算量 = の数recursions * 各再帰が実行される回数

計算と分析により、基本操作が N 回再帰され、時間が複雑であることがわかります。その次数は次のとおりです。 O(N).

例 7: フィボナッチ再帰の時間計算量の計算

計算と分析により、基本演算は 2^N 回再帰的であり、時間計算量は O(2^N) であることがわかります。

ルール:

## 2^0 2^1 2^2 2^3……2^(n-(n-1))

幾何級数の和

a1 は最初の項を表し、q は幾何級数で、2, 1(1-2^n)/-1 と等価です。 2^n 1 になるため、時間計算量は O(2^n)

3. スペース計算量

スペース計算量とは、操作中にアルゴリズムによってストレージが一時的に占有されることを指します。空間の大きさ。スペース複雑度は、プログラムが占めるスペースのバイト数ではありません。これはあまり意味がないため、スペース複雑度は変数の数によって計算されます。空間計算量の計算ルールは基本的に実際の計算量と同様であり、ビッグ O の漸近表記も使用されます。

例 1: バブル ソートの空間複雑度の計算

は一定の追加スペースを使用するため、空間複雑度は O(1)

例 2: フィボナッチの空間複雑度を計算する

##N 個の空間が動的に開かれ、空間複雑度は O(N)

例 3 : 階乗再帰の空間計算量を計算します。

再帰は N 回呼び出され、N 個のスタック フレームが開かれ、各スタック フレームは一定量のスペースを使用します。空間の複雑さは O(N)

です

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