Большая сложность O на зависимых вложенных циклах

Question

Могу ли я получить помощь в понимании того, как решить этот учебный вопрос!Я до сих пор не понимаю объяснения моего профессора.Я не уверен, как посчитать большой 0 для третьего / самого внутреннего цикла.Она объясняет, что ответом для этого алгоритма является O (n ^ 2) и что 2-й и третий цикл должны рассматриваться как один цикл с большим 0 из O (n).Может кто-нибудь, пожалуйста, объясните мне большую букву O для 2-го / третьего цикла в основных терминах непрофессионала. Предполагая, что n = 2 ^ m

for ( int i = n; i > 0; i --) {     
  for (int j =1; j < n; j *= 2){
        for (int k =0; k < j; k++){
        }
  }
 }

Насколько я понимаю, первый цикл имеет большую букву O в видеO (n) Второй цикл = log (n) Третий цикл = log (n) (поскольку число циклов, которое он будет зацикливаться, было уменьшено на logn) * 2 ^ (2 ^ m-1) (для представления увеличенияj?)

Answer 1

позволяет добавить оператор печати в самый внутренний цикл.

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

выход для

j = 1, 1 1

j = 2, 1 1 1

j = 4, 1 1 1 1 1

...

j = n, 1 1 1 1 1 ... n+1 раз.

Вопрос сводится к тому, сколько 1 с будет напечатано.

Это число

(2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= (2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= log n + (1 + 2 + 4 + ... + n)

= O(log n + n)

= O(n).

---

, если вы знаете, почему (1 + 2 + 4 + ... + n) = O(n)

Answer 2

O - примечание является верхним пределом.Вы можете сказать, что у него есть O (n ^ 2).Для наименьшего верхнего я считаю, что это должно быть O(n*log(n)*log(n)), которое принадлежит O(n^2).

Answer 3

Это из-за логарифма.Если у вас есть log (16), возведенное в степень 2 равно 16. Таким образом, log (n), возведенное в степень 2, равно n.Вот почему ваш учитель говорит рассматривать второй и третий цикл как O (n) вместе.

Если максимальные итерации для второго цикла - O (log (n)), то второй и третий циклы будут: O (1 + 2 + 3 + ... + log (n)) = O (log (n) (log (n) + 1) / 2) = O ((log (n) ^ 2 + log (n))) / 2) = O (n)

Answer 4

for ( int i = n; i > 0; i --) {   // This runs n times  
  for (int j =1; j < n; j *= 2){  // This runs atmost log(n) times, i.e m times.
        for (int k =0; k < j; k++){  // This will run atmost m times, when the value of j is m.
        }
  }
 }  

Следовательно, общая сложность будет результатом всех трех, как указано в комментариях к вопросу.
Верхняя граница может быть свободной или жесткой.
Вы можете сказать, что это loosely bound under O(n^2) или tightly bound under O(n * m^2).