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

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

6 голосов
/ 12 апреля 2011

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

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

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

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

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

Вот мой ответ - Обратите внимание, что сумма (x = y, z) является заменой заглавной сигма-записи, где x - это нижняя граница суммирования, инициализированного у, а 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?

Кто-нибудь ...?

1 Ответ

2 голосов
/ 12 апреля 2011

Не задумываясь об этом, я скажу, что 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

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

...