Анализ Big-O для цикла

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

for ( int i = 0; i < n; i += 4 )
    for ( int j = 0; j < n; j++ )
        for ( int k = 1; k < j*j; k *= 2 )`

Вот что я до сих пор:

for ( int i = 0; i < n; i += 4 ) = n

for ( int j = 0; j < n; j++ ) = n

for ( int k = 1; k < j*j; k *= 2 ) = log^2 n

Теперь проблема, к которой я прихожу, - это окончательное время цикла. Мое лучшее предположение - O (n ^ 2), однако я не уверен, что это правильно. Может ли кто-нибудь помочь?

Изменить: извините за О-О вещь. В моем учебнике используется "Big-Oh"

Ответы

Ответ 1

Прежде всего обратите внимание, что внешний цикл не зависит от остальных двух - он просто добавляет множитель (n/4)*. Мы рассмотрим это позже.

Теперь рассмотрим сложность

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

Мы имеем следующую сумму:

0 + log 2 (1) + log 2 (2 * 2) +... + log 2 (n * n )

Хорошо отметить, что log 2 (n ^ 2) = 2 * log 2 (n). Таким образом, мы перегруппируем сумму на:

2 * (0 + log 2 (1) + log 2 (2) +... + log 2 (n) )

Анализ этой суммы непросто, но посмотрите этот пост. Используя приближение Стерлинга, можно считать, что оно принадлежит O(n*log(n)). Таким образом, общая сложность O((n/4)*2*n*log(n))= O(n^2*log(n))

Ответ 2

  • В терминах j внутренний цикл равен O(log_2(j^2)) времени, но синус log_2(j^2)=2log(j), это фактически O(log(j)).

  • Для каждой итерации среднего цикла требуется время O (log (j)) (для выполнения внутренний цикл), поэтому нам нужно суммировать:

    sum {log (j) | j = 1,..., n-1} log (1) + log (2) +... + log (n-1) = log ((n-1)!)

И поскольку log((n-1)!) находится в O((n-1)log(n-1)) = O(nlogn), мы можем заключить, что средний средний цикл принимает операции O(nlogn).

  • Обратите внимание, что и средний, и внутренний цикл не зависят от i, поэтому получим полную сложность, мы можем просто умножить n/4 (число повторы внешнего цикла) со сложностью средней петли и получить:

    O (n/4 * nlogn) = O (n ^ 2logn)

Таким образом, общая сложность этого кода O(n^2 * log(n))

Ответ 3

Время Сложность цикла рассматривается как O (n), если переменные цикла увеличиваются/уменьшаются на постоянную величину (которая приведена в примерах ниже):

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

Сложность времени вложенных циклов равна количеству раз, когда выполняется самый внутренний оператор. Например, следующие контуры образцов имеют сложную временную сложность O (n²):

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

Время Сложность цикла считается O (logn), если переменные цикла делятся/умножаются на постоянную величину:

for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

Теперь мы имеем:

for ( int i = 0; i < n; i += 4 ) <----- runs n times
    for ( int j = 0; j < n; j++ ) <----- for every i again runs n times
        for ( int k = 1; k < j*j; k *= 2 )` <--- now for every j it runs logarithmic times.

Таким образом, сложность O (n²logm), где m равно n², которое можно упростить до O (n²logn), потому что n²logm = n²logn² = n² * 2logn ~ n²logn.