Worst Case Big O с Java Алгоритмы

Question

1.

for(i = 0; i < 3; i++){ 
    for(j = 0; j < 10; j++){ 
     print i+j; 
    } 
} 

Я бы предположил, Big O будет 30, так как наибольшее количество раз будет 3 * 10.

2.

for(i = 0; i < n; i++){ 
    for(j = 0; j < m; j++){ 
     print i+j; 
    } 
} 

Будет O быть н * м?

3.

for(i = 0; i < n; i++){ 
    for(j = 0; j < m; j++){ 
     for(int k = 1; k < 1000; k *= 2){ 
      print i+j+k; 
     } 
    } 
} 

н * м * журнал базы 2 (1000) Big O в NLog (п)

4.

for(i = 0; i < n - 10; i++){ 
    for(j = 0; j < m/2; j++){ 
     print i+j; 
    } 
} 

5.

for(i = 0; i < n; i++){ 
    print i; 
} 
//n and m are some integers 
for(j = 1; j < m; j *= 2){ 
    print j; 
} 

Может кто-нибудь дать мне руку с этим, если вы знаете w Big O. Я смотрю на них и в недоумении. Надеюсь, что я разместил это в нужном месте, я считаю эти проблемы трудными. Я ценю любую помощь.

Answer 1

Я думаю, что важно просто указать, что примечание Big O - это все функции, которые при произвольной константе будут считаться верхними границами в некоторой точке.

1. O (1)

   Это потому, что каждый цикл повторяется в постоянной величины времени. Мы будем называть это как O (1) вместо O (30), потому что функция, являющаяся верхней границей, равна 1 с произвольной константой> = 30.

2. O (Н * м)

   Просто потому, что мы должны перебрать m итераций n раз.

3. О (п * м)

   Это то же самое, что и предыдущий, только мы бросали в другую петлю в середине. Теперь вы можете заметить, что этот цикл, аналогичный первой проблеме, - это просто постоянное время. Поэтому вам даже не нужно действительно тратить время на выяснение того, как часто это происходит, поскольку он всегда будет постоянным - это O (1) и будет интерпретироваться как O (n * m * 1), который мы можем просто называть O (п * м)

4. O (н * м)

   Для внешнего контура, не увязнуть на .. - 10 и понять, что мы можем просто сказать, что запускает цикл в O (п). Мы можем игнорировать то, что .. - 10 по той же причине мы проигнорировали точные значения в первой задаче; константы не имеют значения. Этот же принцип применяется для m/2, потому что вы можете думать о m, просто манипулируя константой 1/2. Поэтому мы можем просто назвать это O (n * m).

5. Т (п) = O (п) + O (Л.Г. м) => О (п + Л.Г. м)

   Таким образом, есть два компонента, мы должны смотреть на здесь; первый цикл и второй цикл. Первый цикл, очевидно, O (n), так что это не проблема. Теперь второй цикл немного сложнее. В принципе, вы можете заметить, что итератор j растет экспоненциально (в частности, степень 2), поэтому в этом цикле будет выполняться инверсная экспоненциальная (логарифмическая). Таким образом, эта функция работает в O (n + lg m).

Answer 2

Любой постоянный фактор можно игнорировать. O(30) равен O(1), что, как правило, говорит 1).

2) Именно так.

3) in O(n*m*log_2(1000)), log_2(1000) постоянный, поэтому это O(n*m).

4) O(n-10) такой же, как O(n). O(m/2) такой же, как O(m). Таким образом, O(n*m) снова.

5) Тривиально O(n).

6) O(log_2(m)).