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

Question

Мне нужно проанализировать этот цикл, среди прочих, и определить его время работы с использованием нотации 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), однако я не уверен, что это правильно. Может ли кто-нибудь помочь?

Редактировать: извините за О -> O вещь. Мой учебник использует «Big-OH»

Answer 1

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

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

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

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

0 + войти (1) + 2 входа _{(2 * 2) + ... + журнал (п * п)}

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

2 * (0 + войти (1) + журнал (2) + ... + журнал (п))

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

Answer 2

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

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

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

Сложность времени вложенных циклов равна количеству раз, когда выполняется самый внутренний оператор. Например, следующие образцы петля имеет О (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 
    } 

Время Сложность цикла рассматриваются как О (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 is n², которое может быть упрощено до O (n²logn), поскольку n²logm = n²logn² = n² * 2logn ~ n²logn.

Answer 3

• С точки зрения j, внутренний цикл является O(log_2(j^2)) время, но синусоидальной log_2(j^2)=2log(j), это на самом деле O(log(j)).

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

  сумму {журнал (J) | J = 1, ..., п-1} журнал (1) + журнал (2) + ... + журнал (п-1) = лог ((п-1)!)

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

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

  о (п/4 * NlogN) = O (N^2logn)

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