具有2个变量的O值相乘 [英] Big O with 2 variables which multiply together

问题描述

如果我使用函数：

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

在这里相当清楚的是分配将是* b。

It is fairly clear here that the complexity in terms of number of asignments is going to be a * b.

到目前为止到目前为止还不错。

Fine so far so good.

所以我想用a来计算Big O，我想我必须考虑该函数具有O（n），因为在这种情况下我必须将b视为常数值？

So if I want to work out the Big O in terms of a I guess I have to consider that the function has O(n) because I must consider b as a constant value in this case?

同样，如果我要以b表示大O，则出于相同的原因也将是O（n）。

And equally if I want the big O in terms of b it would be O(n) for the same reasons.

这似乎很有意义，但是直观地嵌套这样的迭代块，我期望一个O（n ^ 2）或其他一些指数类型的值。当您考虑具有相同值的a和b时，这是很有意义的（即让a = 5且让b = 5会有25个赋值）。

This seems to make sense but intuitively with a nested iteration block like this I expect an O(n^2), or some other exponential type value. And this makes perfect sense when you consider a and b in terms of having the same value (i.e. let a = 5 and let b = 5 there will be 25 assignments).

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

So what is the correct way to express the complexity of this function in Big O notation?

推荐答案

您可以在内部使用两个变量O（n）表示法。例如，此图形复杂度问题使用顶点数和边数进行复杂性分析。在您的情况下，答案将是O（a * b），或者如果您希望更像n，则可以使用O（n * m）。

You can use two variables inside the O(n) notation. For example this graph complexity question uses both the number of vertices and edges for complexity analysis. In your case the answer will be O(a*b), or if you want it more n-like, you can use O(n*m).

假设b或a作为仅使用O（n）表示法中的一个变量的常数会误导分析。始终使用会影响复杂性的所有输入。

Assuming b or a as a constant to use only one variable in O(n) notation is misleading for analysis. Always use every input that affects complexity.

这篇关于具有2个变量的O值相乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！