大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 

这是相当清楚这里说的在asignments数量方面的复杂性将是A * B。

到目前为止很好。

所以，如果我想要解决大O的话，我想我必须考虑函数具有O（n），因为在这种情况下我必须考虑b作为常量值吗？

同样，如果我想要b的大O，它会是O（n）出于同样的原因。

这似乎是有道理的，但直观地使用像这样的嵌套迭代块，我期望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）中的一个变量表示法会误导分析。始终使用影响复杂性的每个输入。

Answer 2

嗯，基本上就是完全按照你自己说的：

如果你的参数a或b之一将是一个不变，则时间复杂度将是O(b)或O(a)，因为它不依赖于常数因子。

但是，如果这两个a和b可以任意大，则asypmtotic时间复杂度（a -> inf和b -> inf）将是O（A * B）。

最重要的一点是，大O符号描述渐近的复杂性，因此，尽管它可以对运行于小型a和b有点混乱，思维直观地进行时，其中一个是恒定的，当你让对方价值趋于无穷大时，线性运行时间再次有意义。

Answer 3

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