algorithm - この実行時間は入力サイズの多項式ですか？

Question

特定のアルゴリズムの入力サイズはn^2 + n*mです。その実行時間はO（m * n ^ 3）です。実行時間は、入力サイズの多項式と見なすことができますか？

Answer 1

はい、そうです。で実行されます。これは、入力のサイズが2次であるO(max{n,m}^4)よりも小さい入力までの多項式時間です。O(max{n^2,n*m}^2)

注：これは、入力がSIZEであり、この「サイズ」の数値n^2+n*mではないことを前提としています。数値はビットとして表すことができるため、疑似多項式の解のみが得られます。log(n^2+n*m)

Answer 2

実行時間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）です。 ）したがって、実行時間は入力サイズの多項式によって制限されます。