O (N + M) временная сложность

Question

Я работаю над некоторыми практическими проблемами, когда мне задают сложность времени и сложность по времени. Один из них дает целевую временную сложность O (N + M). У меня возникли проблемы с интуицией того, как будет выглядеть алгоритм O (N + M). Есть ли у кого-нибудь пример такого алгоритма или он может объяснить это ясно? Каждый пример, который я пытаюсь представить, кажется мне O (N * M).

Answer 1

Простой пример алгоритма, который является O(m+n):

int sum(int[] nArr, int[] mArr) { 
    int sum = 0; 
    for(int i : nArr) { 
     sum += i; 
    } 
    for(int i : mArr) { 
     sum += i; 
    } 
    return sum; 
} 

Чтобы вычислить сумму, вам нужно пройти через все элементы в nArr (размер n) и все элементы в mArr (размер m), поэтому общая сложность O(m+n)

Answer 2

Интуиция этой проблемы заключается в том, что у вас есть две уникальные переменные n и m. Теперь представьте себе эти две уникальные переменные, независимо возрастающие, приближающиеся к бесконечности.

Если бы это была проблема O (n) (т. Е. BIG-O), верхняя граница сложности этой задачи была бы линейной, по крайней мере. Можно сказать, что O(n) = n^2. Но проблема O (n) никогда даже не приблизилась бы к пределу n^2, так как n (вход) приближается к бесконечному.

Аналогичным образом, поведение для m будет таким же. O(m) может быть m^2. Но точнее сказать, что O(m) = m. Сложности этих двух проблем: linear.

---

Теперь, если вы просто делаете O(n+m), является то, что на самом деле n^2? Этого не должно быть. Даже если n=m, сумма будет 2n или 2m. Сложность этой проблемы по-прежнему линейная, потому что размер выхода по-прежнему пропорциональный на входы n и m. Поэтому самым точным ответом на эту проблему будет O(n+m) = n+m.

Answer 3

Таким образом, для того, чтобы расширить другие ответы, я постараюсь добавить пример таких проблем, чтобы помочь вам понять:

• Найти мин/макс в массив размера N, а затем искать это значение в массиве размера M. Поскольку вам нужно выполнить первый поиск min/max, вы не можете сделать это сразу.

Например, суммирование элементов из 2 векторов может быть выполнено в O (M + N), но его можно рассматривать как O (N) (при условии, что N> M) или O (M) (если M> N).

Answer 4

Быстрый и простой пример O (N + M) Алгоритм:

for (i = 0; i < n; i++) 
{ 
    // do something but don't loop or invoke recursive functions 
    // only constant O(c) complexity is allowed: a simple series of commands 
} 

for (i = 0; i < m; i++) 
{ 
    // idem 
} 

Сложность коммутативен при добавлении (O (N + M) == O (M + N)) это означает, что вы можете инвертировать два for() без ущерба для сложности. Очевидно, что на алгоритмическом уровне инвертированный МАЙ не будет эквивалентен прямому.

В качестве дополнительной помощи, вот пример O (Н * м) алгоритм:

for (i = 0; i < n; i++) 
{ 
    for (j = 0; j < m; j++) 
    { 
    // do something but don't loop or invoke recursive functions 
    // only constant O(c) complexity is allowed: a simple series of commands 
    } 
} 

Опять же, вы можете инвертировать внутри с внешним контуром, не затрагивая сложности (O (Н * м) == O (m * n)). Имеются те же очевидные соображения.

Ограничение на то, что вы можете поместить в тела for(), связано с тем, что примечание большой буквы o ограничивает верхнюю границу. Если бы это была нижняя граница (небольшая нотация), вы могли бы добавить более сложные вещи, но она никогда не сможет получить меньше.

Answer 5

Один поучительный пример, который делает что-то нетривиальным, состоит в том, чтобы взять два отсортированных массива размера M и N и вывести новый отсортированный массив со всеми этими элементами. Это является основой для сортировки слияния и будет проводить сравнения O (M + N).

Вы можете найти пример где угодно или сделать это самостоятельно.