Решаване на T(n) = T(n - 1) + T(n - 2) - T(n - 3)

Времето на изпълнение на даден алгоритъм се дава от рекурентната връзка

T(n) = n if n ≤ 3

T(n) = T(n-1) + T(n-2) - T(n-3) в противен случай

Знам, че редът е n, n2, nn или n log n, но не знам кой. Опитах се да реша това, като използвах метода на заместване и метода на дървото на рекурсия, но не можах да постигна никакъв напредък. Някакви идеи?


recurrence math discrete-mathematics
person user3602083    schedule 04.05.2014    source източник
comment
Този въпрос изглежда не е по темата, защото е за дискретна математика, която е по-подходяща на math.stackexchange.com.   -  person templatetypedef    schedule 22.05.2014

Отговори (1)


arrow_upward
1
arrow_downward

Тук разширяването на няколко термина може да помогне:

  • T(1) = 1
  • T(2) = 2
  • T(3) = 3
  • T(4) = T(3) + T(2) - T(1) = 3 + 2 - 1 = 4
  • T(5) = T(4) + T(3) - T(2) = 4 + 3 - 2 = 5
  • T(6) = T(5) + T(4) - T(3) = 5 + 4 - 3 = 6

Общият модел тук изглежда е, че T(n) = n. Можем да формализираме това с индукция:

  • T(1) = 1, T(2) = 2 и T(3) = 3 по дефиниция.
  • T(n) = T(n - 1) + T(n - 2) - T(n - 3) = n - 1 + n - 2 - n + 3 = 2n + 3 - n - 3 = n

Надявам се това да помогне!

person templatetypedef    schedule 22.05.2014
comment
какво ще кажете, ако T(n) = T(n-1) + T(n-2) + T(n-3) също можем ли да използваме основна теорема в случай на + T(n-3) - person Arnab Dutta; 23.07.2018
comment
Не можете да използвате Главната теорема там, защото повторението няма правилната форма. Можете обаче да моделирате тази повторяемост като линейна хомогенна рекурентна връзка и да я разрешите, като използвате различни други техники. Потърсете „метода на анихилатора“ за подробности! - person templatetypedef; 23.07.2018