وأوضح ثيتا الكبيرة والترميز المقارب

يخبرنا Big Omega بالحد الأدنى لوقت تشغيل الدالة ، ويخبرنا Big O بالحد الأعلى.

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

بشكل عام ، نريد دائمًا أن نعطي ثيتا ملزمًا إن أمكن لأنه أكثر الحدود دقة وإحكامًا. إذا لم نتمكن من إعطاء قيمة ثيتا ، فإن أفضل شيء تالي هو أضيق حد ممكن لـ O.

خذ ، على سبيل المثال ، دالة تبحث في مصفوفة عن القيمة 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. ما هي أفضل حالة؟ حسنًا ، إذا كانت المصفوفة التي أعطيناها تحتوي على 0 كقيمة أولى ، فسيستغرق وقتًا ثابتًا: Ω (1)
  2. ما هي أسوأ حالة؟ إذا كانت المصفوفة لا تحتوي على 0 ، فسنقوم بالتكرار خلال المصفوفة بأكملها: O (n)

لقد أعطيناها أوميغا و O مقيد ، فماذا عن ثيتا؟ لا يمكننا أن نعطيها واحدة! اعتمادًا على المصفوفة التي نقدمها ، سيكون وقت التشغيل في مكان ما بين الثابت والخطي.

دعنا نغير الكود الخاص بنا قليلا.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

هل يمكنك التفكير في أفضل وأسوأ حالة ؟؟ لا استطيع! بغض النظر عن المصفوفة التي نعطيها ، علينا أن نكرر كل قيمة في المصفوفة. لذا ستستغرق الوظيفة على الأقل n من الوقت (Ω (n)) ، لكننا نعلم أيضًا أنها لن تستغرق وقتًا أطول من n (O (n)). ماذا يعني هذا؟ ستستغرق وظيفتنا n من الوقت بالضبط : Θ (n).

إذا كانت الحدود محيرة ، فكر في الأمر على هذا النحو. لدينا رقمان ، x و y. نعلم أن x <= y وأن y <= x. إذا كان x أصغر من أو يساوي y ، و y أصغر من أو يساوي x ، فإن x يجب أن يساوي y!

إذا كنت معتادًا على القوائم المرتبطة ، اختبر نفسك وفكر في أوقات التشغيل لكل من هذه الوظائف!

  1. احصل على
  2. إزالة
  3. أضف

تصبح الأمور أكثر إثارة للاهتمام عندما تفكر في قائمة مرتبطة بشكل مزدوج!

تدوين مقارب

كيف نقيس قيمة أداء الخوارزميات؟

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

نقوم بذلك عن طريق تحديد الحدود الرياضية للخوارزمية. هذه هي Big-O و Big-omega و big-theta أو الرموز المقاربة للخوارزمية. على الرسم البياني ، سيكون Big-O هو الأطول التي يمكن أن تستغرقها الخوارزمية لأي مجموعة بيانات معينة ، أو "الحد الأعلى". الأوميغا الكبيرة تشبه Big-O ، "الحد الأدنى". هذا هو المكان الذي تصل فيه الخوارزمية إلى أعلى سرعتها لأي مجموعة بيانات. ثيتا الكبيرة هي إما قيمة الأداء الدقيقة للخوارزمية ، أو نطاق مفيد بين الحدود العليا والسفلى الضيقة.

بعض الأمثلة:

  • "التسليم سيكون هناك خلال حياتك." (كبير- O ، الحد الأعلى)
  • "يمكنني أن أدفع لك دولارًا واحدًا على الأقل." (كبير أوميغا ، انخفاض)
  • "القمة اليوم ستكون 25 درجة مئوية والصغرى 19 درجة مئوية." (ثيتا الكبيرة ، ضيق)
  • "إنها على بعد كيلومتر واحد من الشاطئ." (ثيتا الكبيرة ، بالضبط)

معلومات اكثر:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-٪D3٪ A8- تدوين يمثل //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/