Big 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 собирается быть * б.

Хорошо, пока все хорошо.

Так что, если я хочу выработать Big O в терминах я полагаю, я должен учитывать, что функция имеет O (n), потому что в этом случае я должен рассматривать b как постоянное значение?

И одинаково, если я хочу большой O в терминах b, это будет O (n) по тем же причинам.

Это похоже на смысл, но интуитивно с вложенным блоком итераций, подобным этому, я ожидаю значение O (n^2) или другое значение экспоненциального типа. И это имеет смысл, если вы рассматриваете a и b в терминах того же значения (т. Е. Пусть a = 5 и пусть b = 5 будет 25 заданий).

Итак, каков правильный способ выразить сложность этой функции в нотации Big 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), потому что он не зависит от постоянного множителя.

Если же, как и ab может быть сколь угодно большим, то asypmtotic время сложность (a -> inf и b -> inf) будет O (а * Ь).

Существенный момента является то, что Big O обозначение описывает асимптотических сложности, поэтому в то время как она может быть немного запутанным, думая о время выполнения для малого a и b интуитивно, когда один из них является постоянной, когда вы позволяете другим значение возрастает до бесконечности, линейные времена выполнения снова имеют смысл.

Answer 3

Big O - это функция измерения размера ввода. Если вы его измеряете, например, n = |a| + |b| или n = max(|a|,|b|), тогда сложность O(n^2), что является наиболее разумным способом выразить его в терминах одного параметра. С другой стороны, вы можете просто оставить его как O(a*b). Утверждение, что это O(a) или O(b), вводит в заблуждение, если вы не намерены исправлять одно или другое значение.