الفرق بين تدوين Big-O و Little-O

Question

ماهو الفرق بين كبير O. الرموز O(n) و Little-O الرموز o(n)?

Answer 1

F ∈ O (G) يقول ، بشكل أساسي

ل مرة على الأقل اختيار ثابت ك > 0 ، يمكنك العثور على ثابت أ بحيث يكون عدم المساواة 0 <= f (x) <= kg (x) يحمل لجميع x> a.

لاحظ أن O (G) هي مجموعة من جميع الوظائف التي يحملها هذه الحالة.

F ∈ O (G) يقول ، بشكل أساسي

ل كل اختيار ثابت ك > 0 ، يمكنك العثور على ثابت أ بحيث يكون عدم المساواة 0 <= f (x) <kg (x) يحمل لجميع x> a.

مرة أخرى ، لاحظ أن O (G) عبارة عن مجموعة.

في Big-O ، من الضروري فقط أن تجد مضاعفًا معينًا ك الذي يتجاوز عدم المساواة x.

في Little-O ، يجب أن يكون هناك حد أدنى x بعد ذلك ، يحمل عدم المساواة بغض النظر عن صغر حجمك ك, ، طالما أنها ليست سلبية أو صفر.

كلاهما يصف الحدود العليا ، على الرغم من أنه معاكس إلى حد ما ، إلا أن القليل من O هو البيان الأقوى. هناك فجوة أكبر بكثير بين معدلات نمو F و G إذا كان f ∈ O (g) مما لو f ∈ O (g).

أحد التوضيحات للتفاوت هو: f ∈ O (f) صحيح ، ولكن f ∈ O (f) خاطئة. لذلك ، يمكن قراءة Big-O على أنها "f ∈ O (G) تعني أن النمو المقارب لـ F ليس أسرع من G" ، في حين أن "F ∈ O (G) يعني أن النمو المقارب لـ F أبطأ تمامًا من G". انها مثل <= مقابل <.

وبشكل أكثر تحديداً ، إذا كانت قيمة G (x) مضاعفًا ثابتًا لقيمة f (x) ، فإن f ∈ O (g) صحيحة. هذا هو السبب في أنه يمكنك إسقاط الثوابت عند العمل مع تدوين Big-O.

ومع ذلك ، لكي تكون f ∈ O (g) صحيحة ، يجب أن تتضمن G أعلى قوة من X في صيغته ، وبالتالي يجب أن يصبح الفصل النسبي بين F (x) و g (x) أكبر مع زيادة حجم x.

لاستخدام أمثلة الرياضيات البحتة (بدلاً من الإشارة إلى الخوارزميات):

فيما يلي صحيح بالنسبة لـ Big-O ، ولكن لن يكون صحيحًا إذا استخدمت Little-O:

• x² ∈ O (x²)
• x² ∈ O (x² + x)
• x² ∈ O (200 * x²)

فيما يلي صحيح بالنسبة لـ Little-O:

• x² ∈ O (x³)
• x² ∈ O (x!)
• ln (x) ∈ O (x)

لاحظ أنه إذا كان f ∈ O (g) ، فهذا يعني f ∈ O (g). على سبيل المثال x² ∈ O (x³) لذلك صحيح أيضًا أن x² ∈ O (x³) ، (مرة أخرى ، فكر في O AS <= و س <)

Answer 2

Big-O هو Little-O ≤ هو ل <. Big-O هو الحد العلوي الشامل ، في حين أن Little-O هو الحد الأعلى الصارم.

على سبيل المثال ، الوظيفة f(n) = 3n هو:

• في O(n²), o(n²), ، و O(n)
• ليس في O(lg n), o(lg n), ، أو o(n)

بشكل مشابه ، العدد 1 هو:

• ≤ 2, < 2, ، و ≤ 1
• ليس ≤ 0, < 0, ، أو < 1

إليك طاولة ، تُظهر الفكرة العامة:

(ملاحظة: الجدول هو دليل جيد ولكن يجب أن يكون تعريف الحد الأقصى من حيث حد كبير بدلا من الحد الطبيعي. علي سبيل المثال، 3 + (n mod 2) يتأرجح بين 3 و 4 إلى الأبد. انها في O(1) على الرغم من عدم وجود حد طبيعي ، لأنه لا يزال لديه lim sup: 4.)

أوصي بحفظ كيف يتحول تدوين Big-O إلى مقارنات مقاربة. من الأسهل تذكر المقارنات ، ولكنها أقل مرونة لأنه لا يمكنك قول أشياء مثل n^{س (1)} = P.

Answer 3

أجد أنه عندما لا أستطيع فهم شيء ما ، أفكر لماذا يمكن للمرء استخدام x من المفيد فهم X. (لا تقل أنك لم تجرب ذلك ، فأنا فقط أقوم بإعداد المرحلة.)

الأشياء التي تعرفها] طريقة شائعة لتصنيف الخوارزميات هي عن طريق وقت التشغيل ، وبالاستشهاد بالتعقيد الكبير في الخوارزمية ، يمكنك الحصول على تقدير جيد جدًا من أي شخص "أفضل"-أيهما لديه وظيفة "أصغر" في س! حتى في العالم الواقعي ، O (n) "أفضل" من O (n²) ، باستثناء أشياء سخيفة مثل الثوابت الفائقة وما شابه. [/أشياء تعرفها

دعنا نقول أن هناك بعض الخوارزمية التي تعمل في O (n). جيد جدا ، هاه؟ ولكن دعنا نقول أنك (أنت شخص رائع ، أنت) توصلت إلى خوارزمية تعمل في O (^ن⁄_{loglogloglogn}). ياي! انه اسرع! لكنك تشعر بالسخافة في كتابة ذلك مرارًا وتكرارًا عندما تكتب أطروحتك. لذا ، فأنت تكتبها مرة واحدة ، ويمكنك أن تقول "في هذه الورقة ، أثبتت أن الخوارزمية X ، التي كانت قابلة للحساب مسبقًا في الوقت O (n) ، في الواقع قابلة للحساب في O (n)."

وبالتالي ، يعلم الجميع أن خوارزميةك أسرع --- إلى أي مدى غير واضح ، لكنهم يعرفون أسرع. نظريا. قون