python - 大 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)。

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

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

Answer 1

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

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