Нахождение линейного повторения (рекурсивного алгоритма) - PullRequest
Новая
       10

Нахождение линейного повторения (рекурсивного алгоритма)

1 голос
/ 08 июля 2019

Мне нужна помощь в поиске сложности рекурсивного алгоритма; Я знаю, что для решения этой проблемы мне нужно найти линейное повторение, а затем применить основную теорему. Насколько мне известно, найти повторение было бы просто, если рассматривать только один параметр;
В этом случае есть два параметра (i, j). Рассмотрим функцию, вызываемую ниже (A, 1, n): 

   integer stuff(integer [] A, integer i, integer j){
           if i ≥ j then return i – j 
           integer h ← 0
           for integer k ← 1 to floor((j – i + 1)/3) do {
              h ← h + 1
           }
           return stuff(A, i , i + h) + stuff(A, j – h, j) – stuff(A, i + h + 1, j – h − 1)
   }

Предполагая различные вещи, я угадал соотношение: 

T(1) = k  
T(n) = T(n/3) + T(n/3) + T(n/3) + 1/3*n = 3*T(n/3) + 1/3*n

Я предположил, что, поскольку похоже, что функция вызывается в 3 частях 3, каждая из которых составляет треть от n; будучи h = O (n / 3) 

First call: h+i-i = h ~ n/3   
Second call: j-(j-h) = h ~ n/3   
Third call: j-h-1-(i+h) = j-i-2h ~ n/3 (which I only assumed)

Даже если я могу попытаться угадать отношение и разобраться в нем, я не знаю, как формально доказать это.
Если мои предположения верны, как вы пришли к такому выводу? Если нет, то что мне не хватает?

Извините за длинный вопрос, заранее спасибо

1 Ответ

1 голос
/ 08 июля 2019

Поскольку вы return внутри for, это означает, что все время функция будет завершаться просто с постоянной сложностью!Потому что все время идет к циклу for и return значение функции и все заканчивается, и результат готов к возвращению.

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

Более того, если вы исправите псевдокод и поставите return в конце функции, сложность будет T(n) = 3T(n/3) + \Theta(n) (какты анализировал).Теперь из основной теоремы можно сказать, что T(n) = n log(n)).

...