o (FIB N) خوارزميات التعقيد؟

Question

أثناء المشاهدة محاضرة 1 ب من هيكل وتفسير برامج الكمبيوتر, ، هناك وظيفة تحسب أرقام فيبوناتشي. يشير المحاضر إلى أن التعقيد الزمني هو o (fib n) - لم أر ذلك من قبل. لقد رأيت أنها مدورة إلى التعقيد الثابت أو الخطي أو N+M أو التربيعي أو متعدد الحدود أو التعقيد الأسي ، ولكن هل هناك أي خوارزميات أخرى من O (fib n) أو غيرها من الرموز الكبيرة المثيرة للاهتمام التي ينبغي النظر إليها أو دراستها؟

Answer 1

O(fib N) ليس شيئًا غريبًا أو خاصًا - إنه نفس الشيء تمامًا مثل التعقيد الأسي - إنه مجرد أن المحاضر لم يأخذ الوقت الكافي لتوضيحه. (يمكنك بسهولة* ملزمة fib(N) مع phi^n.)

ليس عليك أن تصدقني - سيكون لديك تفسير أفضل على MATH.STACKEXCHANGE.

*: سأوضح ما أعنيه بـ "بسهولة" - فهذا يعني أن الدليل متاح بسهولة ، على سبيل المثال في هذا المقال ويكيبيديا (بفضل المستجيب السابق الذي أعطى في الأصل الرابط إليه).