アルゴリズムの実行時間の効率を測定するにはどうすればよいですか?

マシンのパフォーマンスを無視することに基づいて、アルゴリズムの時間計算量を使用してアルゴリズムの実行時間を測定します。
1. 時間頻度
アルゴリズムの実行にかかる時間は理論的に計算できず、コンピューター上でテストを実行することによってのみ知ることができます。 しかし、コンピューター上ですべてのアルゴリズムをテストすることは不可能であり、その必要もありません。必要なのは、どのアルゴリズムに時間がかかり、どのアルゴリズムに時間がかからないかを知ることだけです。そして アルゴリズムにかかる時間は、アルゴリズム内のステートメントの実行数に比例します。どのアルゴリズムにステートメントが多いほど、かかる時間も長くなります。アルゴリズムにおけるステートメントの実行数は、ステートメント頻度または時間頻度と呼ばれます。それをT(n)と表します。
2. 時間計算量
先ほどの時間周波数において、n は問題のスケールと呼ばれ、n が変化し続けると、時間周波数 T(n) も変化し続けます。しかし、場合によっては、変化したときにどのようなパターンが示されるかを知りたいことがあります。この目的のために、時間計算量の概念を導入します。

一般に、アルゴリズムの基本演算が繰り返される回数は、T(n) で表される問題サイズ n の関数です。補助関数 f(n) がある場合、次のようになります。 n が無限大に近づくとき、T(n)/f(n) の限界値はゼロに等しくない定数であり、その場合、f(n) は T(n) と同じオーダーの大きさの関数であると言われます。 T(n)=O(f(n)) と表され、O(f(n)) はアルゴリズムの漸近時間計算量、または略して時間計算量と呼ばれます。

さまざまなアルゴリズムでは、アルゴリズム内のステートメントの実行回数が一定であれば、時間計算量は O(1) になりますが、時間頻度が異なると時間計算量は同じになる場合もあります。たとえば、T(n)=n^2 3n 4 と T(n)=4n^2 2n 1 は周波数が異なりますが、時間計算量は同じで、どちらも O(n^2) です。
一般的な時間計算量を大きい順に並べると、次のとおりです。
定数次数 O(1)、対数次数 O(log2n) (底が 2 の n の対数、以下同じ)、線形次数 O( n) ,
線形対数次数 O(nlog2n)、二乗次数 O(n^2)、三次次数 O(n^3),...,
k乗次数 O(n^k) 、指数次数 O (2^n)。問題サイズ n が増加し続けると、上記の時間計算量は増加し続け、アルゴリズムの実行効率は低下します。
アルゴリズムの時間パフォーマンス分析
(1) アルゴリズムにかかる時間とステートメントの頻度

アルゴリズムにかかる時間 = アルゴリズム内の各ステートメントの実行時間の合計

各ステートメントの実行時間 = ステートメントの実行回数 (頻度 (Frequency Count)) × ステートメントを 1 回実行するのに必要な時間

アルゴリズムをプログラムに変換した後各ステートメントの実行に必要な時間は、マシンの命令のパフォーマンス、速度、コンパイルによって生成されるコードの品質など、判断が難しい要因によって異なります。

マシンのソフトウェア システムやハードウェア システムとは独立してアルゴリズムの消費時間を分析するには、各ステートメントを 1 回実行するのに必要な時間が単位時間であり、アルゴリズムの消費時間は、そのステートメント内のすべてのステートメントであると仮定します。アルゴリズム. 周波数の合計。
2 つの n 次正方行列の積 C=A×B を求めるアルゴリズムは次のとおりです:

　　# define n 100 // n 可根据需要定义,这里假定为100
　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
　　{ //右边列为各语句的频度
　　int i ,j ,k;
　　 for(i=0; i<n;j++) n+1
　　 for (j=0;j<n;j++) { n(n+1)
　　 C[i][j]=0; n
　　 for (k=0; k<n; k++) nn(n+1)
　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n
　　}
　　}

アルゴリズム内のすべてのステートメントの頻度の合計(つまり、アルゴリズムのコスト) は次のとおりです:

T(n)=nn(n 1) (1.1)

分析:

ループ制御変数ステートメント (1) の i は n に増加する必要があり、i=n が確立されるまでテストは終了しません。したがって、その周波数は n 1 です。ただし、ループ本体は n 回しか実行できません。ステートメント (2) は、ステートメント (1) のループ本体内のステートメントとして n 回実行される必要がありますが、ステートメント (2) 自体は n 1 回実行される必要があるため、ステートメント (2) の頻度は n(n 1 ）。同様に、文(3)、(4)、(5)の頻度はそれぞれn、nn(n 1)、nとなります。

アルゴリズム MatrixMultiply の消費時間 T(n) は、行列の次数 n3 の関数です。

(2) 問題の規模とアルゴリズムの時間計算量
問題を解くためのアルゴリズムの投入量を問題のサイズ(Size)といい、通常は整数で表されます。

行列積問題の規模は行列の次数です。

グラフ理論の問題のサイズは、グラフ内の頂点またはエッジの数です。

アルゴリズムの時間計算量 (Time Complexity、時間計算量とも呼ばれる) T(n) は、アルゴリズムの消費時間であり、アルゴリズムによって解決される問題のサイズ n の関数です。問題 n のサイズが無限大に近づくとき、時間計算量 T(n) の大きさ (次数) をアルゴリズムの漸近時間計算量と呼びます。

アルゴリズム MatrixMultidy の時間計算量 T(n) は式 (1.1) に示されています。n が無限大になる傾向がある場合、明らかに T(n)~O(n3);

これは、n が十分に大きい場合、T(n) と n3 の比はゼロに等しくない定数であることを示しています。つまり、T(n) と n3 は同じ桁であるか、T(n) と n3 は同じ桁です。 T(n)=O(n3) として示される、これはアルゴリズム MatrixMultiply の漸近時間計算量です。

(3) 漸近的時間計算量評価アルゴリズムの時間パフォーマンス

主に、アルゴリズムの時間計算量の大きさ (つまり、アルゴリズムの漸近的時間計算量) を使用して、アルゴリズムの時間パフォーマンスを評価します。アルゴリズム。
アルゴリズム MatrixMultiply の時間計算量は一般に T(n)=O(n3) であり、f(n)=n3 はアルゴリズム内のステートメント (5) の頻度です。次に、アルゴリズムの時間計算量を見つける方法を説明する例を示します。

i と j の内容を交換します。

Temp=i;
i=j;
j=temp;

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。　　
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：

　　 x=0;y=0;
　　 for(k-1;k<=n;k++)
　　 x++;
　　 for(i=1;i<=n;i++)
　　 for(j=1;j<=n;j++)
　　 y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

变量计数之二：

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

i=n-1;
while(i>=0&&(A[i]!=k))
 i--;
return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

以上がアルゴリズムの実行時間の効率を測定するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。