Можно ли упростить O (N + NM) до O (NM)? - PullRequest
Новая
       32

Можно ли упростить O (N + NM) до O (NM)?

0 голосов
/ 09 июля 2019

Предположим, что N и M являются двумя параметрами алгоритма. Правильно ли следующее упрощение? 

O(N+NM) = O[N(1+M)] = O(NM)

Другими словами, разрешено ли удалять константу в таком контексте?

Ответы [ 2 ]

3 голосов
/ 10 июля 2019

TL; DR Да

Пояснение

По определению записи Big-Oh, если термин внутри O (.) будет меньше, чем константа, умноженная на другое слагаемое для всех достаточно больших значений переменной, тогда вы можете отбросить меньший слагаемый.

Более точное определение Big-Oh можно найти здесь , но некоторые примерные последствия таковы:

  • O (1000 * N + N ^ 2) = O (N ^ 2), поскольку N ^ 2 превзойдет 1000 * N, как толькоN> 1000

  • O (N + M) не может быть упрощено

  • O (N + NM) = O (NM), поскольку N +NM <2 (NM), как только N> 1 и M> 1

3 голосов
/ 10 июля 2019

Очевидно, что вы не можете избавиться от термина N, если M=0. так что давайте предположим, M>0. Возьмите постоянную k > 0 такую, что 1<=kM (если M целое число, k=1, в противном случае возьмите постоянную c, такую, что 0 < c <= M дубль k=1/c). У нас есть 

N+NM  = N(1+M)
     <= N(kM+M)            ; 1<=kM
      = (k+1)NM
      ∊ O(NM)

С другой стороны, 

NM <= N+NM ∊ O(N+NM)

Отсюда и равенство.

...