ما الفرق بين O وΩ وΘ؟

Question

أنا أتعلم تحليل الخوارزمية.أجد صعوبة في فهم الفرق بين O وΩ وΘ.

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

• f(n) = O(g(n)) وسائل c · g(n) هو الحد الأعلى f(n).وبالتالي هناك بعض الثابت c مثل ذلك f(n) هو دائما ≤ c · g(n), ، لحجم كبير بما فيه الكفاية n(أي.، n ≥ n0 لبعض ثابت n0).
• f(n) = Ω(g(n)) وسائل c · g(n) هو الحد الأدنى على f(n).وبالتالي هناك بعض الثابت c مثل ذلك f(n) هو دائما ≥ c · g(n), للجميع n ≥ n0.
• f(n) = Θ(g(n)) وسائل c1 · g(n) هو الحد الأعلى على f(n) و c2 · g(n) هو الحد الأدنى على f(n), للجميع n ≥ n0.وبالتالي هناك ثوابت c1 و c2مثل ذلك f(n) ≤ c1 ·g(n) و f(n) ≥ c2 ·g(n).هذا يعني ذاك g(n)يوفر ربطًا لطيفًا ومحكمًا f(n).

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

• O(f(n)) يعطي أسوأ حالة تعقيد للوظيفة/الخوارزمية المحددة.
• Ω(f(n)) يعطي أفضل تعقيد لحالة الوظيفة/الخوارزمية المحددة.
• Θ(f(n)) يعطي متوسط ​​تعقيد الحالة لوظيفة/خوارزمية معينة.

يرجى تصحيح لي إذا كنت مخطئا.إذا كان الأمر كذلك، فيجب التعبير عن التعقيد الزمني لكل خوارزمية في جميع الرموز الثلاثة.لكنني لاحظت أنه يتم التعبير عنها إما بـ O أو Ω أو Θ؛لماذا لا الثلاثة؟

Answer 1

من المهم أن نتذكر أن الترميز، سواء كان O أو Ω أو Θ، يعبر عن النمو المقارب للوظيفة;ليس لها أي علاقة جوهريًا بالخوارزميات في حد ذاته.الوظيفة المعنية يمكن يكون "التعقيد" (وقت التشغيل) للخوارزمية، إما الحالة الأسوأ، أو الحالة الأفضل، أو الحالة المتوسطة، ولكن التدوين مستقل عن مصدر الوظيفة.

على سبيل المثال، الدالة f(n)=3n²+5 هو:

• على²) ، وهو أيضًا O(n²سجل ن)، يا (ن³)، على⁴) وما إلى ذلك، ولكن ليس O(n).
• Ω(ن²)، فهو أيضًا Ω(n log n)، Ω(n) وما إلى ذلك، ولكنه ليس Ω(n³).
• Θ(ن²).إنها ليست حتى Θ(n²سجل ن) أو Θ(ن²/سجل ن).

الآن، عادة ما تكون الوظيفة التي يتم النظر فيها هي أسوأ حالة تعقيد للخوارزمية، وأي تدوين للثلاثة يتم استخدامه يعتمد على ما نريد أن نقوله عنها وعلى مدى دقة إجراء التحليل.على سبيل المثال، قد نلاحظ أنه نظرًا لوجود حلقتين متداخلتين، فإن أسوأ وقت للتشغيل هو في الغالب على²)، دون الاهتمام بما إذا كان هذا قد تم تحقيقه بالفعل لبعض المدخلات.(عادة ما يكون الأمر واضحًا). أو يمكننا القول أن أسوأ وقت تشغيل للفرز هو Ω(n log n)، لأنه يجب أن يكون هناك بعض المدخلات التي يجب أن يستغرقها على الأقل cn(log n) خطوات.أو قد ننظر إلى خوارزمية فرز دمج معينة، ونرى أنها تستغرق خطوات O(n log n) على الأكثر في أسوأ الحالات و أن بعض المدخلات تجعلها تستغرق خطوات n log n، وبالتالي فإن وقت التشغيل الأسوأ هو Θ(n log n).

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

