Что такое обозначение Big-O для этого кода?

Question

У меня проблемы с выбором между N ^ 2 и NlogN как Big O?То, что сбивает меня с толку, является третьим вложенным циклом для k <= j.Как мне с этим смириться? </p>

int Max_Subsequence_Sum( const int A[], const int N )
{
  int This_Sum = 0, Max_Sum = 0;
  for (int i=0; i<N; i++)
  {
    for (int j=i; j<N; j++)
    {
      This_Sum = 0;
      for (int k=i; k<=j; k++)
      {
        This_Sum += A[k];
      }
      if (This_Sum > Max_Sum)
      {
        Max_Sum = This_Sum;
      }
    }
  }
  return Max_Sum;
}

Answer 1

Это можно сделать с помощью оценки или анализа.Если посмотреть на самый внутренний цикл, то во втором цикле выполняется j-i операций.Чтобы получить общее количество операций, нужно получить сумму:

(1+N)(2 N + N^2) / 6

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

Answer 2

Давайте сначала проанализируем самый внутренний цикл:

for (int k=i; k <= j; k++) {
    This_Sum += A[k];
}

Здесь счетчик k выполняет итерацию от i (включительно) до j (включительно), это означает, что тело цикла for выполняется j-i+1 раз. Если предположить, что извлечение k -ого числа из массива выполняется за постоянное время, и выполняются арифметические операции (увеличение k, вычисление суммы This_Sum и A[k] и сравнение k с j), то это таким образом работает в O (ji) .

Инициализация This_Sum и оператора if не имеет значения:

This_Sum = 0;
// ...
if (This_Sum > Max_Sum) {
    Max_Sum = This_Sum;
}

Действительно, если мы можем сравнить два числа в постоянное время и установить одну переменную в значение, которое удерживается другим значением в постоянное время, то независимо от того, выполняется условие или нет, число операций является фиксированным.

Теперь мы можем взглянуть на цикл в середине и абстрагироваться от самого внутреннего цикла:

for (int j=i; j < N; j++) {
    // constant number of oprations
    // j-i+1 operations
    // constant number of operations
}

Здесь j колеблется от i до N, что означает, что общее количество операций составляет:

 N
---
\
/     j - i + 1
---
j=i

Эта сумма эквивалентна:

                   N
                  ---
                  \
(N-j) * (1 - i) + /   j
                  ---
                  j=i

Это арифметическая сумма [wiki] и она эквивалентна:

(N - i + 1) × ((1 - i) + (i+N) / 2) = (N - i + 1) × ((N-i) / 2 + 1)

или когда мы расширим это:

i<sup>2</sup>/2 + 3&times;N/2 - 3&times;i/2 + N<sup>2</sup>/2 - N&times;i + 1

Так что теперь мы можем сосредоточиться на внешнем цикле:

for (int i=0; i<N; i++) {
    // i<sup>2</sup>/2 + 3&times;N/2 - 3&times;i/2 + N<sup>2</sup>/2 - N&times;i + 1
}

Так что теперь мы можем снова рассчитать количество операций с:

 N
---
\
/  i<sup>2</sup>/2 + 3&times;N/2 - 3&times;i/2 + N<sup>2</sup>/2 - N&times;i + 1
---
i=0

Мы можем использовать формулу Фолхабера [wiki] здесь, чтобы вычислить эту сумму, и получить:

(N+1)&times;(N<sup>2</sup>+5&times;N+6)/6

или в развернутом виде:

N<sup>3</sup>/6 + N<sup>2</sup> + 11&times;N/6 + 1

, то есть алгоритм O (n ³ ) .