تعقيد الخوارزميات البسيطة وهياكل البيانات في JS

في المقالة السابقة "خطوة نحو الحوسبة كعلم: خوارزميات بسيطة وهياكل البيانات في JS" ، ناقشنا الخوارزميات البسيطة (عمليات البحث الخطية والثنائية ؛ الفقاعات وأنواع التحديد والإدراج) وهياكل البيانات (كائنات مصفوفة وقيمة رئيسية مقترنة ). هنا ، أواصل مفهوم التعقيد وتطبيقه على هذه الخوارزميات وهياكل البيانات.

تعقيد

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

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

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

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

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

هذا مشابه لما يحدث عند التفكير في الخوارزميات وهياكل البيانات.

عمليات البحث

البحث الخطي

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

بحث ثنائي

بالنسبة للبحث الثنائي ، فإن أفضل حالة هي O (1) ، مما يعني أن عنصر البحث يقع في منتصف الطريق. و أسوأ ومتوسط الحال هي قاعدة سجل 2 ن أو:

اللوغاريتم أو اللوغاريتم هو طريقة للتعبير عن الأس لأساس معين. لذا ، إذا كان هناك 16 عنصرًا (ن = 16) ، فسيستغرق الأمر ، في أسوأ الأحوال ، 4 خطوات للعثور على الرقم 15 (الأس = 4).

أو ببساطة: O (تسجيل الدخول)

أنواع

فقاعة

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

لذلك ، بالنسبة لكل عنصر ، فأنت تقارنه ببقية مجموعتك. هذا يصل إلى 16 مقارنة (أو عملية) لأربعة عناصر (4² = 16). في أفضل الأحوال هو إذا تم فرزها مجموعتك تقريبا، باستثناء عنصر واحد. سيكون هذا بمثابة جولة واحدة من المقارنات. وهذا يعني أن هناك حاجة إلى أربع مقارنات لتكوين فقاعات لعضو من مجموعة مكونة من أربعة عناصر ، وهو ما يمثل تعقيدًا لـ O (n) .

اختيار

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

إدراج

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

هياكل البيانات

المصفوفات

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

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

مفتاح - قيمة الكائنات المقترنة

الوصول ، إدخال أو إزالة قيمة باستخدام مفتاح غير لحظية، وهكذا، لديهم تعقيد O (1) . إن البحث في كل "صندوق إيداع" عن عنصر معين باستخدام كل مفتاح متاح هو في الأساس بحث خطي . وهكذا ، فإن لها تعقيد O (n) .

استنتاج

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

مرجع:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/