算法时间复杂度O(nm + n²logn)是否属于多项式时间？

好问题！咱们先从多项式时间的核心定义入手，再拆解这个复杂度的每一项来分析：

多项式时间的定义 #

多项式时间算法的核心判定标准是：算法的运行时间可以被一个多项式函数作为上界。换句话说，存在某个固定的常数k，使得算法的时间复杂度满足O(nᵏ)，其中n是输入规模的度量（如果问题里的n、m都是输入的核心规模，分析时会结合两者的关系来看，但绝大多数场景下m都是输入的多项式级参数）。

拆解分析O(nm + n²logn) #

我们把这个复杂度拆成两项逐一解读：

• 第一项：nm
  只要m是输入规模的多项式函数（比如m和n同阶，或者m≤nᵏ，k是某个固定常数——这在绝大多数算法场景里都成立，比如m是矩阵的列数、图的边数这类输入参数），那么nm就是一个多项式项（比如m=n时对应n²，m=n²时对应n³），显然属于多项式时间范畴。

• 第二项：n²logn
  你提到知道O(n logn)包含于O(n²)属于多项式时间，n²logn其实是类似的逻辑：logn的增长速度比任何正整数次幂的多项式项都慢（比如当n足够大时，logn < n）。所以n²logn必然被更高阶的多项式n³上界约束，也就是O(n²logn) ⊆ O(n³)，而O(n³)是标准的多项式时间复杂度。

结论 #

结合两项来看，只要m是输入规模的多项式函数（这是算法分析中的常规情况），那么O(nm + n²logn)整体就属于多项式时间。只有当m是指数级增长的参数时，这个复杂度才会超出多项式时间范畴，但这种情况在绝大多数实际算法问题中很少出现。

内容的提问来源于stack exchange，提问作者martine