التعقيد الحسابي تسلسل فيبوناتشي

Question

أنا أفهم Big-O التدوين ، ولكن لا أعرف كيفية حساب ذلك من أجل العديد من الوظائف.على وجه الخصوص, لقد تم في محاولة لمعرفة التعقيد الحسابي ساذجة نسخة من سلسلة فيبوناتشي:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

ما هو التعقيد الحسابي تسلسل فيبوناتشي و كيف يتم حسابها ؟

Answer 1

أنت نموذج الوقت وظيفة لحساب Fib(n) كما مبلغ من الوقت لحساب Fib(n-1) بالإضافة إلى الوقت لحساب Fib(n-2) بالإضافة إلى الوقت لإضافة معا (O(1)).هذا على افتراض أن عمليات التقييم المتكررة من نفس Fib(n) خذ نفس الوقت - أيلا التحفيظ هو استخدام.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

يمكنك حل هذا تكرار علاقة (باستخدام توليد الوظائف ، على سبيل المثال) و عليك في نهاية المطاف مع الجواب.

بدلا من ذلك, يمكنك رسم العودية شجرة ، والتي سوف يكون لها عمق n و حدسي معرفة أن هذه هي وظيفة مقارب O(2n).ثم يمكنك إثبات الظن بك عن طريق الاستقراء.

قاعدة: n = 1 واضح

نفترض T(n-1) = O(2n-1), لذلك

T(n) = T(n-1) + T(n-2) + O(1) الذي يساوي

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

ومع ذلك, كما ذكر في التعليق ، ليس هذا هو ضيق ملزمة.حقيقة مثيرة للاهتمام حول هذه الوظيفة هو أن T(n) هو مقارب نفس قيمة Fib(n) لأن كلا بأنها

f(n) = f(n-1) + f(n-2).

أوراق العودية شجرة دائما العودة 1.قيمة Fib(n) هو مجموع كل القيم التي يتم إرجاعها من قبل الأوراق في العودية الشجرة التي يساوي عدد من الأوراق.لأن كل ورقة تأخذ O(1) لحساب ، T(n) يساوي Fib(n) x O(1).وبالتالي ضيق لا بد لهذه الوظيفة هو فيبوناتشي نفسها (~θ(1.6n)).يمكنك معرفة هذا ضيق ملزمة باستخدام توليد الوظائف كما ذكرتها أعلاه.

Answer 2

وفقط اسأل نفسك كم من البيانات تحتاج إلى تنفيذ لF(n) لإكمال.

لF(1)، فإن الجواب هو 1 (الجزء الأول من الشرطي).

لF(n)، فإن الجواب هو F(n-1) + F(n-2).

وإذا ما وظيفة تلبي هذه القواعد؟ حاول <سوب> ن في (أ> 1):

وعلى <سوب> ن == ل<سوب> (ن 1) في + ل<سوب> (ن 2) في

وتقسيم من خلال من قبل <سوب> (ن 2) :

وعلى <سوب> 2 في == ل+ 1

وحل لa وتحصل (1+sqrt(5))/2 = 1.6180339887، والمعروف باسم الذهبي نسبة .

وهكذا يستغرق وقتا الأسي.

Answer 3

هناك لطيفة جدا مناقشة هذا مشكلة محددة في معهد ماساتشوستس للتكنولوجيا.في الصفحة 5 ، لأنها تجعل النقطة أنه إذا افترض أن إضافة يأخذ أحد الحسابية وحدة الوقت اللازم لحساب Fib(ن) ارتباطا وثيقا جدا نتيجة Fib(ن).

ونتيجة لذلك ، يمكنك القفز مباشرة إلى التقريب من سلسلة فيبوناتشي:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

ويقول بالتالي أن أسوأ الأحوال الأداء من السذاجة الخوارزمية

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS:هناك مناقشة إغلاق النموذج التعبير عن أقصى عدد فيبوناتشي في ويكيبيديا إذا كنت ترغب في مزيد من المعلومات.

