علاقة تكرارية:العثور على O الكبير

Question

أحاول العثور على O الكبير المرتبط بعلاقة التكرار التالية:

T(n) = T(n-1) + n^c, where c >= 1 is a constant

لذلك قررت حل هذه المشكلة باستخدام التكرار:

T(n) = T(n-1) + n^c
T(n-1) = T(n-2) + (n-1)^c
T(n) = T(n-2) + n^c + (n-1)^c
T(n-2) = T(n-3) + (n-2)^c
T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c
T(n) = T(n-k) + n^c + (n-1)^c + .... + (n-k+1)^c

Suppose k = n-1, then:

T(n) = T(1) + n^c + (n-1)^c + (n-n+1+1)^c
T(n) = n^c + (n-1)^c + 2^c + 1

لست متأكدًا مما إذا كان هذا صحيحًا أم لا، بالإضافة إلى أنني سأقدر حقًا بعض الإرشادات حول كيفية استخلاص Big O من هذا.شكرًا جزيلاً!

Answer 1

نعم، أنت صحيح:

t (n)= n ^{c + (n-1) c + (n-2) c + ... + 3 C + 2 C + 1،}

وهذا المبلغ هو

t (n)= o (n ^{c + 1 ).انظر على سبيل المثال صيغة faulhaber .في الواقع، يمكنك حتى تحديد الثابت في المدى الرائد (حتى لو لم يكن الأمر جيرمانيا على الخوارزمية): المبلغ هو N C + 1 / (C + 1) + O ( C )، كما يمكنك تحديد من خلال، باستخدام، قل، التكامل.}

Answer 2

ما لديك غير صحيح، لكنك كنت على المسار الصحيح.

الخطأ الذي صنعته:

giveacodicetagpre.

لا يمكنك الذهاب فقط من السطر الأول إلى السطر الثاني.

كما تزيد K، يزيد عدد المصطلحات في الجانب الأيمن أيضا.

لمعرفة هذا التفكير في كتابة ذلك بهذه الطريقة:

giveacodicetagpre.

ماذا يحدث إذا أضفت هذه؟

بمجرد القيام بذلك، هل يمكنك أن ترى ما ستكون الإجابة ل C= 1 و C= 2؟هل يمكنك معرفة نمط للإجابة النهائية من هناك؟

Answer 3

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

Answer 4

أود أن أبدأ بمراقبة أن n ^ c، أثناء التأثير بالطبع متأثرا بقيمة n، لن يكون أكثر تعقيدا ل n vs. + 1 - إنه ج يحدد "وقت التشغيل" الخاص بهذامصطلح.بالنظر إلى أنه، يمكنك أن تفترض (على الأقل سأفعل) أن المصطلح له وقت عمل ثابت وتحديد عدد المرات التي ستنفذ فيها العودية ل N معينة وستحصل على حدودك.

Answer 5

لمعرفة ذلك، املأ بضع من الناحية والبحث عن النموذج:

t (1)= 0 + 1 ^ c

t (2)= t (1) + 2 ^ c= 0 + 1 ^ c + 2 ^ c

t (3)= t (2) + 3 ^ c= 0 + 1 ^ c + 2 ^ c + 3 ^ c

t (4)= ...

تعبر الآن عن النمط من حيث ن ولديك إجابتك.

Answer 6

ها هو:

T(n) = n^c + (n-1)^c + (n-2)^c + ... + 2^c + 1^c
     < n^c +     n^c +     n^c + ... + n^c + n^c
     = n * n^c
     = n^(c+1)

وهو يا (ن^ج+1).

لإظهار أن هذا حد معقول، لاحظ أنه متى c = 1,

T(n) = n + (n-1) + (n-2) + ... + 2 + 1
     = n * (n-1) / 2

وهو بوضوح Θ(n²).