علاقة تكرارية

Question

لماذا تعتبر علاقة تكرار الخوارزمية العودية؟

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

لماذا ليس هذا؟

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

وضع قيم n ie 1،2،3،4 ...... علاقة التكرار الثانية (يتم حساب العوامل الصكرية بشكل صحيح) وليس الأول.

Answer 1

هذا السؤال مربك للغاية ... أنت الصيغة الأولى ليست عازلة. إنه ببساطة t (n) = n + 1 ، لجميع n. عامل N N هو نتاج أول عدد إيجابي N: Factorial (1) = 1. Factorial (n) = n * factorial (N-1). صيغتك الثانية صحيحة بشكل أساسي.

Answer 2

يبدو أن t (n) هي علاقة تكرار تعقيد الوقت من الخوارزمية العودية العودية ، بافتراض تكاثر الوقت المستمر. ربما أخطأت في قراءة مصدرك؟

Answer 3

نستخدم علاقة التكرار عمومًا للعثور على التعقيد الزمني للخوارزمية.

---

هنا ، فإن الوظيفة t (n) ليست في الواقع لحساب قيمة العامل ولكنها تخبرك عن التعقيد الزمني للخوارزمية العازلة.

---

وهذا يعني للعثور على مصنع لـ n ، سيستغرق عملية واحدة أكثر من عامل N-1 (أي t (n) = t (n-1) +1) وهكذا.

---

لذا فإن علاقة التكرار الصحيحة لخوارزمية عودية عودية هي t (n) = 1 لـ n = 0 t (n) = 1+t (n-1) لـ n> 0 ليس كما ذكرت لاحقًا.

---

مثل تكرار برج hanoi هو t (n) = 2t (n-1) +1 لـ n> 0 ؛

Answer 4

أفترض أن لديك معلومات سيئة. علاقة التكرار الثانية التي تستشهد بها هو الصحيح ، كما لاحظت. أول واحد يولد فقط الأرقام الطبيعية.

Answer 5

أين وجدت الأول؟ إنه خاطئ تمامًا.

سيضيف فقط 1 في كل مرة كانت القيمة.

Answer 6

ما وضعه لم يكن العودية العليا ، ولكن التعقيد الزمني منه.
على افتراض أن هذا هو الرمز الكاذب لمثل هذا التكرار:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

• أنا أفترض أن القضاء على خلفية الذيل غير متورط.

يكلف السطر 2 و 3 وقتًا ثابتًا ، C1 و C2.
يكلف السطر 4 وقتًا ثابتًا أيضًا. ومع ذلك ، فإنه يطلق على Factorial (N-1) الذي سيستغرق بعض الوقت T (N-1). أيضًا ، يمكن تجاهل الوقت الذي يستغرقه مضاعفة الحقوق (N-1) بواسطة N بمجرد استخدام T (N-1).
الوقت للوظيفة بأكملها هو مجرد مجموع: T (n) = C1 + C2 + T (N-1).
يتم تقليل هذا ، في تدوين كبير O ، إلى t (n) = 1 + t (n-1).

هذا ، كما أشار القطر ، هو عودة مسطحة ، وبالتالي يجب أن يكون وقت التشغيل O (N). سيكون تعقيد الفضاء هائلا رغم ذلك.

Answer 7

t (n) = t (n-1) + 1 هي معادلة تكرار صحيحة لماكينة n. تمنحك هذه المعادلة الوقت لحساب عازف N وليس قيمة عازلة n.

Answer 8

أولاً ، يجب عليك العثور على عملية أساسية ولهذا المثال ، فهي تكاثر. يحدث الضرب مرة واحدة في كل عودية. لذلك t (n) = t (n-1) +1 هذا +1 هو التشغيل الأساسي (mutliplication لهذا المثال) t (n-1) هو استدعاء التكرار التالي.

Answer 9

TL ؛ DR: تعتمد الإجابة على سؤالك فعليًا ما تسلسل علاقة تكرارك تعريف. هذا هو ، ما إذا كان التسلسل ر_ن في سؤالك يمثل وظيفة العازلة أو تكلفة وقت التشغيل لحساب الوظيفة العليا^x.

---

وظيفة العازلة

ال العودية تعريف العازف ن, F_ن, ، هو:

F_ن = n • f_N-1 إلى عن على n> 0 مع F₀ = 1.

كما ترون ، المعادلة أعلاه هي في الواقع أ علاقة تكرارية, ، لأنه هو معادلة ذلك ، مع فترة أولية (بمعنى آخر، F₀ = 1), متكرر يحدد أ تسلسل (أي الوظيفة العليا ، F_ن).

---

نمذجة تكلفة وقت التشغيل لحساب العازف

الآن ، سنجد نموذج لتمثيل تكلفة وقت التشغيل لحساب العازف ن. لنتصل ر_ن ال تكلفة وقت التشغيل من الحوسبة F_ن.

النظر في التعريف أعلاه من الوظيفة العليا F_ن, ، تكلفة وقت التشغيل ر_ن سوف تتكون من تكلفة وقت التشغيل للحوسبة F_N-1 (أي هذه التكلفة ر_N-1) بالإضافة إلى تكلفة وقت التشغيل لأداء الضرب بين ن و F_N-1. يتم تحقيق الضرب في الوقت المستمر. لذلك يمكننا أن نقول ذلك ر_ن = ر_N-1 + 1.

ومع ذلك ، ما هي قيمة ر₀? ر₀ يمثل تكلفة وقت التشغيل للحوسبة F₀. منذ قيمة F₀ يُعرف في البداية بحكم التعريف ، تكلفة وقت التشغيل للحوسبة F₀ هو في الواقع ثابت. لذلك ، يمكننا أن نقول ذلك ر₀ = 1.

أخيرًا ، ما نحصل عليه هو:

ر_ن = ر_N-1 + 1 إلى عن على n> 0 مع ر₀ = 1.

هذه المعادلة أعلاه هي أيضا علاقة تكرارية. ومع ذلك ، فإن ما يحدده (جنبا إلى جنب مع المصطلح الأولي) ، هو تسلسل نماذج تكلفة وقت التشغيل لحساب الوظيفة العليا.

---

^x_{مع الأخذ في الاعتبار كيف تسمى التسلسل في علاقة تكرارك (أي ، رن) ، أعتقد أنه من المحتمل جدًا أن يمثل الأخير ، أي تكلفة وقت التشغيل لحساب الوظيفة العليا.}