ما الفرق بين Θ(n) وO(n)؟

Question

أحيانًا أرى Θ(n) مع رمز Θ الغريب مع شيء ما في منتصفه، وأحيانًا أرى O(n) فقط.هل هو مجرد كسل في الكتابة لأنه لا أحد يعرف كيفية كتابة هذا الرمز، أم أنه يعني شيئًا مختلفًا؟

Answer 1

شرح مختصر:

إذا كانت الخوارزمية هي Θ(g(n))، فهذا يعني أن وقت تشغيل الخوارزمية عندما يصبح n (حجم الإدخال) أكبر يتناسب مع g(n).

إذا كانت الخوارزمية O(g(n))، فهذا يعني أن وقت تشغيل الخوارزمية مع زيادة n هو في الغالب يتناسب مع ز (ن).

عادة، حتى عندما يتحدث الناس عن O(g(n)) فإنهم يقصدون في الواقع Θ(g(n)) ولكن من الناحية الفنية، هناك فرق.

---

أكثر من الناحية الفنية:

يمثل O(n) الحد الأعلى.Θ (ن) يعني ملزمة ضيقة.Ω(n) يمثل الحد الأدنى.

f (x) = Θ (g (x)) iff f (x) = O(g(x)) وf(x) = Ω(g(x))

بشكل أساسي عندما نقول أن الخوارزمية هي O(n)، فهي أيضًا O(n²)، على^1000000) ، يا (2^ن)،...لكن خوارزمية Θ(n) موجودة لا Θ(ن²).

في الواقع، بما أن f(n) = Θ(g(n)) تعني أنه بالنسبة لقيم n الكبيرة بدرجة كافية، يمكن ربط f(n) داخل c₁ز(ن) و ج₂g(n) لبعض قيم c₁ و ج₂, ، أي.معدل نمو f يساوي بشكل مقارب g :يمكن أن يكون g الحد الأدنى و والحد الأعلى من f.هذا يعني بشكل مباشر أن f يمكن أن يكون حدًا أدنى وحدًا أعلى لـ g أيضًا.بالتالي،

f(x) = Θ(g(x)) إذا g(x) = Θ(f(x))

وبالمثل، لإظهار f(n) = Θ(g(n)))، يكفي إظهار g هو الحد الأعلى لـ f (أيf(n) = O(g(n))) و f هو الحد الأدنى لـ g (أيf(n) = Ω(g(n)) وهو نفس الشيء تمامًا مثل g(n) = O(f(n))).بإيجاز،

f(x) = Θ(g(x)) إذا f(x) = O(g(x)) و g(x) = O(f(x))

---

هناك أيضًا القليل من أوه والقليل من أوميغا (ω) الرموز التي تمثل الحدود العلوية والسفلية السائبة للدالة.

كي تختصر:

f(x) = O(g(x)) (كبير-أوه) يعني أن معدل نمو f(x) هل مُتَقَارِباً اقل او يساوي إلى معدل النمو g(x).

f(x) = Ω(g(x)) (بيج أوميغا) يعني أن معدل نمو f(x) هل مُتَقَارِباً أكبر من أو يساوي معدل النمو g(x)

f(x) = o(g(x)) (ليتل أوه) يعني ذلك معدل نمو f(x) هل مُتَقَارِباً أقل من ال معدل نمو g(x).

f(x) = ω(g(x)) (ليتل أوميغا) يعني أن معدل نمو f(x) هل مُتَقَارِباً أكثر من ال معدل نمو g(x)

f(x) = Θ(g(x)) (ثيتا) تعني أن معدل نمو f(x) هل مُتَقَارِباً يساوي ال معدل نمو g(x)

لمناقشة أكثر تفصيلا، يمكنك اقرأ التعريف على ويكيبيديا أو استشر كتابًا دراسيًا كلاسيكيًا مثل مقدمة للخوارزميات من تأليف كورمين وآخرين.

Answer 2

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

وجميع الرموز كبير-O يمكن اعتبار أن لها شريط.

عند النظر في Ω، شريط في أسفل، لذلك هو (مقارب) الأدنى.

عند النظر في Θ، شريط من الواضح في الوسط. لذلك هو (مقارب) ملزمة ضيق.

عند الكتابة اليدوية O، التي عادة ما تنتهي في الجزء العلوي، ورسم تمايل. لذا O (ن) هو الحد الأعلى من وظيفة. ولكي نكون منصفين، هذا واحد لا يعمل مع معظم الخطوط، ولكن هذا هو المبرر الأصلي من الأسماء.

Answer 3

واحد هو كبير "O"

واحد كبير ثيتا

http://en.wikipedia.org/wiki/Big_O_notation

والكبير O يعني أن الخوارزمية الخاصة بك تنفيذ في أي خطوات أكثر مما كانت عليه في التعبير معين (ن ^ 2)

والكبير أوميغا يعني أن الخوارزمية الخاصة بك تنفيذ في أي خطوات أقل مما كانت عليه في التعبير معين (ن ^ 2)

عند صحيحة على حد سواء شرطا لنفس التعبير، يمكنك استخدام ثيتا تدوين كبير ....

Answer 4

بدلاً من تقديم تعريف نظري، والذي تم تلخيصه بشكل جميل هنا بالفعل، سأقدم مثالاً بسيطًا:

افترض وقت التشغيل f(i) يكون O(1).يوجد أدناه جزء من التعليمات البرمجية الذي يكون وقت تشغيله مقاربًا Θ(n).هو - هي دائماً يستدعي الوظيفة f(...) n مرات.كل من الحد الأدنى والأعلى هو n.

