プログラム猿必修科目のデータ構造(二)アルゴリズムとアルゴリズムの複雑さ

原文の出典:http://www.jianshu.com/p/d72d4c9e90c6
開発中に環境パッケージを頻繁に切り替えることに悩んでいますか?Evironment Switchを試してみましょう.それを使ってappの運行の時に環境を切り替えることができて、その上その他の親密な心の小さい機能を支持して、そのお母さんがあってもう頻繁な環境の切り替えを心配する必要はありません.https://github.com/CodeXiaoMai/EnvironmentSwitcher
前の章:プログラム猿必修科目のデータ構造(一)データ構造の基本概念と用語
アルゴリズム
アルゴリズムは特定の問題を解決するためのステップの記述であり、コンピュータでは命令の有限シーケンスとして表現され、各命令は1つ以上の動作を表す.
アルゴリズムの特性
アルゴリズムは5つの基本的な特性を持っています.入出力、貧困性、確定性、実現可能性があります.
アルゴリズム設計の要求
良いアルゴリズムは、正確さ、可読性、健やかさ、高効率、および低保存量の特徴を有するべきである.
関数の漸近成長
入力規模nは制限なしに,一つの数値Nを超えると,この関数は常に他の関数より大きくなり,関数は漸近的に成長するという.
2つの関数f(n)とg(n)が与えられ、すべてのn＞Nに対してf(n)は常にg(n)より大きくなるように整数Nがあるならば、f(n)の成長はg(n)よりも漸近的に速いという.
アルゴリズム時間複雑度
アルゴリズム解析を行う場合、文全体の実行回数T(n)は問題規模nに関する関数であり、さらにT(n)のnに対する変化状況を分析し、T(n)の数量レベルを決定する.アルゴリズムの時間複雑さ、すなわちアルゴリズムの時間メトリックは、T(n)＝O(f(n))と記す.問題規模nの増加とともにアルゴリズム実行時間の成長率はf(n)の成長率と同じであり、アルゴリズムの漸近時間複雑度と呼ばれ、時間複雑度と略称される.f(n)は、規模nのある関数である.
O()を使ってアルゴリズムの時間の複雑さを表現する覚え方を大O記法といいます.
大O次法を導く

は、運転時間における加算定数のすべてを定数1で置換する.

は、修正後の運転回数関数において、最上位項目のみを保持する.

最高次項が存在し、かつ1でない場合、この項に乗算された定数が除去される.

定数次数
ガウスアルゴリズム

int sum = 0, n = 100;   //    1  
sum = (1 + n) * n / 2;  //    1  
printf("%d", sum);      //    1  

このアルゴリズムの実行回数関数はf(n)＝3である.大きなO次数を導出する方法により、第1ステップは定数項3を1に変更する.第二のステップは最高次数項を保持し,最高次数項がないので,このアルゴリズムの時間複雑さはT(n)＝O(1)である.
n＝1の場合、アルゴリズムの実行回数は3であり、n＝100の場合、アルゴリズムの実行回数は3であるので、このアルゴリズムの実行回数はnの規模とは関係がないことがわかる.問題の大きさ(nの大きさ)に関係なく、一定時間のアルゴリズムを実行することを定数次数といいます.
分岐構造については、実行回数は真でも偽でも一定であり、nの変化に伴って変化しないので、単純な分岐構造(循環構造に含まれない)であり、その時間複雑度もO(1)である.
線形次数
下記のコードの時間複雑度はO(n)です.循環体のコードはn回実行しなければならないからです.

int i;
for (i = 0; i < n; i++) {
    /*        O(1)         */
}

対数階

int count = 1;
while (count < n) {
    count = count * 2;
    /*        O(1)         */
}

countに2をかけるたびに、nに近づいてきます.つまり、2を掛けてnより大きいものがどれぐらいあるかというと、ループは終了します.x=log 2 nは2 x=nで待つ.このアルゴリズムの時間複雑度はT(n)＝O(logn)である.
二乗階
これはループネストのコードです.

int i, j;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        /*        O(1)         */
    }
}

その内部循環は、時間の複雑さがO(n)であり、外層の循環に対しては、O(n)の文であるだけで、n回循環することを知っています.このコードの時間複雑度はO(n 2)です.
外回りの回数をmに変えると、時間の複雑さがO(m＊n)になります.

int i, j， m;
for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
        /*        O(1)         */
    }
}

したがって、循環時間の複雑さは、循環体の複雑さに等しいということをまとめて示します.
このループの入れ子は次のどれぐらいの時間が複雑ですか?

int i, j;
for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {   //    j = i     0
        /*        O(1)         */
    }
}

i=0の場合、内サイクルはn回実行されたので、i=1の場合はn-1回実行され、…i=n-1の場合は1回実行された.したがって、部の実行回数は以下の通りです.
n+(n-1)+(n-2)+…+1=n(n+1)/2=n 2/2+n/2.
大きなO次数を導出する方法を用いて,第一条は加法定数を考慮しない.第二条最高次項だけを保持するので、n 2/2を保持する.第三条この項の乗算定数を除去すること、すなわち1/2を除去すること、最終的にこのアルゴリズムの時間複雑度はT(n)=O(n 2)である.
ありふれた時間の複雑さ
階数
非公式用語
O(1)
定数次数
O(n)
線形次数
O(n 2)
二乗階
O(logn)
対数階
O(nlogn)
nlogn階
O(n 3)
立方階段
O(2 n)
指数‐かい
常用時間の複雑さによる時間は小さい時から順に次のようになります.
O(1)アルゴリズムの空間複雑度
アルゴリズムの空間複雑度は、計算アルゴリズムに必要な記憶空間によって実現され、アルゴリズムの空間複雑度の計算式:S(n)＝O(f(n)))であり、nは問題の規模であり、f(n)は文がnに対する記憶空間の関数である.
締め括りをつける

アルゴリズムは、特定の問題を解決するステップの説明であり、コンピュータでは命令の有限シーケンスであり、各命令は1つまたは複数の動作を表す.

アルゴリズムの特性:貧困性、決定性、実現可能性、入出力があります.

アルゴリズムの設計要求:正確さ、可読性、頑丈さ、高効率、低保存量の必要性.

次の章:プログラム猿必修科目のデータ構造(三)線形表1