アルゴリズムの時間複雑度と空間複雑度分析
アルゴリズムの時間性能分析
1.アルゴリズムが消費する時間1つのアルゴリズムの実行時間は、アルゴリズム内のすべての文の実行時間の合計を指す.各文の実行時間は、その文の実行回数に1回の実行に要する実際の時間を乗じたものと等しい.文の実行はソースプログラムからターゲットコードにコンパイルして実行するため、文の実行に実際に必要な具体的な時間は計算によるソフト、ハードウェア環境と密接に関連しているため、正確な推定は難しい.2.文頻度メジャーアルゴリズムの効率は具体的なコンピュータ条件を捨て、アルゴリズム自体の効率の高低だけを考慮しなければならない.文頻度とは、1つのアルゴリズムで文が繰り返し実行される回数を指します.1つのアルゴリズムの時間消費は、アルゴリズム内のすべての文の頻度の和です.
eg:2つのn次方正の積c=a*bを求めます.
このアルゴリズムにおけるすべての文頻度の和は,f(n)=2 n^3+3 n^2+2 n+1である.
3.アルゴリズムの時間的複雑度時間的複雑度は、アルゴリズム実行回数nのある関数f(n)であっても、nに伴うf(n)の変化を解析し、T(n)の桁数を決定する.ここでは「O」を用いて桁数を表し,時間的複雑さの式は.
これは,問題規模のnが増大するにつれて,アルゴリズムの実行時間の成長率とf(n)の成長率が同じであることを示し,これをアルゴリズムの漸進時間複雑度と呼び,時間複雑度と略称する.我々が一般的に議論しているのは、最悪の場合の時間複雑度は、アルゴリズムが任意の入力インスタンス上で時間の上界を実行し、最悪の場合を分析してアルゴリズムが時間の上界を指すことを推定するためである.4.漸近時間複雑度アルゴリズム時間複雑度と漸進アルゴリズム時間複雑度は実際のアルゴリズム分析過程で区別されず、漸進時間複雑度は時間複雑度と略称し、T(n)=O(f(n))と記すことができる.ここで,統計アルゴリズムにおける基本動作の繰返し実行回数によりアルゴリズムの実行効率を近似的に得ることができ,O(n)で表され,時間複雑度と呼ばれる.5.常用アルゴリズム時間複雑度O(1)定数型O(n)線形型O(n^2)二乗型O(n^3)立方型O(2^n)指数型O(log 2^n)対数型O(nlog 2^n)二次元型
時間の複雑度の分析方法:1、時間の複雑度は関数の中で基本的な操作の実行する回数です2、一般的にデフォルトのは最悪の時間の複雑度で、つまり最悪の情況の下で実行することができる回数を分析します3、定数の項を無視します4、運行時間の成長傾向に関心を持って、関数式の中で成長するのが最も速い表現に関心を持って、係数5を無視します計算時間複雑度は、nの成長関数の実行回数に伴う増加傾向を推定する6であり、再帰アルゴリズムの時間複雑度は、再帰総回数*再帰毎に基本操作が実行される回数である
アルゴリズムの空間性能分析
1.アルゴリズムが消費する空間1つのアルゴリズムの占有空間とは、アルゴリズムが実際に占有する補助空間の総和である.アルゴリズムの空間複雑度アルゴリズムの空間複雑度は、実際に占有される空間を計算するのではなく、アルゴリズム全体の「補助空間ユニットの個数」を計算する.アルゴリズムの空間的複雑度S(n)は、問題規模nの関数であるアルゴリズムが消費する空間の数段として定義される.メモ:
アルゴリズム実行時に必要な補助空間が入力データ量nに対して定数である場合、このアルゴリズムの補助空間をO(1)と呼ぶ.再帰アルゴリズムの空間複雑度:再帰の深さN*は再帰ごとに必要な補助空間であり、再帰ごとに必要な補助空間が定数である場合、再帰の空間複雑度はO(N)である.
次に、時間と空間の複雑さを二分ルックアップ法とフィボナッチ数列で分析します.空間が限られているため、別のブログを開きます.二分ルックアップ法とフィボナッチ数列の時間と空間の複雑さを分析します.
1.アルゴリズムが消費する時間1つのアルゴリズムの実行時間は、アルゴリズム内のすべての文の実行時間の合計を指す.各文の実行時間は、その文の実行回数に1回の実行に要する実際の時間を乗じたものと等しい.文の実行はソースプログラムからターゲットコードにコンパイルして実行するため、文の実行に実際に必要な具体的な時間は計算によるソフト、ハードウェア環境と密接に関連しているため、正確な推定は難しい.2.文頻度メジャーアルゴリズムの効率は具体的なコンピュータ条件を捨て、アルゴリズム自体の効率の高低だけを考慮しなければならない.文頻度とは、1つのアルゴリズムで文が繰り返し実行される回数を指します.1つのアルゴリズムの時間消費は、アルゴリズム内のすべての文の頻度の和です.
eg:2つのn次方正の積c=a*bを求めます.
#define n 100
void multi(int a[n][n],int b[n][n],int c[n][n])
{
for(i=0;i
for(j=0;j
c[i][j]=0; n^2
for(k=0;k
c[i][j]=c[i][j]+a[i][j]*b[i][j]; n^3
}
} このアルゴリズムにおけるすべての文頻度の和は,f(n)=2 n^3+3 n^2+2 n+1である.
3.アルゴリズムの時間的複雑度時間的複雑度は、アルゴリズム実行回数nのある関数f(n)であっても、nに伴うf(n)の変化を解析し、T(n)の桁数を決定する.ここでは「O」を用いて桁数を表し,時間的複雑さの式は.
T(n)=O(f(n))
これは,問題規模のnが増大するにつれて,アルゴリズムの実行時間の成長率とf(n)の成長率が同じであることを示し,これをアルゴリズムの漸進時間複雑度と呼び,時間複雑度と略称する.我々が一般的に議論しているのは、最悪の場合の時間複雑度は、アルゴリズムが任意の入力インスタンス上で時間の上界を実行し、最悪の場合を分析してアルゴリズムが時間の上界を指すことを推定するためである.4.漸近時間複雑度アルゴリズム時間複雑度と漸進アルゴリズム時間複雑度は実際のアルゴリズム分析過程で区別されず、漸進時間複雑度は時間複雑度と略称し、T(n)=O(f(n))と記すことができる.ここで,統計アルゴリズムにおける基本動作の繰返し実行回数によりアルゴリズムの実行効率を近似的に得ることができ,O(n)で表され,時間複雑度と呼ばれる.5.常用アルゴリズム時間複雑度O(1)定数型O(n)線形型O(n^2)二乗型O(n^3)立方型O(2^n)指数型O(log 2^n)対数型O(nlog 2^n)二次元型
時間の複雑度の分析方法:1、時間の複雑度は関数の中で基本的な操作の実行する回数です2、一般的にデフォルトのは最悪の時間の複雑度で、つまり最悪の情況の下で実行することができる回数を分析します3、定数の項を無視します4、運行時間の成長傾向に関心を持って、関数式の中で成長するのが最も速い表現に関心を持って、係数5を無視します計算時間複雑度は、nの成長関数の実行回数に伴う増加傾向を推定する6であり、再帰アルゴリズムの時間複雑度は、再帰総回数*再帰毎に基本操作が実行される回数である
アルゴリズムの空間性能分析
1.アルゴリズムが消費する空間1つのアルゴリズムの占有空間とは、アルゴリズムが実際に占有する補助空間の総和である.アルゴリズムの空間複雑度アルゴリズムの空間複雑度は、実際に占有される空間を計算するのではなく、アルゴリズム全体の「補助空間ユニットの個数」を計算する.アルゴリズムの空間的複雑度S(n)は、問題規模nの関数であるアルゴリズムが消費する空間の数段として定義される.メモ:
S(n)=O(f(n)) アルゴリズム実行時に必要な補助空間が入力データ量nに対して定数である場合、このアルゴリズムの補助空間をO(1)と呼ぶ.再帰アルゴリズムの空間複雑度:再帰の深さN*は再帰ごとに必要な補助空間であり、再帰ごとに必要な補助空間が定数である場合、再帰の空間複雑度はO(N)である.
次に、時間と空間の複雑さを二分ルックアップ法とフィボナッチ数列で分析します.空間が限られているため、別のブログを開きます.二分ルックアップ法とフィボナッチ数列の時間と空間の複雑さを分析します.