Формирование рекуррентных отношений

Question

У меня вопрос о формировании рекуррентных отношений и вычислении временной сложности.

Если у нас есть рекуррентное соотношение T (n) = 2T (n/2) + c, то это означает, что постоянное количество работы c делится на 2 части T (n/2) + T (n/2)) при рисовании дерева рекурсии.

Теперь рассмотрим рекуррентное отношение факториала, которое является T (n) = n * T (n-1) + c. Если следовать описанному выше методу, то мы должны разделить работу c на n экземпляров каждого из T (n-1), а затем оценить временную сложность. Однако если вычислить таким образом, то ответ будет O (n^n), потому что мы будем иметь рекурсивные вызовы O (n^n), которые являются неправильными.

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

Answer 1

Позвольте рекуррентному соотношению быть T(n) = a * T(n/b) + O(n).

Это повторение означает, что существует рекурсивная функция, которая:

• делит исходную задачу в a подзадач
• размер каждой подзадачи будет n/b, если размер проблема является n
• когда подзадачи тривиальны (слишком легко решить), рекурсии не требуется, и они решаются напрямую (и этот процесс займет время O (n)).

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

Так, например, если функция:

int f(int n) 
{ 
    if(n <= 1) 
     return n; 
    return f(n-1) + f(n-2); 
} 

мы говорим, что проблема (размер n) делится на 2 подзадачи, размеров n-1 и n-2. Отношение повторения будет T(n) = T(n-1) + T(n-2) + c. Это связано с тем, что есть 2 рекурсивных вызова и с разными аргументами.

Но, если функция как:

int f(int n) 
{ 
    if(n <= 2) 
     return n; 
    return n * f(n-1); 
} 

мы говорим, что проблема (размер n) делится только 1 подзадачи, что размер n-1. Это потому, что есть только 1 рекурсивный звонок.

Таким образом, отношение повторения будет T(n) = T(n-1) + c.

Если мы умножим T(n-1) с n, а казалось бы нормально, мы передаем, что были n рекурсивные вызовы, сделанные.

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

Но, если вы говорите об , то значение будет функцией f(n) = n * f(n-1). Здесь мы умножаемся на n, потому что это фактическое значение, которое будет использоваться при вычислении.

Теперь, приходя в c в T(n) = T(n-1) + c; он просто предполагает, что, когда мы решаем проблему размера n, нам нужно решить меньшую проблему с размером n-1 и некоторые другие константы (постоянное время) работают как сравнения, умножения и возвращаемые значения.

Мы не можем разделить «постоянное количество работ c» на две части T(n/2) и T(n/2), даже используя рекурсивный метод дерева. На самом деле мы разделяем проблему на две половины. Тот же «c» объем работы будет необходим в каждом рекурсивном вызове на каждом уровне рекурсивного дерева.

Если возникло такое повторяющееся отношение, как T(n) = 2T(n/2) + O(n), где объем выполняемой работы зависит от размера ввода, тогда объем работы, выполняемой на каждом уровне, будет уменьшен на два уровня на следующем уровне, как описано выше ,

Но, если отношение повторения было как T(n) = T(n-1) + O(n), мы не будем делить объем работы на две половины на следующем уровне рекурсии. Мы просто уменьшаем объем работы на один на каждом последующем уровне (n -размерная проблема становится n-1 на следующем уровне).

Чтобы проверить, как изменится объем работы с рекурсией, примените метод замещения к вашему рекуррентному отношению.

Надеюсь, я ответил на ваш вопрос.