涉及 2 个独立变量的运行时算法复杂度

Question

我有一个在 a^b 时间内运行的算法，其中 a 和 b 都是单独的输入。

我的算法还是多项式时间复杂度算法还是nⁿ？我认为 nⁿ 不是多项式，但我仍然不确定。

我看到 n 算法的阶乘仍然评估为 nⁿ 复杂度，因此 nⁿ 也必须是非多项式。请帮助并澄清我的疑问。

Answer 1

如果 b 是输入的一部分，则您的运行时间不是多项式。 (尝试给出限制它的多项式的次数!)

在某些领域，研究了特殊的子问题(脑海中浮现出具有有限度数的图，或者用固定数量的尺寸打包)所以你可以说是的，对于固定的 b 你的算法是多项式 in a。