Big O复杂度O(a*b)命名咨询：它属于线性还是多项式复杂度？

名称与所属类型 #

• O(a*b)一般直接称为双变量乘积复杂度，也可归类到多项式复杂度范畴。
• 它不属于线性复杂度（线性复杂度是O(n)，仅单个变量的线性增长），而多项式复杂度包含所有变量的多项式组合形式，a和b是两个独立输入变量，它们的乘积属于二元多项式项，因此符合多项式复杂度的定义。

与二次复杂度O(n²)的区别 #

二次复杂度O(n²)是针对单一变量的平方级增长，比如嵌套循环都依赖同一个变量n（外层循环n次，内层也循环n次）。而你的代码中，外层循环次数由a决定，内层由独立变量b决定，二者没有绑定关系，因此不能用O(n²)描述，必须用O(a*b)来准确表示。

正如你学习的课程指出：当嵌套循环基于两个不同的独立变量时，复杂度是两个变量的乘积，而非单变量的平方。

对应代码示例 #

function twoInputsMult(a, b) {
    for (let i = 0; i < a; i++) {
        for (let j = 0; j < b; j++) {
            // do something
        }
    }
}

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