Big O для 3 вложенных циклов

Другой вопрос о нотации Big O... Что такое Big O для следующего кода:

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           for (int k = 0; k < n; k++){
              count++;
           }
        }
     }

Мои мысли: Поэтому, разбирая его, я думаю, что внешний цикл равен O(log2(n)), тогда каждая из внутренних циклов O(n), которая приведет к O(n^2 * log2(n)) Вопрос № 1, является правильным?

Вопрос № 2: при объединении вложенных циклов это всегда так же просто, как mulitply Big O каждого цикла?

Ответы

Ответ 1

Когда счетчики циклов не зависят друг от друга, всегда можно работать изнутри наружу.

Самый внутренний цикл всегда занимает время O (n), потому что он циклически n раз, независимо от значений j и i.

Когда выполняется второй цикл, он запускается для итераций O (n), на каждой итерации выполняется O (n) для запуска самого внутреннего цикла. Это занимает время O (n 2).

Наконец, когда выполняется внешний цикл, он выполняет O (n 2) на одну итерацию. Он также работает для итераций O (log n), так как он работает равным количеству раз, когда вам нужно разделить n на два, прежде чем вы достигнете 1. Следовательно, общая работа - это O (n 2 log п).

В общем, вы не можете просто комбинировать петли вместе, так как их границы могут зависеть друг от друга. В этом случае, однако, поскольку нет зависимости, время выполнения можно просто умножить. Надеемся, что приведенные выше рассуждения проливают некоторый свет на то, почему это так - потому что, если вы работаете изнутри, думая о том, как много работает каждая петля и сколько раз она это делает, промежутки времени в конечном итоге умножаются вместе.

Надеюсь, это поможет!

Ответ 2

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

Ответ 3

Чтобы ответить на это немного (обратите внимание: немного) более формально, скажем, T(n) - это время (или количество операций), необходимое для завершения алгоритма. Затем для внешнего цикла T(n) = log n*T2(n), где T2(n) - количество операций внутри цикла (без учета каких-либо констант). Аналогично, T2 (n) = n * T3 (n) = n * n.

Тогда воспользуемся следующей теоремой:

Если f 1 (n) = O (g 1 (n)) и f 2 (n) = O (g 2 (n)), то f 1 (n) × f 2 (n) = O (g 1 (п) × г <суб > 2суб > (п))
(источник и доказательство)

Это оставляет нас с T (n) = O (n 2 logn).

"Объединение вложенных циклов" - это просто применение этой теоремы. Проблема состоит в том, чтобы выяснить, сколько операций использует каждый цикл, который в этом случае прост.

Ответ 4

Вы можете действовать формально с помощью Sigma Notation, чтобы точно подражать вашим циклам:

enter image description here