Алгоритмическая сложность наивного кода для обработки всех последовательных подпоследовательностей списка: n ^ 2 или n ^ 3?

У вас есть 3 для заявлений. Для больших n вполне очевидно, что это O(n^3). i и j имеют O(n) каждый, k немного короче, но все же O(n).

Алгоритм возвращает наибольшую сумму последовательных членов. Вот почему для последнего возвращается 99, даже если у вас есть 0 и 1, у вас также есть -3, который уменьшит вашу сумму до 97.

PS: треугольная форма означает 1 + 2 + ... + n = n(n+1) / 2 = O(n^2)

Независимо от формы треугольника или нет, это всегда сложность O (N ^ 3), но, конечно, с более низкой постоянной, чем полные тройные вложенные циклы.

О (п ^ 3).

Вы вычислили любые два элемента между arr [0] и arr [arr.length - 1] , используя «i» и «j», что означает C (n, 2), что это n * (n + 1) / 2 раза расчета.

И средний шаг между каждым расчетом, выполняемым с помощью «k», составляет (0 + длина стрелки) / 2, поэтому общее время расчета составляет C (n, 2) * обр. длина / 2 = n * n * (n + 1) / 4, то есть O (n ^ 3).

Код:

for (int i=0; i<arr.length; i++) // Loop A
{
    for (int j=i; j<arr.length;j++) // Loop B
    {
        for (int k=i+1; k<=j; k++) // Loop C
        {
            // ..
        }
    }
}

Асимптотический анализ на Big-O:

Loop A: Time = 1 + 1 + 1 + .. 1 (n times) = n

Loop B+C: Time = 1 + 2 + 3 + .. + m = m(m+1)/2

Time = SUM { m(m+1)/2 | m in (n,0] }

Time < n * (n(n+1)/2) = 1/2 n^2 * (n+1) = 1/2 n^3 + 1/2 n^2

Time ~ O(n^3)

Полные рассуждения таковы:

Пусть n будет длиной массива.

1) Есть три вложенных цикла.

2) Самый внутренний цикл выполняет ровно j-i итераций (k, начиная с i+1 до j включительно). Нет преждевременного выхода из этого цикла.

3) Средний цикл выполняет ровно n-j итераций (j от i до n-1 включительно), каждая из которых включает j-i самых внутренних итераций, всего (i-i)+(i+1-i)+(i+2-i)+... (n-1-i) = 0+1+2... + (n-1-i). Нет преждевременного выхода из этого цикла.

4) Самый внешний цикл выполняет ровно n итераций (i работает от 0 до n-1 включительно), каждая из которых включает 0+1+2+ ... (n-1-i) внутренних итераций. Всего (0+1+2... n-1) + (0+1+2+... n-2) + (0+1+2+... n-3) + ... (0). Нет преждевременного выхода из этого цикла.

Теперь, как справиться с этим беспорядком? Вам нужно немного узнать о формуле Фолхабера ( http://en.wikipedia.org/wiki/Faulhaber%27s_formula ). В двух словах, он говорит, что сумма целых чисел до n равна O(n^2); и сумма суммы целых чисел до n равна O(n^3) и т. д.

Если вы помните из исчисления, примитив X является X^2/2; и примитивом X^2 является X^3/3. Каждый раз, когда степень увеличивается. Это не случайно.

Ваш код работает в O(n^3).

Вы можете смоделировать время работы функции как

sum(sum(sum(Theta(1), k=i+1..j),j=i..n),i=1..n)

Как

sum(sum(sum(1, k=i+1..j),j=i..n),i=1..n) = 1/6 n^3  - 1/6 n,

время работы - Theta (n ^ 3).

Если вы недостаточно разбираетесь в основной теории, чтобы напрямую применять анализ @ MohamedEnnahdiElIdri, почему бы просто не начать с тестирования кода?

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

public static long countwhat(int length) {
  long count = 0;
  for (int i = 0; i < length; i++) {
    for (int j = i; j < length; j++) {
      for (int k = i + 1; k <= j; k++) {
        count++;
      }
    }
  }
  return count;
}

Глядя на это, легче ли вывести гипотезу? Если нет, просто проверьте, пропорционально ли возвращаемое значение length в квадрате или length в кубе ...

public static void main(String[] args) {
  for (int l = 1; l <= 10000; l *= 2) {
    long count = countwhat(l);
    System.out.println("i=" + l + ", #iterations:" + count + 
      ", #it/n²:" + (double) count / l / l +
      ", #it/n³:" + (double) count /  l / l / l);
  }
}

... и обратите внимание, что одно значение не приближается к какой-либо константе с ростом l, а другое (не случайно, к той же самой константе, связанной с наибольшей степенью $ n $ в методологическом анализе).

Это требует O(n^3) времени из-за того факта, что в трех циклах увеличиваются три различные переменные . То есть, когда один внутренний цикл закончен, это не влияет на внешний цикл. Внешний цикл выполняется столько раз, сколько он должен был работать до того, как был введен внутренний цикл.

И это проблема максимальной смежной суммы подмассивов. Самоочевиден, когда вы видите пример:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99

Существует отличный алгоритм, известный как алгоритм Кадане (сделайте это для Google), который решает это за O(n) время.

Вот так:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Ссылки: 1 , 2 , 3 .