Время выполнения нисходящего алгоритма программирования Dynami c

Question

Я придумал следующий алгоритм для задачи. в первую очередь для-l oop в строке 23-24, что делает меня неуверенным.

function TOP-DOWN-N(C, n, p)
  let N[1...n, 1...C] be a new array initialized to -1 for all indicies
  return N(C, n)

function N(C, n)
  if N[C,n] >= 0 then
    return N[C,n]
  if C < 0 or n < 1 then
    return 0
  elif C = 0 then
    return 1
  elif C > 0 and i > 0 then
    r = 0
    for i = 0 to n do
      r += N(C-p[n-i], n-(i+1))
    N[C,n] = r
    return N

Answer 1

Давайте проигнорируем тот факт, что этот алгоритм реализован рекурсивно. В общем, если алгоритм программирования Dynami c строит массив из N результатов, и для вычисления каждого результата требуется использовать значения k других результатов из этого массива, то его временная сложность составляет Ω (Nk), где Ω обозначает ниже связаны. Это должно быть понятно: требуется Ω (k), чтобы использовать k значений для вычисления результата, и вы должны сделать это N раз.

С другой стороны, если вычисление ничего не делает асимптотически более трудоемким, чем чтение k значений из массива, тогда O (Nk) также является верхней границей, поэтому сложность по времени составляет Θ (Nk).

---

Итак, по этим логам c мы должны ожидать, что временная сложность вашего алгоритма равна Θ (n ² C), поскольку он строит массив размером n C, для вычисления каждого результата используется Θ (n) других результатов из этого массив, и в этом вычислении не доминирует что-то еще.

Однако , ваш алгоритм имеет преимущество перед итеративной реализацией, потому что он не обязательно вычисляет каждый результат в массиве. Например, если число 1 отсутствует в массиве p, тогда ваш алгоритм не будет вычислять N(C-1, n') для любого n'; и если числа в p все больше или равны C, то l oop выполняется только один раз, и во время выполнения преобладает необходимость инициализировать массив размера n C.

Из этого следует, что Θ (n ² C) - сложность времени в наихудшем случае, а сложность времени в лучшем случае Θ (n C).