O(m+n) против O(m)/O(n)
Разные алгоритмы имеют разную временную сложность. Я слишком много интересовался этим.
O(m+n) представляет собой линейную функцию, аналогичную O(m) или O(n), которые также представляют линейные функции. Чем O(m+n) отличается от O(m) или O(n)? Оба они представляют линейное время. В случае O(n)/O(m) мы пренебрегаем остальными членами и берем только наивысшую степень. Даже в случае следующего уравнения: T(n)=n+1+n+1; мы делаем T (n) = 2n и, таким образом, делаем O (n). Во всяком случае, мы не принимаем во внимание другие части уравнения.
Я читал некоторые статьи по этому поводу и не совсем понял, что они означают, потому что, согласно этим статьям (или, может быть, я неправильно истолковал), m и n относятся к двум переменным i и j, но если это так, то почему мы напишите алгоритмы с двумя указателями как O (n ^ 2).
Меня все это очень смущает, объясните мне пожалуйста разницу.
Это отвечает на ваш вопрос?
Ответы 1
M и n могут иметь очень разные значения, поэтому O(m+n) отличается от O(m) или O(n) (но похож на O(max(m,n)))
Простой пример: Поиск в ширину на графах имеет сложность O(V+E), где V — количество вершин, E — количество ребер.
Для плотных графов E может быть таким же большим, как V*(V-1)/2, поэтому E~V^2 и мы не можем сказать, что сложность равна O(V) — в данном случае это O(V^2).
С другой стороны — очень разреженные графики, где E очень мало по сравнению с V. В данном случае нельзя сказать, что O(E) - в данном случае это O(V).
И O(E+V) действует во всех случаях.
Возможно, вам следует включить в свой вопрос несколько конкретных примеров алгоритмов. Например. алгоритм, который O (n ^ 2), что вы ожидаете, что это будет O (m + n) или наоборот.