Asymptotyczne przybliżenie relacji nawrotu (wydaje się, że nie ma zastosowania Akra-Bazzi)

Załóżmy, że algorytm ma relację powtarzalności środowiska wykonawczego:

$T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 \end{array} \right.$

dla niektórych stałych . Załóżmy, że jest wielomianem w , być może kwadratowym. Najprawdopodobniej będzie wykładnicze w . $0 < \delta < 1$ $g$ $n$ $f$ $n$

Jak przejść do analizy środowiska wykonawczego ( byłoby doskonałe)? Wydaje się, że nie można zastosować twierdzenia głównego i bardziej ogólnej metody Akra-Bazzi. $\Theta$

asymptotics recurrence-relation

— Austin Buchanan
źródło

T (n) = a \cdot T (n / a) + g (n)

$T(n) = a\cdot T(n/a) + g(n)$

Jeśli nadal szukasz odpowiedzi, sprawdź Grahama, Knutha i Patashnika, „Matematyka konkretna”.

— Kaveh

n_{0}

$n_0$

f

$f$

n_{0}

$n_0$

n_{0}

$n_0$

Zadałem pokrewne pytanie, które jak dotąd nie wysunęło żadnego ogólnego twierdzenia o nawrotach tego rodzaju.

— Raphael

$T'(n) = T(n)-T(n-1)$ $T'(n)$ $T(n)$

T^{'} (n) = T (⌊ δ n ⌋) + g (n) .

$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$

t^{'} (x) = t (δ x) + g (x),

$t'(x) = t(\delta x) + g(x),$

\frac{d}{d x} t (x) = t (δ x) + g (x) .

${d \over dx} t(x) = t(\delta x) + g(x).$

$t(x)$

Zapomniałem wszystkiego, co kiedyś wiedziałem o równaniach różniczkowych, więc nie znam rozwiązania tego równania różniczkowego, ale być może uda się go rozwiązać, przeglądając wszystkie techniki rozwiązywania równań różniczkowych.

— DW
źródło

Wydaje się, że Donald J Newman często stosował tę technikę, osiągając świetne wyniki.

— Aryabhata,

t (x)

$t(x)$