Big O：复杂度 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
        }
    }
}

编辑：根据我正在经历的课程，它不是 n^2 或二次，因为它使用两个不同的数字进行循环。参考下图

Answer 1

O(ab)只是O(ab)。^{从技术上讲}，ab是二阶多元多项式。^但这并不等于二次多项式，例如2。

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

顺便请注意，O(a + b ) 就是O(max(a, b))。

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