ن سجل ن هو O(ن)؟

Question

أحاول حل هذا التكرار

تي(ن) = 3 تي(ن/2) + ن إل جي ن ..

لقد توصلت إلى الحل الذي ينتمي إلى حالة نظرية الماجستير 2 حيث أن n lg n هو O(n^2)

ولكن بعد الرجوع إلى دليل الحل لاحظت هذا الحل الذي لديهم

يقول الحل أن n lg n = O ( n ^(lg 3 - e)) لـ e بين 0 و0.58

فهذا يعني أن n lg n هو O(n) ..هل هذا صحيح؟نسيت شيئا ما هنا؟

أليس nlgn O(n^2) ؟

Answer 1

سيشرح هذا الأمور بشكل أفضل

Answer 2

n*log(n) ليس O(n^2).يُعرف باسم شبه الخطي وينمو بشكل أبطأ بكثير من O(n^2).في الحقيقة n*log(n) أقل من كثير الحدود.

بعبارة أخرى:

O(n*log(n)) < O(n^k)

أين k > 1

في المثال الخاص بك:

3*T(2n) -> O(n^1.585)

منذ O(n^1.585) هو متعدد الحدود ويهيمن O(n*log(n)), ، يسقط المصطلح الأخير لذا يكون التعقيد النهائي عادلاً O(n^1.585).

Answer 3

n ^lg3 ليس O (n).إنها تتعدى O (n) ... في الواقع ، أي أس في n أكبر من 1 ينتج عنه وقت أطول بشكل مقارب من O (n).نظرًا لأن lg (3) يبلغ حوالي 1.58 ، طالما أنك تطرح أقل من .58 من الأس ، فستكون أكبر من O (n) بشكل مقارب.