Временная сложность алгоритма с множественной рекурсией - PullRequest
Новая
       4

Временная сложность алгоритма с множественной рекурсией

0 голосов
/ 13 сентября 2018

Я пытаюсь понять сложность времени по поводу следующих алгоритмов: 

static int g(int[] a) {
  return g(a, 0, a.length-1);
}

static int g(int[] a, int i, int j) {
  if(i == j) return a[i];
  int onefourth = (j+1-i)/4;
  return g(a, i, i+onefourth) + g(a, i+onefourth+1, j);
}

Это моя попытка:

Алгоритм g (int [] a, int i, int j) разделяет размерность массива a на 4 и вызывает сам себя рекурсивно через множественную рекурсию. Я могу написать следующее уравнение рекуррентности T (n) = T (n / 4) + T (3n / 4) + c = .... = T (n / 4 ^ k) + T (3n / 4 ^ k) + кц. Здесь у меня есть проблема, чтобы выбрать значение к. Кто-нибудь может мне помочь?

1 Ответ

0 голосов
/ 13 сентября 2018

Я не знаю, каким методам вас учили, но я знаю, как бы я понял это с нуля.

Когда вы делите проблему, распределяйте стоимость рекурсивных вызовов на более низкий уровень пропорционально их размерам. Затем задайте вопрос о том, какое наибольшее значение может быть отнесено к любому значению в нижней части.

Вот что я имею в виду.

Если вы смотрите на диапазон длины 1, у вас будет постоянная стоимость c.

Если вы смотрите на диапазон длины 2, у вас будет постоянная рекурсивная стоимость r, деленная равномерно для стоимости элемента c+r/2.

Если вы смотрите на диапазон длины 3, то первый элемент будет стоить c + r/3, но последняя пара сначала получает 2/3 r на верхнем уровне, который затем делится на 2 с другой рекурсией. стоимость на общую сумму c + r/2 + r/3.

и т. Д.

Теперь вот проблема. Какую наибольшую рекурсивную стоимость можно отнести к определенному вызову? Наихудший случай где-то в цепочке - r для его уровня, плюс 3/4 r для уровня выше него, плюс (3/4)^2 r для уровня выше этого, и так далее. Можете ли вы найти верхнюю границу?

Можете ли вы превратить эту верхнюю границу в верхнюю границу стоимости, приписываемой одному элементу внизу?

Умножьте это число на количество элементов, и вы получите O(n).

...