java - 時間複雑度メソッド呼び出し計算

Question

メソッド呼び出しの時間の複雑さを計算するとき、メソッドの複雑さも考慮する必要がありますか、それとも単に複雑さを定数時間と見なす必要がありますか? どうもどうも

Answer 1

メソッドの複雑さを考慮する必要があります。

この要点を示す簡単な例を次に示します。行列のすべての要素を合計するアルゴリズムがあるとします。できるよ ：

sum = 0
for (i = 0; i < m.M; ++i)
    for (j = 0; j < m.N; ++j)
        sum += m[i, j];

また ：

sum = 0
for (i = 0; i < m.M; ++i)
    sum += sumRow(m, i);

sumRow を使用:

for (j = 0; j < m.N; ++j)
    sum += m[i, j];
return sum

ご覧のとおり、実行時間は問題の次元に依存するため、sumRow 関数の複雑さが一定であると見なすことはできません。

ただし、メソッドがどの次元にも依存しない場合は、一定時間で実行されていると見なします。

例として、合計する前に値を射影できます。

sum = 0
for (i = 0; i < m.M; ++i)
    for (j = 0; j < m.N; ++j)
        sum += project(m[i, j]);

次に、行列の次元ではなくスカラー値にのみ依存するため、プロジェクトを定数時間と見なします。