大 O 有 2 个变量相乘

Question

如果我采用函数：

def nested_multiplier(a, b):
    """
    returns a*b
    """
    count = 0
    for i in range(a):
        for j in range(b):
            count += 1
    return count

这里很明显，就赋值次数而言，复杂度将是 a * b。

到目前为止还不错。

因此，如果我想根据 a 计算大 O，我想我必须考虑该函数具有 O(n)，因为在这种情况下我必须将 b 视为常数值？

同样，如果我想要 b 的大 O，出于同样的原因，它将是 O(n)。

这似乎是有道理的，但直觉上，对于像这样的嵌套迭代块，我期望 O(n^2) 或其他一些指数类型的值。当您考虑具有相同值的 a 和 b 时，这是完全合理的（即让 a = 5 并让 b = 5 将有 25 个分配）。

那么用大 O 表示法表达这个函数的复杂性的正确方法是什么？

Answer 1

好吧，基本上就像你自己说的那样：

如果您的参数之一 a 或 b 将成为常量那么时间复杂度将是 O(b)或 O(a)，因为它不依赖于常数因子。

但是，如果 a 和 b 都可以任意大，那么渐近时间复杂度（a -> inf 和 b -> inf）将为 O(a * b) .

关键是大 O 表示法描述了渐近复杂性，因此考虑小 a 和 [=11 的运行时可能会有点混乱=] 直观地说，当其中一个是常数时，当你让另一个值向无穷大增长时，线性运行时间再次有意义。

Answer 2

您可以在 O(n) 表示法中使用两个变量。例如，此 graph complexity question 同时使用顶点数和边数进行复杂性分析。在你的情况下，答案将是 O(a*b)，或者如果你想要它更像 n，你可以使用 O(n*m)。

假设 b 或 a 为常量仅使用 O(n) 表示法中的一个变量对分析有误导性。始终使用影响复杂性的每个输入。

Answer 3

Big O 是衡量输入大小的函数。如果你测量它，例如n = |a| + |b|或者n = max(|a|,|b|)那么复杂度就是O(n^2)，用单个参数来表达是最合理的。另一方面，您可以简单地将其保留为 O(a*b)。除非您打算修复其中一个值，否则说它是 O(a) 或 O(b) 是一种误导。

大 O 有 2 个变量相乘

Big O with 2 variables which multiply together

python

algorithm

big-o

computer-science