Как решить: T (n) = T (n / 2) + T (n / 4) + T (n / 8) + (n)

Question

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

Например:

T(n) = T(n/2) + T(n/4) + T(n/8) + (n)

Answer 1

Использовать дерево рекурсии. См. Последний пример дерева рекурсии в CLRS "Введение в алгоритм".

T (n) = T (n / 2) + T (n / 4) + T (n / 8) + n. Корень будет n (стоимость) и разделен на 3 рекурсии. Итак, дерево рекурсии выглядит следующим образом:

T (n) = n = n T (n / 2) T (n / 4) T (n / 8) (n / 2) (n / 4) (n / 8) T (n / 4) T (n / 8) T (n / 16) T (n / 8) T (n / 16) T (n / 32) T (n / 16) T (n / 32) T ( п / 64)

                                             n---------------------------------> n      

                             (n/2)         (n/4)           (n/8)--------------> (7/8)n

                         n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n
                                            ...         

Самый длинный путь: левая левая ветвь = n -> n / 2 -> n / 4 -> ... -> 1

Самая короткая ветвь: самая правая правая ветвь = n -> n / 8 -> n-> 64 -> ... -> 1

Количество листьев (l): 3 ^ log_8 (n) n ^ 0.5

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

T (n) = Big-Oh (Суммирование j = 0 до log_2 (n) -1 (7/8) ^ j n) = ... => T (n) = O (n). T (n) = Биг-Омега (Суммирование j = 0 до log_8 (n) -1 (7/8) ^ j n) = ... => T (n) = Биг-Омега (n).

Следовательно, T (n) = Theta (n).

Вот пункты: Т (н / 2) путь имеет наибольшую длину ...

Это не должно быть полное троичное дерево ... высота = основание журнала 2 из n & # листьев должно быть меньше, чем n ...

Надеюсь, вероятно, таким образом вы сможете решить проблему.

Answer 2

Есть два способа решения этой проблемы. Одним из них является развертывание рекурсии и поиск сходств, которые могут потребовать изобретательности и могут быть действительно сложными. Другой способ - использовать метод Акра-Бацци .

В этом случае g(x) = n, a1 = a2 = a3 = 1 и b1 = 1/2, b2 = 1/4, b3 = 1/8. Решение уравнения

то есть 1/2^p + 1/4^p + 1/8^p = 1 вы получите p = 0.87915. Решив интеграл, вы получите , что означает, что сложность равна: O(n)

Answer 3

Как сказал CLRS, T(n) можно заменить на cn математической индукцией.Это индуктивное предположение работает для числа ниже n.Как упоминалось выше, нам нужно доказать, что значение параметра равно n.Поэтому, следующим образом: предположим: T(n) <= cn для числа ниже n;вывод:

T(n) = T(n/2) + T(n/4) + T(n/8) + n
    <= c/2*n + c/4*n + c/8*n + n
     = (7/8*c + 1) * n
    <= cn (when c >= 8)

вот и все.

Answer 4

Точно так же, как кодирование последовательности Фибоначчи (сложный путь) в качестве примера, вы просто наберете что-то вроде:

long fib(long n){
 if(n <= 1) return n; 
 else return fib(n-1) + fib(n-2);
}     

Или, что еще лучше, запомните это, используя глобальную переменную, чтобы сделать это намного быстрее. Еще раз, с последовательностью Фибоначчи:

static ArrayList<Long>fib_global = new ArrayList(1000); 
  //delcare a global variable that can be appended to
long fib(long n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   return fib_global.get(n);
}

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