for(int i=0; i<n; i++){
    f(i);
}

يحتوي الجزء الثاني من الكود أدناه على وقت التشغيل المقارب لـ O(n).انها تستدعي الوظيفة f(...) في الغالب n مرات.الحد الأعلى هو n، ولكن يمكن أن يكون الحد الأدنى Ω(1) أو Ω(log(n)), ، اعتمادا على ما يحدث في الداخل f2(i).

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Answer 5

وثيتا هي طريقة مختصرة للإشارة إلى situtation خاص حيث يا كبير وأوميغا هي نفسها.

وهكذا، إذا كان أحد يدعي The Theta is expression q، ثم هم أيضا يدعون بالضرورة أن Big O is expression q وOmega is expression q.

---

والقياس الخام:

إذا: يدعي ثيتا "هذا الحيوان لديه 5 الساقين". ثم يتبع ذلك: O كبير هو الصحيح ( "هذا الحيوان لديه أقل من أو يساوي 5 الساقين.") و أوميغا هو الصحيح ( "هذا الحيوان لديه أكثر من أو يساوي 5 الساقين.")

وانها مجرد التشبيه الخام بسبب التعابير ليست بالضرورة أرقام محددة، ولكن بدلا من ذلك ظائف أوامر من حجم مثل سجل (ن) متفاوتة، ن، ن ^ 2، (الخ).

Answer 6

الرسم البياني يمكن أن تجعل من الأجوبة السابقة أسهل لفهم ما يلي:

Θ-الترقيم - بنفس الترتيب | O-الترقيم - العليا ملزمة

في اللغة الإنجليزية،

في الجهة اليسرى، لاحظ أن هناك حدا أعلى والأدنى على حد سواء من نفس الترتيب من حيث الحجم (أي ز (ن) ). تجاهل الثوابت، وإذا كان الحد الأعلى والأدنى لها نفس الترتيب من حيث الحجم، يمكن القول صحيحا <م> و (ن) = Θ (ز (ن)) أو <م> و (ن) في ثيتا كبيرة من ز (ن) .

وبدءا من الحق، والمثال الأبسط، هو قائلا ان الحد الأعلى ز (ن) هو ببساطة أمر من حجم ويتجاهل ثابت <م> ج (تماما كما جميع <م> كبير O تدوين يفعل).

Answer 7

وf(n) ينتمي إلى O(n) في حالة وجود k إيجابيا f(n)<=k*n

وf(n) ينتمي إلى Θ(n) في حالة وجود k1 إيجابية، k2 كما k1*n<=f(n)<=k2*n

مقالة ويكيبيديا حول Big O تدوين

Answer 8

<اقتباس فقرة>   

والخلاصة: أننا نعتبر O كبير، Ω θ وكبيرة كبيرة كما الشيء نفسه.

     

لماذا؟ سأقول السبب أدناه:

     

أولا، أود أن أوضح بيان الخطأ واحد، وبعض الناس يعتقدون أننا مجرد الرعاية أسوأ وقت التعقيد، لذلك نحن دائما استخدام O كبير بدلا من θ كبير. أقول هذا الرجل bullshitting. تستخدم العلوي والسفلي ملزمة لوصف وظيفة واحدة، لا تستخدم لوصف تعقيد الوقت. أسوأ وظيفة الوقت ديها في العليا والأدنى. وظيفة أفضل وقت لديه للالعلوي والسفلي ملزمة للغاية.

     

في أجل شرح واضح للعلاقة بين O كبير وθ كبيرة، وأنا سوف يشرح العلاقة بين O كبيرة وصغيرة س أولا. من التعريف، يمكننا أن نعرف بسهولة أن صغيرة س هي مجموعة فرعية من O. كبير على سبيل المثال:

T (ن) = ن ^ 2 + ن، يمكننا أن نقول T (ن) = O (ن ^ 2)، T (ن) = O (ن ^ 3)، T (ن) = O (ن ^ 4). ولكن لس صغير، T (ن) = س (ن ^ 2) لا ينطبق عليه تعريف س الصغيرة. حتى مجرد T (ن) = س (ن ^ 3)، T (ن) = س (ن ^ 4) صحيحة لس الصغيرة. وT زائدة (ن) = O (ن ^ 2) ما هو؟ انها θ كبير!

<اقتباس فقرة>   

وعموما، فإننا نقول O الكبير هو O (ن ^ 2)، لا يكاد القول T (ن) = O (ن ^ 3)، T (ن) = O (ن ^ 4). لماذا ا؟ لأننا نعتبر O كبير بحجم θ شعوريا.

     

وعلى نحو مماثل، ونحن أيضا نعتبر Ω كبير بحجم θ شعوريا.

     

في كلمة واحدة، يا كبير، Ω θ وكبيرة كبيرة ليست الشيء نفسه عن التعريفات، بل هي نفس الشيء في فمنا والدماغ.

Answer 9

استخدام الحدود

دعونا نفكر f(n) > 0 و g(n) > 0 للجميع n.لا بأس في أخذ ذلك في الاعتبار، لأن أسرع خوارزمية حقيقية لديها عملية واحدة على الأقل وتكتمل تنفيذها بعد البداية.وهذا سوف يبسط حساب التفاضل والتكامل، لأنه يمكننا استخدام القيمة (f(n)) بدلا من القيمة المطلقة (|f(n)|).

1. f(n) = O(g(n))

   عام:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   ل g(n) = n:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   أمثلة:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   أمثلة مضادة:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f(n) = Θ(g(n))

   عام:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   ل g(n) = n:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   أمثلة:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   أمثلة مضادة:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0