حل التكرار [مغلق

Question

أحتاج إلى العثور على تعقيد التكرار الحالي:

T(n) = 1/(T(n-1) + 1) + 1

شكرًا مقدمًا على أي فكرة أو رابط بمعلومات مفيدة

Answer 1

التوسع على تعليقاتي أعلاه ...

هذا لا معنى له كعلاقة تكرار في العالم الحقيقي. T(n) يدل على وقت التشغيل لحل مشكلة الحجم n; T(n-1) يدل على وقت التشغيل للحجم (n-1). بالنظر إلى أنه يجب عليك حل المشكلة للحجم (n-1) قبل أن تتمكن من حل الحجم n (وإلا فإنه لن يكون عودة) ، يجب أن يكون وقت التشغيل بالضرورة رتابة كما n يزيد.

ومع ذلك ، فإن تعبيرك يتأرجح لأعلى ولأسفل n; ؛ هذا لا معنى له.

الطريقة الوحيدة التي يمكن أن يكون بها هذا التعبير منطقيًا هي إذا افترضنا ذلك T(n) ثابت مع n, ، بحيث لا يوجد تذبذب. اتضح أن هناك قيمة ثابتة تسمح بحدوث ذلك ، فقط تعيين T(n) = T(n-1), ، وحل. (لاحظ أن هذا لا معنى له بنفس القدر ؛ نحن لا نتحدث عمومًا مطلق قيم T(n).)