دعونا نبسط تعقيدات الخوارزمية!

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

نعم! المفهوم الذي يتم تجاهله في معظم الأحيان ، لأن الغالبية منا المطورين يفكرون ، "حسنًا ، ربما لن أحتاج إلى معرفة ذلك بينما أقوم بالفعل بالبرمجة!".؟

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

ما هو تحليل الخوارزمية على أي حال ، ولماذا نحتاج إليه؟ ؟

قبل الغوص في تحليل تعقيد الخوارزمية ، دعنا أولاً نحصل على فكرة موجزة عن ماهية تحليل الخوارزمية. يتعامل تحليل الخوارزمية مع مقارنة الخوارزميات بناءً على عدد موارد الحوسبة التي تستخدمها كل خوارزمية.

ما نريد تحقيقه من خلال هذه الممارسة هو القدرة على اتخاذ قرار مستنير بشأن أي الخوارزمية هي الفائز من حيث الاستخدام الفعال للموارد (الوقت أو الذاكرة ، اعتمادًا على حالة الاستخدام). هل لهذا معنى؟

لنأخذ مثالا. لنفترض أن لدينا منتج دالة () يضرب كل عناصر المصفوفة ، باستثناء العنصر في الفهرس الحالي ، ويعيد المصفوفة الجديدة. إذا تجاوزت [1،2،3،4،5] كمدخل ، يجب أن أحصل على [120 ، 60 ، 40 ، 30 ، 24] كنتيجة لذلك.

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

هل أنت قادر على المتابعة؟ عظيم!

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

دعنا نفكر في الطريقة التالية. في هذا الإصدار المعدل ، المبدأ المطبق هو أنه لكل عنصر ، احسب ناتج القيم الموجودة على اليمين ، واحسب حاصل ضرب القيم الموجودة على اليسار ، واضرب هاتين القيمتين ببساطة. جميلة حلوة ، أليس كذلك؟

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

يمكننا أن نستنتج بأمان أن الخوارزمية الأخيرة تعمل بشكل أفضل من الأولى. حتى الان جيدة جدا؟ في احسن الاحوال!

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

اعتمادًا على وقت تحليل الخوارزمية ، أي قبل التنفيذ أو بعد التنفيذ ، يمكن تقسيم تحليل الخوارزمية إلى مرحلتين:

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

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

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

الآن بعد أن أصبح لدينا فهم أساسي لماهية تحليل الخوارزمية ، يمكننا المضي قدمًا إلى موضوعنا الرئيسي: تعقيد الخوارزمية. سنركز على تحليل Apriori ، مع الأخذ في الاعتبار نطاق هذا المنشور ، لذلك دعونا نبدأ.

الغوص العميق في التعقيد مع التحليل المقارب

تحليل تعقيد الخوارزمية هو أداة تسمح لنا بشرح كيف تتصرف الخوارزمية مع نمو المدخلات بشكل أكبر.

لذلك ، إذا كنت تريد تشغيل خوارزمية بمجموعة بيانات بالحجم n ، على سبيل المثال ، يمكننا تعريف التعقيد كدالة عددية f (n) - الوقت مقابل حجم الإدخال n .

الآن يجب أن تتساءل ، أليس من الممكن أن تأخذ الخوارزمية كميات مختلفة من الوقت على نفس المدخلات ، اعتمادًا على عوامل مثل سرعة المعالج ومجموعة التعليمات وسرعة القرص والعلامة التجارية للمترجم؟ إذا كانت الإجابة بنعم ، فربت على ظهرك ، لأنك على حق تمامًا !؟

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

يتم إجراء تحليل التعقيد على عاملين:

  1. الوقت : يشير تعقيد الوقت إلى المدة التي تستغرقها الخوارزمية حتى تكتمل فيما يتعلق بحجم الإدخال. المورد الذي نهتم به في هذه الحالة هو وحدة المعالجة المركزية (ووقت ساعة الحائط).
  2. الفضاء : تعقيد الفضاء مشابه ، ولكنه مؤشر على مقدار الذاكرة "المطلوبة" لتنفيذ الخوارزمية فيما يتعلق بحجم الإدخال. هنا ، نتعامل مع نظام RAM كمورد.

هل ما زلت معي؟ حسن! الآن ، هناك رموز مختلفة نستخدمها لتحليل التعقيد من خلال التحليل المقارب. سنتناولها جميعًا واحدة تلو الأخرى ونفهم الأساسيات وراء كل منها.

ذا بيج أوه (بيج أو)

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

دعنا ندخل في الجانب الرياضي منها لفهم الأشياء في جوهرها.

لنفكر في خوارزمية يمكن وصفها بالدالة f (n). لذلك ، لتحديد BigO لـ f (n) ، نحتاج إلى إيجاد دالة ، دعنا نقول ، g (n) ، التي تحدها. بمعنى ، بعد قيمة معينة ، n0 ، ستتجاوز قيمة g (n) دائمًا f (n) .

يمكننا كتابتها كـ

و (ن) ≤ ج ج (ن)

حيث n≥n0 ؛ ج> 0 ؛ n0≥1

إذا تم استيفاء الشروط المذكورة أعلاه ، فيمكننا القول أن g (n) هي BigO لـ f (n) ، أو

