Временная сложность рекурсивной функции, вызываемой переменным в цикле - PullRequest
Новая
       28

Временная сложность рекурсивной функции, вызываемой переменным в цикле

2 голосов
/ 21 марта 2019

Какова будет временная сложность этой функции: 

 public int calculate(int[] arr, int index) {
  int max = 0, sum = 0;
  for (int i = index; i < arr.length && i < index + arr[index]; i++) {
    sum += arr[i];
    max = Math.max(max, calculate(arr, i + 1));
  }
  return Math.max(max, sum);
}

Функция вызывается с массивом и индексом. Поскольку функция выполняет рекурсивные вызовы arr [index], можем ли мы сказать, что ее временная сложность равна O (max (arr) ^ n) («n» - число элементов в arr)? Можно ли найти более жесткий лимит? Сложность времени определенно не 2 ^ n, верно?

1 Ответ

3 голосов
/ 21 марта 2019

Давайте сначала удалим часть i < index + arr[index] из условия цикла, что только (иногда) уменьшит количество итераций. Удалив его, мы можем получить худший случай.

Поскольку в каждой итерации цикла вызывается функция, подсчет количества выполнений функции (на любой глубине рекурсии) является хорошим показателем сложности времени. Давайте назовем это число c .

Теперь определим k как число итераций цикла без учета рекурсии, поэтому k равно arr.length - i

c зависит от k , поэтому давайте поговорим о c k

Для k = 0 итерации нет, поэтому достаточно одного вызова, поэтому c 0 = 1 . Мы можем продолжить увеличение k :

c 1 = 1 + c 0 = 2
c 2 = 1 + c 0 + c 1 = 2c 1 = 4
c 3 = 1 + c 0 + c 1 + c 2 = 2c 2 = 8
...
c k = 1 + ∑ k-1 i = 0 (c i ) = 1 + ∑ k-2 i = 0 (c i ) + c k-1 = 2.c k-1 = 2 k

Когда вы вызываете функцию с помощью i=0 и определяете n как arr.length, тогда вывод состоит в том, что функция имеет временную сложность O (2 n )

...