Решение 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