Большой вопрос О - Алгоритмический анализ III

У меня следующий вопрос:

Решите рекуррентное соотношение, упростив ответ, используя нотацию Big 'O':

f(0) = 2
f(n) = 6f(n-1)-5, n>0

Я знаю, что это неоднородное рекуррентное соотношение первого порядка, и я пытался ответить на вопрос, но я не могу получить правильный результат для базового случая (f (0) = 2).

Вопрос ДОЛЖЕН использовать формулу суммы геометрических рядов в доказательстве.

Вот мой ответ: Обратите внимание, что сумма (x = y, z) является заменой сигма-заглавной записи, где x – нижняя граница суммирования, инициализированного значением y, а z – верхняя граница суммирования:

1.  *change forumla:*
2.     f(n) = 6^n.g(n)
3.  => 6^n.g(n) = 6.6^(n-1) .g(n-1) -5   
4.  => g(n) = g(n-1)-5/6^n
5.  => g(n) = sum(i=1, n)-5/6^i
6.  => f(n) = 6^n.sum(i=1, n)-5/6^i
7.  => *Evaluate the sum using geometric series forumla*
8.  => sum(i = 1, n)-5/6^i = [sum(i = 1, n)a^i] -------> (a = -5/6)
9.  => *sub a = -5/6 into geometric forumla [a(1-a^n)/(1-a)]*
10. => [(-5/6(1 - (-5/6)^n))/(1-(-5/6))]
11. => g(n) = [(-5/6(1 + (5/6)^n))/(1+5/6)]
12. => f(n) = 6^n . g(n) = 6^n[(-5/6(1 + (5/6)^n))/(1+5/6)]
13. => *sub in n = 0 to see if f(0) = 2*

Во-первых, я уверен, что уравнение в строке 11 можно еще больше упростить, а во-вторых, подстановка в n = 0 должна дать в результате 2. Я не могу получить этот ответ при достижении строки 13...

РЕДАКТИРОВАТЬ: мне нужно знать, почему я не получаю f (0) = 2 при подстановке n = 0 в уравнение в строке 12. Также я хотел бы знать, как я могу упростить уравнение для f (n) в строке 12?

Кто угодно...?


recurrence algorithm big-o code-analysis
person user559142    schedule 12.04.2011    source источник
comment
@user559142: Это домашнее задание?   -  person abeln    schedule 12.04.2011
comment
Хорошо, может быть, это очевидно для всех, кроме меня... но какое это имеет отношение к большому-оу?   -  person Jeremy Powell    schedule 22.04.2011
comment
И когда вы спрашиваете «решить», вы имеете в виду, что вам нужна нерекурсивная функция, эквивалентная f?   -  person Jeremy Powell    schedule 22.04.2011
comment
Привет, Ответ нужно упростить под большим - о. Да, под решением я подразумеваю определение нерекурсивного решения в закрытой форме.   -  person user559142    schedule 22.04.2011

Ответы (1)


arrow_upward
2
arrow_downward

Не слишком задумываясь об этом, я скажу, что f(n + 1) в 6 раз больше, чем f(n), за вычетом константы. Таким образом, f (n) определенно равно O (6 ^ n). Хотя вы можете найти более жесткую границу, это примерно то, на что я бы пошел на практике!

Ради интереса попробую так:

f(1) = 6f(0) - 5
     = 6^1.f(0)
f(2) = 6f(1) - 5
     = 6(6f(0) - 5) - 5
     = 6^2.f(0) - 6^1.5 - 5
f(3) = 6f(2) - 5
     = 6^3.f(0) - 6^2.5 - 6^1.5 - 5

рискну предположить, что

f(n) = 6^n.f(0) - 5.(6^0 + 6^1 + ... + 6^(n-1))

и я почти уверен, что смогу доказать это по индукции в нескольких строчках (упражнение оставлено как упражнение для ученика).

Теперь,

sum (k in 0..n-1) 6^k  =  (1 - 6^n) / (1 - 6)

поэтому

f(n) = 6^n.f(0) - 5.(1 - 6^n) / (1 - 6)
     = 6^n.f(0) + (1 - 6^n)
     = 6^n.(2 - 1) + 1
     = 6^n + 1

подтверждая мою предыдущую интуицию.

Давайте просто сделаем несколько быстрых расчетов проверки:

f(0) = 2 = 6^0 + 1
f(1) = 6.2 - 5 = 7 = 6^1 + 1
f(2) = 6.7 - 5 = 37 = 6^2 + 1
f(3) = 6.37 - 5 = 237 = 6^3 + 1

Для домашнего задания мне достаточно :-)

person Rafe    schedule 12.04.2011
comment
извините, это не то, что я просил. - person user559142; 12.04.2011
comment
Ну, я думаю, ни одно доброе дело не остается безнаказанным. Жаль, что ты ничему не научился. - person Rafe; 13.04.2011
comment
@Rafe, ну, я только что попытался ответить сам себе, и примерно на полпути понял, что делаю именно то, что ты делал. +1 для вас. :) - person Jeremy Powell; 22.04.2011
comment
@Rafe, извини, я прочитал мой комментарий, и он прозвучал резко. То, как вы это сделали, кажется мне наиболее интуитивным, но, к сожалению, я ограничен методами, которые использовал выше. - person user559142; 22.04.2011
comment
@ user559142, без проблем. Вот где я думаю, что вы идете не так. - person Rafe; 23.04.2011
comment
@ user559142, извините, я только что увидел, что не закончил свой последний комментарий. Переходя от строки 4 к строке 5, вы делаете неверное предположение, что g(0) = 0, тогда как на самом деле g(0) = 2. - person Rafe; 01.05.2011