データ構造とアルゴリズム学習-複雑度分析

前言
このメモは主にアルゴリズムの複雑さをまとめたものですか?なぜアルゴリズムの複雑度分析を行いますか?アルゴリズムの複雑度分析はどうやって行いますか?よく使う複雑度のレベルは?及び複雑度分析はどうやって掌握しますか?などの問題
アルゴリズムの複雑度分析は何ですか? が解決したのは 、 の問題です.したがって、 の方法が必要であり、これは複雑度分析方法である.
複雑さも と呼ばれ、 と の2次元を含み、 （ ）と との関係を解析するために用いられ、高次の複雑度を越えたアルゴリズムの実行効率が低いことを大まかに表現することができる.
なぜアルゴリズムの複雑さを分析するのですか?

統計、監視などの の限界:

試験結果高度依存試験環境

試験結果はデータ規模の影響が大きいです.

ですので、 が必要です. が可能な方法です. は、実行環境に依存せず、低コストであり、操作性が高い.

は を掌握して、性能のより良いコードを書き出します.

アルゴリズムの複雑さの分析はどうしますか?
大O複雑度表示法

のすべてのコードの実行時間T(n)は、各ラインのコードの実行回数nに比例する.

O は、実際にコードの真の実行時間を具体的に表していません. の を表しています.

は、数式中の低レベル、定数、係数が成長傾向に影響しないため、無視できます.最大級を記録する必要があります.

アルゴリズムの複雑度分析の法則

循環実行回数が一番多い部分コード

だけに注目します.

加算の法則:総複雑度は最大級のコードの複雑度に等しい

です.

乗算規則:ネストコードの複雑さは、ネスト内外コードの複雑さの積

に等しい.
空間複雑度分析
類比時間複雑度、空間複雑度全称は で、 と の を表しています.
一般的な空間の複雑さは、O(1)、O(n)、O(n^2)です.
最悪時間複雑度
コードによっては複雑さが固定されていない場合があります.最良、最悪の場合があります.配列要素検索のように、初めて見つけられるかもしれません.この時のアルゴリズム時間の複雑さは定数次数O(1)であり、配列全体を通して見つけられるかもしれません.この時は最悪の時間複雑度O(n)です.

最適時間複雑度:理想的な場合、コード実行時間の複雑さ.

最悪時間複雑度:最悪の場合、コード実行時間の複雑さ.

平均複雑度
最悪の場合と最悪の場合の複雑さに対応するのは、いずれも極端な場合のコード複雑さであり、発生確率は大きくないので、 を導入して、アルゴリズムをより良い時間複雑さを表現する必要がある. は、様々な場合に時間複雑度が発生する確率を考慮して全体時間複雑度の期待値を計算するので、 は または とも呼ばれる.
多くの場合、複雑さを一つ使えば、需要を満たすことができます.同じブロックコードだけが異なる場合、時間複雑度は であり、この3つの複雑度表現法を用いて区別される.
時間割りの複雑さ
＊適用シーン:＊＊1つのデータ構造に対して連続動作を行う場合、時間の複雑度はほとんど低く、個別の場合のみ時間の複雑度が高く、しかもこれらの操作の間に が存在する場合、このセットを一緒に分析してもいいです.より高い時間複雑度の動作 を他の時間の複雑度の低い動作にすることができるかどうかを確認する.一般的に を適用できるシーンでは、 は に等しい.
解析方法: .
一般的なアルゴリズムの複雑度レベル

非多項式級

O(2^n)とO(n!)

は、データサイズnが大きいほど、非多項式レベルのアルゴリズムの実行時間が急激に増加する.したがって、非多項式級アルゴリズムは非常に非効率なアルゴリズムであるので、使用を避けるべきである.

多項式級

O(1):コードの実行時間はnの増加とともに増加しない.このようにコードの時間複雑度はO(1)として記録されている.一般的に、アルゴリズムに循環文、再帰文が存在しない場合、コードの数に関係なく時間複雑度はO(1)である.

O(logn)、O(nlogn):対数階の複雑さ.

O(m＋n)、O(m＊n):コードの複雑さは によって決定される.

多項式級アルゴリズム時間複雑度は、データ規模の増加とともに変化する傾向曲線

である.
複雑さの分析はどうやって掌握しますか?
練習します
授業後の問題
1.プロジェクトの前に性能テストを行います.コードの時間の複雑さ、空間の複雑さの分析は何度も一挙に行われますか?
＊解答:＊＊は余計なことではなく、漸進時間、空間複雑度の分析は非常に良い理論分析の方向を提供してくれました.コストが低く、操作性が強く、具体的なテストデータを使わずに計算方の実行効率を大まかに推定できます.性能テストと相性がいいです.
2.以下のコードの複雑さを分析する

//     ，    10     array，   len，   i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

//           
void add(int element) {
   if (i >= len) { //        
     //        2         
     int new_array[] = new int[len*2];
     //     array          copy   new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array     array，array        2   len  
     array = new_array;
     len = 2 * len;
   }
   //   element       i    ，   i   
   array[i] = element;
   ++i;
}

答え:

最適時間複雑度:iがlen未満の場合、コードはif文を実行しない.アルゴリズム時間複雑度はO(1)、

である.

最悪時間複雑度:i>=lenの場合、コードはif文を実行し始め、中には循環動作があるので、アルゴリズム時間の複雑さはO(n)である.

平均状況複雑度:if文に入ると、配列が2倍になり、配列が要素を挿入する確率は1/len+1となりますので、加重時間複雑度に応じて数式は1*1/len+1+1/len+1+1+1+1+1+1+len*(1/len+1)=1となりますので、平均状況複雑度はO(1)です.

均等償却時間の複雑度:毎回O(len)前にlen回O(1)があり、前後一貫したタイミング関係があるので、時間の複雑度が高いO(len)を前のlen回に均等償却できるので、均等償却時間の複雑度はO(1)である.

個人の技術学習記録とランニングマラソンのトレーニング試合、読書ノートなどの内容を共有して、興味がある友達は私の公称「青争兄」に関心を持つことができます.