Время работы этого алгоритма?

Question

Следующий алгоритм (использует динамическое c программирование) принимает входные данные: C - это целое число, p - это массив, содержащий целые числа, а n - это размер p. Обратите внимание, что этот код является псевдокодом.

Start(C, p, n)
   let mem[1..C, 1..n] be a multi-dimensional array
   for i=1 to C
      for j=1 to n
         mem[i,j] = -1
   return Count(C, p, n, mem)

Count(C, p, i, mem)
   if mem[C, i] >= 0
      return mem[C, i]
   if C==0
      q = 1
   elif n < 1 or C < 0
      q = 0
   else
      q = Count(C - p[i], p, i-1, mem) + Count(C, p, i-1, mem)
   mem[C, i] = q
   return q

Почему время выполнения этой реализации называется O (n *C)?

Для каждой подзадачи в Count , существует максимум i-1 подзадач, и мы решаем две из них, Count(C - p[i], p, i-1, mem) и Count(C, p, i-1, mem).

Таким образом, почему время выполнения не равно O (n ^ 2)? Я имею в виду, если мы для каждой подзадачи решаем подзадачи i-1 * 2, мы получим арифметический ряд c, который равен O (n ^ 2)? Если я не прав, скажите, пожалуйста:)

Наш C положительный, но в остальном он не ограничен. C может быть больше n, и в этом случае я вижу, что n*C > n*n, что подразумевает O(n*C) из-за инициализации массива в Start. Однако, если C меньше n, то n*C < n*n, что означает O(n^2). Так что вы скажете O(n*C) или O(n^2) - почему бы и нет?

Answer 1

Время выполнения этого кода O (n C). Одним из способов убедиться в этом является то, что в таблице содержится O (n C) элементов, и вы тратите O (1) времени на заполнение каждого из них, благодаря тому, как работает мемоизация.

Ваш вопрос сводится к тому, можете ли вы переписать O (n C) как O (n ² ). Это зависит от того, что C. Если C - это то, что может изменяться независимо от n (например, если C может быть 10 ²⁰ , а n = 3), то O (n C) нельзя упростить до O (n ² ).

С другой стороны, если C каким-то образом ограничено способом, зависящим от n (скажем, вы знаете, что C ≤ n), тогда Можно сказать, что время выполнения равно O (n ² ). Тогда возникает вопрос: является ли это полезным ограничением? O (n C) является более точным, чем O (n ² ), поскольку оно более прямо указывает на то, что стоимость времени выполнения зависит как от n, так и от C, а для малых C вы получите лучшее указание на то, сколько времени займет работа с O (n C), чем если бы вы использовали O (n ² ) в качестве границы.

Надеюсь, это поможет!