Answer 2

Θ يدل على الحد العلوي والسفلي الضيق بشكل مقارب.

يشير O إلى حد أعلى، ولكن هذا الحد قد يكون أو لا يكون ضيقًا.
o يدل على الحد الأعلى غير الضيق.

تشير Ω إلى الحد الأدنى، ولكن هذا الحد قد يكون أو لا يكون ضيقًا.
ω يشير إلى الحد الأدنى غير الضيق.

Answer 3

هذه بعض الموارد التي ستساعدك حقًا:

• ويكيبيديا
• كتاب ويكي
• فيديو محاضرة معهد ماساتشوستس للتكنولوجيا
• فيديو من IITB، الهند

Answer 4

لمعرفة ما يعنيه هؤلاء الثلاثة، راجع إجابة جان بيرك جودر.

لاحظ أيضًا أنه لا علاقة لها على الإطلاق بأفضل الحالات وأسوأ الحالات ومتوسط ​​الحالات.الفرز الفقاعي على سبيل المثال هو أفضل حالة Θ(n) (لأنه إذا تم فرز البيانات بالفعل، فستكون هناك حاجة فقط إلى مقارنات n-1)، وΘ(n^2) أسوأ حالة.إنها الحالة المتوسطة Θ(n^2) التي تفترض إدخالاً عشوائيًا.وبالتالي فإن هذه الحالة المتوسطة هي أيضًا O(n^2) وO(n^3) وO(2^n).

إذن، O وΘ وΩ يخبرونك بنوع الارتباط.لا يخبرونك بما هو الحد الأقصى.في السياق، قد يكون هذا حدًا للحالة الأفضل، أو الحالة الأسوأ، أو الحالة المتوسطة، أو الخوارزمية ككل (جميع الحالات).

بالطبع إذا كانت الخوارزمية تحتوي على أفضل حالة Ω(g)، فهي في حد ذاتها Ω(g).إذا كان لديه O(g) في أسوأ الأحوال فهو O(g).لذلك هناك علاقة هناك.ولكن إذا كانت تحتوي على حالة متوسطة Θ(g)، فهذا لا يخبرك تقريبًا بأي شيء عن أفضل الحالات وأسوأها.

أما بالنسبة لـ "لماذا ليس الثلاثة؟".

إذا كانت وظيفتك هي Θ(g)، فهي أيضًا O(g) وΩ(g).لذلك ليس هناك فائدة كبيرة من توفير حدود أخرى إلى جانب الحد Θ.

عندما ترى أحد الآخرين بمفرده، فذلك عمومًا لأننا نهتم فقط بالحد الأعلى، أو نهتم فقط بالحد الأدنى.لذلك نقول أن جميع أنواع المقارنة هي بالضرورة أسوأ حالة Ω(n log n)، وهذا النوع الفقاعي هو O(n^2) أسوأ حالة ولكن O(n) أفضل حالة، لأننا لا نحاول وصف الوقت بشكل كامل التعقيد، نحن فقط نعبر عن الحدود التي نهتم بها في سياق معين.

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

Answer 5

غالبًا ما يُشار إلى تدوين Big-O على أنه تعقيد الخوارزمية لأنه يؤكد لنا أن أداء الخوارزمية لن يكون أسوأ بكثير بالنسبة إلى n الكبيرة.ومع ذلك، كما تمت الإشارة إليه سابقًا، فإن Big-O يمنحنا التقييم المقارب وقد تتصرف خوارزميتنا بشكل مختلف عند إعطاء مدخلات معينة.على سبيل المثال، يمكن أن يكون الفرز السريع هو O(n^2)، عندما يكون المصفوفة مرتبة بالفعل.OTOH، يمكن تحسين الوضع المقارب عمليًا من خلال التنفيذ الدقيق.