データ構造------アルゴリズム入門

アルゴリズム(algorithm):コンピュータで命令の有限シーケンスとして表現され、各命令は1つ以上の動作を表す特定の問題解決ステップの記述である.
データ構造とアルゴリズムの関係:データ構造を単独で学習し、データ構造が何の役に立つか理解できない.
アルゴリズムの特性:入力と出力(ゼロまたは複数の入力、1つまたは複数の出力)、貧乏性、確定性、実行可能性
アルゴリズム設計の要求:正確性、可読性、丈夫性、時間効率が高く、記憶量が低い、
アルゴリズム効率のメトリック方法:ここでのアルゴリズム効率は実行時間を指す
コードの中間部分に注目し,ループを全体と見なし,Uターンテールループ判定のオーバーヘッドを無視する.
たとえば、次のコードがあります.

int i,sum = 0,n = 100;//  1 
for(i = 1,i< = n,i++){//  n+1 
    sum = sum + i;//  n         
}
printf("%d",sum)://    

コード中間部,すなわちループ部に注目し,反転ループ判定のオーバーヘッド,すなわち2行目を無視する.
運転時間を測定する最も信頼できる方法は、運転時間に消費される基本操作の実行回数を計算することである.実行時間はこのカウントに比例します.アルゴリズムの実行時間を解析する際に重要なのは,基本操作の数を入力規模に関連付けることであり,すなわち,基本操作の数を入力規模の関数f(n)として表す必要がある.
関数の漸進的成長:入力規模nに制限がない場合、1つの具体的な数値Nを超える限り、この関数は常に別の関数より大きくなり、関数は漸進的成長と呼ぶ.
1つのアルゴリズム効率を判断する場合,関数の定数や他の副次的な項は無視でき,主項(最高次数)の次数に注目すべきである.
アルゴリズム時間複雑度定義:アルゴリズム解析を行う場合、文の総実行回数T(n)は問題規模nに関する関数であり、さらにT(n)のnに伴う変化状況を解析してT(n)の数級を決定し、アルゴリズムの時間複雑度もアルゴリズムの時間量度である.T(n)=O(f(n))と表記し、問題規模nの増大に伴いアルゴリズム実行時間の増加率とf(n)の増加率が同じであることを示し、アルゴリズムの漸進時間複雑度と呼ばれ、時間複雑度と略称され、一般的に大文字Oでアルゴリズム時間複雑度を表す記法を大O記法と呼ぶ.一般にnの増大とともにT(n)成長が最も遅いアルゴリズムが最適アルゴリズムである.
一般的な時間の複雑さ:
実行回数関数
ステップ
非公式用語
12
O(1)
ていすうステップ
2n+3
O(n)
線形次数
3n^2+2n+1
O(n^2)
平方階
5log2 n+20
O(logn)
たいすうかい
2n+3nlog2 n+19
O(nlogn)
nlogn次数
6n^3+2n^2+3n+4
O(n^3)
りっぽうだん
2^n
O(2^n)
インデックス次数