Answer 4

وأنا أتفق مع pgaur وrickerbh والتعقيد عودي فيبوناتشي هو O (2 ^ ن).

وجئت إلى نفس النتيجة عن طريق التبسيط نوعا ما ولكن أعتقد أن المنطق لا يزال ساري المفعول.

أولا، انها كل شيء عن معرفة عدد المرات التي وظيفة فيبوناكسي عودي (F () من الآن فصاعدا) يحصل على استدعاء عند حساب عدد فيبوناتشي نطة. إذا كان يحصل يطلق عليه مرة واحدة لكل رقم في تسلسل 0 إلى n، ثم لدينا O (ن)، إذا كان يحصل على استدعاء ن مرات لكل رقم، ثم نحصل O (ن * ن)، أو O (ن ^ 2)، وهلم جرا.

وهكذا، عندما يتم استدعاء F () لعدد من ن، عدد مرات يسمى F () لعدد معين بين 0 و n-1 ينمو ونحن نقترب 0.

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

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

والآن، والسؤال هو، كيف بسرعة هي قاعدة هذا الهرم توسيع كما ينمو ن؟

ودعونا نلقي حالة حقيقية، على سبيل المثال F (6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

ونحن نرى F (0) يحصل على استدعاء 32 مرات، والذي هو 2 ^ 5، والتي لهذه الحالة عينة هو 2 ^ (ن 1).

والآن، نريد أن نعرف كم مرة (خ) يحصل على استدعاء F في كل شيء، ويمكننا أن نرى عدد مرات F (0) يسمى ليست سوى جزء من ذلك.

وإذا انتقلنا عقليا جميع * الصورة من F (6) لF (2) خطوط إلى F (1) الخط، ونحن نرى أن F (1) و F (0) خطوط الآن على قدم المساواة في الطول. وهو ما يعني، مرة الإجمالية F () يحصل على استدعاء عندما ن = 6 غير 2x32 = 64 = 2 ^ 6.

والآن، من حيث التعقيد:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Answer 5

ويمكنك توسيعه ولها تصور

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

Answer 6

ويحدها على أدنى حد من 2^(n/2) وعلى الطرف العلوي 2 ^ ن (كما ورد في تعليقات أخرى). وحقيقة مثيرة للاهتمام من أن تنفيذ العودية هو أن لديها مقارب ضيق بد من فيب (ن) نفسه. ويمكن تلخيص هذه الحقائق:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

ويمكن تخفيض باستخدام مزيد من rel="noreferrer"> إذا أردت.

Answer 7

والأجوبة واقية جيدة، ولكن لدي دائما إلى القيام ببعض التكرار من جهة لإقناع حقا نفسي. فرسمت من شجرة الدعوة صغيرة على بلدي السبورة، والتي عد العقد. أنا تقسيم التهم لي للخروج الى اجمالي العقد، والعقد ورقة، والعقد الداخلية. وهنا ما حصلت عليه:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

وماذا قفزات على الفور هو أن عدد رقة العقد هو fib(n). ما حدث بضعة تكرارات لاحظت أن عدد العقد الداخلية هو fib(n) - 1. وبالتالي فإن العدد الإجمالي من العقد هو 2 * fib(n) - 1.

ومنذ كنت إسقاط معاملات عند تصنيف التعقيد الحسابي، والجواب النهائي هو θ(fib(n)).

Answer 8

عودي الخوارزمية تعقيد الوقت يمكن أن يكون أفضل تقدير الرسم العودية شجرة, في هذه الحالة تكرار علاقة الرسم العودية شجرة سيكون T(n)=T(n-1)+T(n-2)+O(1) لاحظ أن كل خطوة يأخذ O(1) يعني وقت ثابت,لأنه لا واحد فقط مقارنة تحقق قيمة ن في إذا كتلة.العودية شجرة تبدو

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

هنا دعونا نقول كل مستوى من فوق الشجرة الرمز بواسطة أنا ومن ثم ،

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

يتيح القول في قيمة خاصة من أنا شجرة تنتهي هذه الحالة سيكون عندما n-i=1, وبالتالي i=n-1 ، وهذا يعني أن ارتفاع الشجرة هو n-1.الآن دعونا نرى كيف الكثير من العمل القيام به لكل من n طبقات في شجرة.لاحظ أن كل خطوة يأخذ O(1) الوقت كما جاء في تكرار علاقة.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

حيث i=n-1 هو ارتفاع الشجرة العمل المنجز في كل مستوى سوف تكون

i work
1 2^1
2 2^2
3 2^3..so on

وبالتالي مجموع العمل سوف مبلغ من العمل في كل مستوى ، ومن ثم سيكون 2^0+2^1+2^2+2^3...+2^(n-1) حيث i=n-1.من خلال سلسلة هندسية وهذا المبلغ هو 2^n, وبالتالي مجموع الوقت التعقيد هنا س(2^n)

Answer 9

حسنا، وفقا للي أن وO(2^n) كما هو الحال في هذه الوظيفة العودية فقط يأخذ وقتا طويلا (فرق تسد). ونحن نرى ذلك، سيستمر الدالة أعلاه في شجرة حتى يترك هي النهج عندما نصل إلى مستوى F(n-(n-1)) أي F(1). لذلك، وهنا عندما كنا ندون تعقيد الوقت اجه في كل عمق الشجرة، سلسلة الجمع هي:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

وهذا هو ترتيب 2^n [ O(2^n) ].

Answer 10

http://www.ics.uci.edu/~eppstein/161/960109.html

وقت(ن) = 3F(ن) - 2

Answer 11

ساذجة العودية نسخة من فيبوناتشي الأسي حسب التصميم بسبب الرسوب في حساب:

في جذور كنت الحوسبة:

F(n) يعتمد على F(n-1) و F(n-2)

F(n-1) يعتمد على F(n-2) مرة أخرى و F(n-3)

F(n-2) يعتمد على F(n-3) مرة و(ن-4)

ثم لديك في كل مستوى 2 العودية المكالمات التي يتم إضاعة الكثير من البيانات في حساب الوقت وظيفة سوف تبدو مثل هذا:

T(n) = T(n-1) + T(n-2) + C ، C المستمر

T(n-1) = T(n-2) + T(n-3) > T(n-2) ثم

T(n) > 2*T(n-2)

...

T(n) > 2^(ن/2) * T(1) = س(2^(ن/2))

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

وبالإضافة إلى ذلك, يمكنك أن تجد إصدارات محسنة من فيبوناتشي باستخدام البرمجة الديناميكية مثل هذا:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

هذا هو الأمثل والقيام فقط n الخطوات ولكن أيضا الأسي.

التكلفة وظائف محددة من حجم المدخلات إلى عدد من الخطوات لحل المشكلة.عندما ترى ديناميكية نسخة من فيبوناتشي (n خطوات حساب الطاولة) أو أسهل خوارزمية أن أعرف إذا كان عدد الوزراء (الجذر التربيعي(n) لتحليل صالح المقسومات عدد).قد تعتقد أن هذه الخوارزميات O(n) أو O(الجذر التربيعي(n)) ولكن هذا هو ببساطة ليس صحيحا للسبب التالي:المدخلات الخاصة بك خوارزمية عدد: n, باستخدام الترقيم الثنائي الإدخال حجم عدد صحيح n هو log2(n) ثم القيام متغير تغيير

m = log2(n) // your real input size

دعونا معرفة عدد الخطوات بوصفها وظيفة من حجم المدخلات

m = log2(n)
2^m = 2^log2(n) = n

ثم تكلفة خوارزمية الخاص بك بوصفها وظيفة من حجم المدخلات هي:

T(m) = n steps = 2^m steps

و هذا هو السبب التكلفة الأسي.