time-complexity - 大O : What is the name for the complexity O(a * b)?

Question

我是学习大O表示法的新手，并想到了这个问题。复杂度 O(a * b) 的名称是什么？是线性复杂度吗？多项式？或者是其他东西。实现代码如下。

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

编辑:根据我正在经历的类(class)，它不是 n^2 或二次，因为它使用两个不同的数字进行循环。引用下图

Answer 1

O(ab) 就是 O(ab)。从技术上讲，ab 是 multivariate polynomial二级^nd。但这并不等于二次多项式，例如a²。

如果您对a和b了解更多，您也许能够推断出更多关于他们的关系。例如，如果a = O(b)，则O(ab) = O(b²)，这是二次的。另一方面，如果a是一个常数，那么我们可以将其减少到O(b)，这是线性的。

顺便说一下，请注意，O(a + b) 只是 O(max(a, b))。

如果您对现实世界感兴趣，我可能还会提到这两个复杂性类别都出现了很多，例如在图论中，我们有顶点数 |V| 和边数 |E|，通常为 |E| = O(|V|²) 但不一定。例如，Depth-first search时间复杂度为 O(|V| + |E|)，这仅意味着它在顶点或边较多的情况下是线性的。