大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)是有誤導性的，除非你打算修正其中一個或另一個值。