[シリーズ記事]データ構造とアルゴリズムのゲッターアップ(一)

最近はオーディエンスタイムのアプリでデータ構造とアルゴリズムを勉強しています.勉強した後のノート、成果、考え方を記録しています.
アルゴリズムの時間と空間の複雑さの分析
データ構造とは?つまり、データのセットの格納構造です.アルゴリズムは何ですか?データ操作の方法です.したがって、アルゴリズムとデータ構造は結合されており、相補的であり、切り離すことができない.データはアルゴリズムにサービスし、アルゴリズムはデータに作用するからです.たとえば、アルゴリズムの二分割検索は、行列がランダムにアクセスできるため、チェーンでは二分割検索アルゴリズムが実現できなくなります.アルゴリズムの実行効率はどのように推定されますか?時間の複雑さと空間の複雑さ、時間の複雑さはアルゴリズムの実行に費やされたcpu時間であり、空間の複雑さはアルゴリズムの実行中に消費された資源(メモリ)である.時間や空間の複雑さが高いほど、アルゴリズムの効率が低いことを示し、アルゴリズムはより速く、より省的に追求される.アルゴリズムの複雑さは、データ規模の増加に伴うアルゴリズムの実行効率の変化傾向を表しており、アルゴリズムが実際に環境で実行される実際の時間ではなく、アルゴリズムの効率を分析し判定する予測方法である.アルゴリズムの実行時間を取得するには、事後統計の方法が必要です.マシンを探して実行し、時間を統計します.
一般的なアルゴリズムの時間複雑さ
複雑さは大きなOで表しています.通常の複雑さは、定数オーダ(1)、対数オーダ(logn)、線形オーダ(n)、線形対数オーダ(nlogn)、二乗オーダ(n 2)、立方オーダ(n 3)、またはk次オーダ(nk)、指数レベルO(2 n)、乗数オーダ級O(n!)の他の多段以上に属します.データ規模nが大きくなると,非多項式級アルゴリズムの実行時間は急激に増加し,問題を解く実行時間は無限に増大する.したがって,非多項式時間複雑度のアルゴリズムは実は非常に非効率なアルゴリズムである.
アルゴリズムの時間複雑度分析例
いくつかの例を挙げて複雑度の分析を強化する方法:1、足し算の法則:全体の複雑度は級の最大のあのコードの複雑さに等しいです.

function f () {
		for(i = 0; i<= 10000; i++) {
			u += i;
		}
		for(k = 0; k<= n; k++) {
			s += s * k;
		}
	}

ここには2つのサイクルがあり、最初は20000回、時間複雑度はO(20000)、2番目は2 n、時間複雑度はO(2 n)、この関数の実際の複雑度はO(20000)＋O(2 n)＝O(2 n＋20000)である.20000は定数であり、アルゴリズム時間の複雑さは変化しないので、この関数の時間複雑さはO(n)であり、nの前の係数は無視できる.
2、乗算の法則:ネストコードの複雑さはネスト内外の複雑さの積に等しい.

	function f () {
		for(k = 0; k<= n; k++) {
			s += s * k;
		}
	}
	function cf() {
		for (i = 0; i < n; i++) 
			f();
	}

cf()の時間の複雑さを分析して、関数cf()はf()を呼び出して、2つの関数はすべて1つの循環があって、だから、cf()の時間の複雑さはO(n*n)=O(n 2)です.
アルゴリズムの空間複雑度分析例
空間複雑度分析の例を示しています.

function f(int n) {
	int * pi = new int[n];
	for(i = 0; i < n; i++) {
		pi[i] = i*i;
	}
}

空間複雑度分析は比較的簡単であり、この例のアルゴリズム空間複雑度はn個の整数空間のメモリを割り当てているので、複雑度はO(n)である.
複雑度の分析はどんな効果がありますか?
アルゴリズムを実行して分析し、実行時間を統計し、資源の消耗状況を確認できるなら、複雑な分析が必要ですか?複雑度分析の利点:1、アルゴリズムを実行しなくても、比較アルゴリズム間の優劣を推定することができます.2、評価アルゴリズムの最適化の参考にすることができます.