حل علاقة تكرار استخدام التكرار طريقة

Question

وجرب هذا المثال:

T(n) = T(7n/8) + 2n 

وتوليت T (1) = 0

ووحاول حلها بالطريقة التالية

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

ولكن أنا لا يمكن أن يأتي إلى أي استنتاج حول هذا الموضوع. فأنا في حيرة حول ما يجب فعله في الخطوة التالية.

Answer 1

والنهج الخاص بك هو الصوت، ولكن سترى ما يجب القيام به إذا كنت إعادة كتابتها بشكل مختلف قليلا:

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

والآن، دعونا k تميل إلى ما لا نهاية ونرى ما سيحدث. سيكون من المفيد إذا كنت على دراية هندسية سلسلة .

Answer 2

وT (ن) = T (7N / 8) + 2N = 2N * (1 + 7/8 + (7/8) ^ 2 + (7/8) ^ Z) + T (1) حيث Z =؟

والحيلة الوحيدة هي العثور Z. أراهن سوف يساعد السجل. آسف فوات، وأنا لا أفكر مباشرة، ولكن ... يجب أن لا حاجة لإضافة 2N المتعدد.

وتحرير: Z هو كم من الوقت تحتاج لمضاعفة ن من 7/8 حتى تحصل على 1

وهكذا، ن * 7 ^ Z / 8 ^ Z = 1

و(7/8) ^ Z = 1 / ن

و(8/7) ^ Z = ن

وترغب في حل لZ.

Answer 3

ما الذي حصل لك هناك في السطر الأخير هو متسلسلة هندسية وهناك < وأ href = "http://en.wikipedia.org/wiki/Geometric_series#Formula" يختلط = "noreferrer نوفولو"> صيغة لتبسيط مثل هذا المبلغ.