كيفية حل:T(n) = T(n - 1) + n

Question

أنا عملت بها:

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

الآن عندما أعمل هذا أجد أن لا فضفاضة جدا.هل فعلت شيئا خاطئا أو هل هو فقط بهذه الطريقة ؟

Answer 1

أعتقد أنه من هذا الطريق:
في كل "تكرار" من العودية ، تقوم بعمل O (n).
كل تكرار يعمل N-1 للقيام به ، حتى ن = حالة قاعدة. (أفترض أن الحالة الأساسية هي O (n) العمل)
لذلك ، بافتراض أن الحالة الأساسية هي مستقل ثابت لـ n ، هناك تكرارات O (n) من العودية.
إذا كان لديك تكرارات n (n) تعمل لكل ، o (n)*o (n) = o (n^2).
تحليلك صحيح. إذا كنت ترغب في مزيد من المعلومات حول طريقة حل التكرارات ، فابحث في أشجار العودية. فهي بديهية للغاية مقارنة بالطرق الأخرى.

Answer 2

تحتاج أيضًا إلى حالة أساسية لعلاقة تكرارك.

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

لحل هذا ، يمكنك أولاً تخمين حل ثم إثبات أنه يعمل باستخدام الحث.

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

أولا القضية الأساسية. عندما ن = 1 يعطي C كما هو مطلوب.

للآخرين n:

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

لذلك يعمل الحل.

للحصول على التخمين في المقام الأول ، لاحظ أن علاقة تكرارك تولد أرقام ثلاثية عندما C = 1:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

إن المثلث بشكل حدسي هو نصف مربع تقريبًا ، وفي تدوين كبير ، يمكن تجاهل الثوابت بحيث O (n^2) هي النتيجة المتوقعة.

Answer 3

الحل سهل جدا لهذا واحد. عليك أن تنفجر العودية:

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n 

لديك تقدم الحساب هنا والمبلغ هو 1/2*n*(n-1). من الناحية الفنية ، تفتقد الشرط الحدود هنا ، ولكن مع أي حالة حدود ثابتة ترى أن العودة O(n^2).

Answer 4

يبدو عن الحق, ولكن سوف تعتمد على قاعدة القضية T(1).على افتراض أنك سوف تفعل n خطوات للحصول على T(n) T(0) و في كل مرة ن المصطلح في أي مكان بين 0 و n المتوسط n/2 حيث n * n/2 = (n^2)/2 = O(n^2).