و (ن) = O (ز (ن))

هل يمكننا تطبيق نفس الشيء لتحليل خوارزمية؟ هذا يعني بشكل أساسي أنه في أسوأ سيناريو تشغيل خوارزمية ، يجب ألا تتجاوز القيمة نقطة معينة ، وهي g (n) في هذه الحالة. ومن ثم ، g (n) هو BigO لـ f (n).

لنستعرض بعض رموز bigO الشائعة الاستخدام وتعقيدها ونفهمها بشكل أفضل قليلاً.

  • O (1): يصف خوارزمية سيتم تنفيذها دائمًا في نفس الوقت (أو المساحة) بغض النظر عن حجم مجموعة بيانات الإدخال.
function firstItem(arr){ return arr[0];}

ستستغرق الوظيفة المذكورة أعلاه firstItem () دائمًا نفس الوقت للتنفيذ ، حيث تقوم بإرجاع العنصر الأول من المصفوفة ، بغض النظر عن حجمها. وقت تشغيل هذه الوظيفة مستقل عن حجم الإدخال ، وبالتالي فإن لها تعقيدًا ثابتًا لـ O (1).

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

  • O (N) يصف خوارزمية سينمو أداؤها خطيًا وبشكل مباشر مع حجم مجموعة بيانات الإدخال. ألق نظرة على المثال أدناه. لدينا وظيفة تسمى matchValue ( ) والتي ترجع true كلما تم العثور على حالة مطابقة في المصفوفة. هنا ، نظرًا لأنه يتعين علينا تكرار المصفوفة بأكملها ، فإن وقت التشغيل يتناسب طرديًا مع حجم المصفوفة.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

يوضح هذا أيضًا كيف تفضل Big O سيناريو الأداء الأسوأ. يمكن العثور على حالة مطابقة أثناء أي تكرار forللحلقة وستعود الوظيفة مبكرًا. لكن تدوين Big O سيفترض دائمًا الحد الأعلى (أسوأ حالة) حيث ستؤدي الخوارزمية أقصى عدد من التكرارات.

  • O (N²): يمثل هذا خوارزمية يتناسب أداؤها بشكل مباشر مع مربع حجم مجموعة بيانات الإدخال. هذا شائع مع الخوارزميات التي تتضمن تكرارات متداخلة على مجموعة البيانات. ستؤدي التكرارات المتداخلة الأعمق إلى O (N³) ، O (N⁴) ، إلخ.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O (2 ^ N): يشير إلى خوارزمية يتضاعف نموها مع كل إضافة إلى مجموعة بيانات الإدخال. منحنى نمو دالة O (2 ^ N) أسي - يبدأ ضحلًا جدًا ، ثم يرتفع نيزكيًا. مثال على دالة O (2 ^ N) هو الحساب المتكرر لأرقام فيبوناتشي:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

هل فهمت هذا؟ في احسن الاحوال. إذا لم يكن كذلك ، فلا تتردد في إطلاق استفساراتك في التعليقات أدناه. :)

بالمضي قدمًا ، بعد أن أصبح لدينا فهم أفضل لترميز BigO ، فلننتقل إلى النوع التالي من التحليل المقارب وهو Big Omega (Ω).

أوميغا كبيرة (Ω) ؟

T انه كبير أوميغا (Ω) يوفر لنا أفضل سيناريو لتشغيل الخوارزمية. بمعنى أنه سيعطينا الحد الأدنى من الموارد (الوقت أو المكان) التي قد تستغرقها الخوارزمية للتشغيل.

دعونا نتعمق في الرياضيات لتحليلها بيانيا.

لدينا خوارزمية يمكن وصفها بالدالة f (n). لذلك ، لتحديد BigΩ لـ f (n) ، نحتاج إلى إيجاد دالة ، دعنا نقول ، g (n) ، والتي هي الأقرب إلى الحد الأدنى لـ f (n) . بمعنى ، بعد قيمة معينة ، n0 ، ستتجاوز قيمة f (n) دائمًا g (n) .

يمكننا كتابتها كـ

و (ن) ≥ ج ج (ن)

حيث n≥n0 ؛ ج> 0 ؛ n0≥1

إذا تم استيفاء الشروط المذكورة أعلاه ، فيمكننا القول أن g (n) هي BigΩ لـ f (n) ، أو

و (ن) = Ω (ز (ن))

هل يمكننا أن نستنتج أن Ω (...) مكمل لـ O (...)؟ الانتقال إلى القسم الأخير من هذه المشاركة ...

The Big Theta (θ) ؟

T he Big Theta (θ) هو نوع من مزيج من كل من BigO و BigΩ. يعطينا سيناريو الحالة المتوسطة لتشغيل الخوارزمية. بمعنى أنه سيوفر لنا أفضل وأسوأ حالة. دعنا نحللها رياضيا.

النظر في خوارزمية يمكن وصفها بالدالة f (n). سيكون Bigθ لـ f (n) دالة ، دعنا نقول ، g (n) ، التي تربطها بأقصر حد من الحد الأدنى والأعلى ، مثل:

C₁g (n) ≤ f (n) ≤ C₂ g (n)

أينC₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • سلسلة جيدة حول الخوارزمية وهياكل البيانات: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html