Асимптотическая аппроксимация рекуррентного отношения (Акра-Бацци, кажется, не применяется)

10

Предположим, что алгоритм имеет отношение повторения во время выполнения:

T(N)знак равно{г(N)+T(N-1)+T(δN):NN0е(N):N<N0

для некоторой константы . Предположим, что g полиномиально от n , возможно, квадратично. Скорее всего, f будет экспоненциальным по n .0<δ<1гNеN

Как можно было бы проанализировать время выполнения ( было бы отлично)? Основная теорема и более общий метод Акра-Бацци, похоже, не применяются.Θ

Остин Бьюкенен
источник
Найти хорошую нижнюю границу легко, но найти хорошую верхнюю границу сложно, но, грубо говоря, кажется, что она близка к . T(N)знак равноaT(N/a)+г(N)
1
Если вы все еще ищете ответ, вы должны проверить Грэма, Кнута и Паташника «Конкретная математика».
Каве
Предполагая, что является постоянным, нам не нужны какие-либо предположения о f , или мы? N0е
Рафаэль
Параметр может быть специфичным для экземпляра. Было бы неплохо увидеть, как время выполнения зависит от n 0 . N0N0
Остин Бьюкенен
1
Я задал соответствующий вопрос, который до сих пор не выдвинул никакой общей теоремы для повторений такого рода.
Рафаэль

Ответы:

5

Одним из возможных подходов может быть аналогия с дифференциальными уравнениями. Пусть . Здесь T ( n ) - дискретный аналог первой производной от T ( n ) . Мы получаем следующее соотношение: T ( n ) = T ( δ n ) + g ( n ) .T'(N)знак равноT(N)-T(N-1)T'(N)T(N)

T'(N)знак равноT(δN)+г(N),
Непрерывный аналог этого является дифференциальным уравнением или, если вы предпочитаете видеть , что это написано по- другому: д
T'(Икс)знак равноT(δИкс)+г(Икс),
Это дифференциальное уравнение.
ddИксT(Икс)знак равноT(δИкс)+г(Икс),

T(Икс)

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

DW
источник
Дональд Ньюман, кажется, часто использовал эту технику, и результаты были великолепными.
Арьябхата
T(Икс)