特定のアルゴリズムの入力サイズはn^2 + n*mです。その実行時間はO(m * n ^ 3)です。実行時間は、入力サイズの多項式と見なすことができますか?
2286 次
2 に答える
4
はい、そうです。で実行されます。これは、入力のサイズが2次であるO(max{n,m}^4)
よりも小さい入力までの多項式時間です。O(max{n^2,n*m}^2)
注:これは、入力がSIZEであり、この「サイズ」の数値n^2+n*m
ではないことを前提としています。数値はビットとして表すことができるため、疑似多項式の解のみが得られます。log(n^2+n*m)
于 2012-10-23T15:36:11.513 に答える
1
実行時間T(n、m)は、T(n、m)の上限である多項式がSにある場合、入力サイズS(n、m)= n ^ 2 + n*mの多項式であると言われます。 。
多項式S^2(n、m)=(n ^ 2 + n * m)^ 2 = n ^ 4 + 2(n ^ 2)n * m +(n ^ 2)(m ^ 2)を考えます。n ^ 4と(n ^ 2)(m ^ 2)は正の整数の二乗であるため、正です。したがって、S ^ 2(n、m)> 2(n ^ 2)n * m> n ^ 3*mです。
T(n、m)はO(n ^ 3 * m)であり、S ^ 2(n、m)> n ^ 3 * mであるため、T(n、m)はO(S ^ 2(n、m)です。 )したがって、実行時間は入力サイズの多項式によって制限されます。
于 2012-10-23T16:36:55.560 に答える