大 O 包含两个相乘的变量

如果我采用该功能：

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表示法来表达这个函数的复杂性的正确方法是什么呢？

您可以在 O(n) 表示法中使用两个变量。例如这个图复杂性问题 https://stackoverflow.com/questions/18615362/is-the-worst-time-complexity-of-bfs-in-a-graph-traversal-n2e使用顶点和边的数量进行复杂性分析。在你的情况下，答案将是 O(a*b)，或者如果你想要它更像 n，你可以使用 O(n*m)。

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