Подтвердить что ты не робот

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

Я изучаю тест и нашел этот вопрос:

Я не могу определить сложность, я понял, что это O (n 2) или O (n 3), и я склоняюсь к O (n 3).
Может кто-нибудь сказать мне, что это такое и почему?

Моя идея, что это O (n 2), заключается в том, что в цикле j j = i, который дает форму треугольника, а затем цикл k идет от i + 1 до j, который, я думаю, является другой половиной треугольника.

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

Также, если вы можете сказать мне, что он делает?

Я решил, что он возвращает добавление положительных целых чисел или наибольшее целое число в массиве.
Но для таких массивов, как {99, -3, 0, 1}, он возвращает 99, что, я думаю, связано с ошибкой. Если нет, то у меня нет идеи, что она делает:

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

ОТВЕТЫ

Ответ 1

Вы можете действовать методично, используя Sigma Notation, чтобы получить порядок сложности роста:

enter image description here

Ответ 2

У вас есть 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)

Ответ 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)

Ответ 4

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

Ответ 5

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

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

As

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

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

Ответ 6

О (п ^ 3).

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

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

Ответ 7

Если вы недостаточно хорошо разбираетесь в основополагающей теории, чтобы непосредственно применить анализ @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 cubed...

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);
  }
}

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

Ответ 8

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

И это максимальная непрерывная проблема суммирования субарах. Непонятно, когда вы видите пример:

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

Существует отличный алгоритм, известный как алгоритм Кадане (do 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.

Ответ 9

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

Пусть 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).