العودية و Big O

Question

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

أوجد أفضل معدل نمو باستخدام ترميز big-Oh لحل التكرار التالي؟

ت(1) = 2

T(n) = 2T(n - 1) + 1 لـ n>1

والاختيارات هي:

• يا (ن سجل ن)
• يا (ن ^ 2)
• يا (2 ^ ن)
• يا (ن ^ ن)

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

إذن سؤالي هو:لماذا ليس هذا O(ن)؟

Answer 1

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

يمكنك استخدام الطريقتين الأخريين، ولكن أسهل طريقة لهذه المشكلة هي حلها بشكل متكرر.

ت(ن) = 2ت(ن-1) + 1
ت(ن) = 4ت(ن-2) + 2 + 1
ت(ن) = 8ت(ن-3) + 4 + 2 + 1
ت(ن) = ...

انظر النمط؟

ت(ن) = 2^ن-1⋅T(1) + 2^{ن -2} + 2^ن-3 + ... + 1
ت(ن) = 2^ن-1⋅2 + 2^{ن -2} + 2^ن-3 + ... + 1
ت(ن) = 2^ن + 2^{ن -2} + 2^ن-3 + ... + 1

وبالتالي فإن الحد الأضيق هو Θ(2^ن).

Answer 2

أعتقد أنك أساءت فهم السؤال قليلاً.لا يسألك عن المدة التي سيستغرقها حل التكرار.إنه يسأل ما هو الحجم الكبير (الحدود المقاربة) للحل نفسه.

ما عليك فعله هو التوصل إلى حل مغلق، أي.ه.الصيغة غير العودية لـ T(n)، ثم حدد ما هو الرقم الكبير لهذا التعبير.

Answer 3

السؤال يطلب ترميز كبير أوه لحل التكرار، وليس تكلفة حساب التكرار.

ضع طريقا اخر:التكرار ينتج:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

ما هي الرموز الكبيرة التي تصف التسلسل 2، 5، 11، 23، 47، ...

الطريقة الصحيحة لحل ذلك هي حل المعادلات التكرارية.

Answer 4

أعتقد أن هذا سيكون أسيًا.كل زيادة إلى n تجعل القيمة أكبر بمرتين.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

سيكون T(x) هو وقت تشغيل البرنامج التالي (على سبيل المثال):

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 5

أعتقد أن هذا سيكون الأسي.كل زيادة إلى n تجلب ضعف الحساب.

لا، لا.على العكس تماماً:

النظر في ذلك ل ن التكرارات، نحصل على وقت التشغيل ر.ثم ل ن + 1 التكرارات التي سنحصل عليها بالضبط ر + 1.

وبالتالي، فإن معدل النمو ثابت ووقت التشغيل الإجمالي ثابت بالفعل يا(ن).

لكن أعتقد أن افتراض ديما حول السؤال صحيح رغم أن حله معقد للغاية:

ما عليك فعله هو التوصل إلى حل مغلق، أي.ه.الصيغة غير العودية لـ T(n)، ثم حدد ما هو الرقم الكبير لهذا التعبير.

يكفي فحص الحجم النسبي لـ ت(ن) و ت(ن + 1) التكرارات وتحديد معدل النمو النسبي.من الواضح أن المبلغ يتضاعف مما يعطي النمو المقارب بشكل مباشر.

Answer 6

أولاً، جميع الإجابات الأربعة أسوأ من O(n)...O(n*log n) أكثر تعقيدًا من O(n) القديم العادي.ما هو أكبر:8 أو 8*3، 16 أو 16*4، الخ...

إلى السؤال الفعلي.من الواضح أنه يمكن حل الحل العام في وقت ثابت إذا كنت لا تقوم بالتكرار

( T(n) = 2^(n - 1) + 2^(n) - 1 )، إذًا هذا ليس ما يطلبونه.

وكما ترى، إذا كتبنا الكود التكراري:

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

من الواضح أنه O(n).

لذا، يبدو أن السؤال مكتوب بشكل سيئ، ومن المحتمل أنهم يطلبون منك تطوير الوظيفة نفسها، وليس تعقيد التعليمات البرمجية.هذا هو 2 ^ ن.اذهب الآن وقم ببقية واجباتك المنزلية..وادرس على O(n * log n)

Answer 7

من السهل حساب حل النموذج المغلق للتكرار.وبالتفتيش تظن أن الحل هو

T(n) = 3*2^(n-1) - 1

ثم تثبت بالاستقراء أن هذا هو الحل بالفعل.الحالة الأساسية:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

تعريفي:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

حيث تنبع المساواة الأولى من تعريف التكرار ، والثاني من الفرضية الاستقرائية.QED.

3*2^(n-1) - 1 هو بوضوح ثيتا(2^n)، وبالتالي فإن الإجابة الصحيحة هي الثالثة.

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