اذا كنت راغبا في تعلم البرمجة بشكل عام، فلا مفر من تعلم الخوارزميات. الخوارزميات تعتبر اساس معظم التقنيات الحديثة ان لم تكن اهم اساسها. ويعتبر حجر البناء الاساسي للخوارزميات هي خوارزميات البحث والترتيب – Sorting and Searching – في هذا المقال سنناقش باختصار خوارزمية البحث وانواعها ومميزاتها وعيوبها ومتى يصلح كل نوع للاستخدام.
تحدثنا في مناسبة سابقة عن خوارزميات الترتيب، يمكنك الاطلاع من هنا
تعقيد الوقت – Time Complexity
قبل مناقشة اي نوع من انواع الخوارزميات، يجب ان تكون ملم ببعض مفاهيم الخاصة بالخوارزميات. كنا قد تحدثنا في مناسبة لاحقة عن مفهوم Time Complexity، ولكن باختصار، هو كمية الوقت التي يحتاجها الكود للمعالجة او التشغيل، ويعتبر هو احد اهم المقاييس التي تقاس بها مدى جودة الكود الخاص بك.
يمكننا تطبيق مفهوم تعقيد الوقت بشكل عام على اي نوع من انواع الكود، لأن – بشكل ما – كل كود هو خوارزمية خاصة. ولكن عندما نذكر الخوارزميات على وجه الخصوص، فيجب عليك معرفة تعقيد الوقت لكل خوارزمية ما ستستخدمها. وكيفية قياسها وكيف تعمل.
خوارزمية البحث
ربما قد تتوقف قليلا عند محرك البحث “جوجل”، لتلاحظ السرعة التي تجد بها نتيجة بحثك في موضوع ما ضمن مليارات الموضوعات الموجودة عليه، تخيل ان تبحث باستخدام كلمة من اصل ملايين الكلمات عن مقال من وسط ملايين المقالات، او فيديو ما وسط مئات الملايين في منصة اليوتيوب، لتجد الفيديو الذي كنت تبحث عنه، وتجد نفس النتيجة اذا بحثت مرتين بنفس العنوان، تخيل ان كل هذه العمليات المعقدة يتم معالجتها في اقل من الثواني!
اثناء سنواتي الاولى بكلية الحاسبات والمعلومات، كان ينتباني الفضول لتجربة بعض الامور العجيبة، ضمن تلك الامور هي خلق مصفوفة بلغة ++C حجمها مليون عنصر لكنها خالية من البيانات، والبحث عن العنصر رقم 969, 669. فيستغرق المترجم الخاص باللغة بضع ثوان، ليأتي بعنوان هذا المكان المحجوز بالذاكرة. فكنت اتسائل، مصفوفة بها مليون عنصر – رقم كبير بالطبع. وسيرفر مثل سيرفر جوجل لديه ملايين الملايين من المقالات والفيديوهات والصور، ومع ذلك كنت احصل على نتائج اسرع من البحث خلال مليون عنصر فقط.
في تجربة الطالب حديث العهد بالبرمجة، اثناء بحثه عن عنصر ما ضمن مجموعة من العناصر، اضطر المترجم – compiler – للبحث خلال المليون عنصر كاملين للحصول على هذه النتيجة. او اضطر في البحث خلال 969, 669 عنصر للحصول على النتيجة المرجوة، لكن بقليل من التفكير لتقليل الوقت اللازم، كان يمكن لهذا الطالب ان يخبر المترجم بأن عليه ان يقسم مصفوفته لنصفين، كل نصف مكون من 500,000 عنصر، ويقارن رقم العنصر اما اذا كان اكبر او اصغر من خمسمائة الف. في هذه الحالة سيضطر المترجم للبحث بين خمسمائة الف ومليون، مما سيقلل بكثير الوقت اللازم للبحث الى النصف تقريبا. وفي حالة الحصول على نتائج اسرع، يمكننا تقسيم المليون الى ارباع، مما سيقلل الوقت اللازم الى الضعفين. وكلما زادت الرغبة في الحصول على نتائج اسرع كلما ازدادت تقسيمة المليون عنصر.
هذه هي خوارزمية البحث بشكل بسيط، تحديدا يسمى هذا النوع من الخوازرميات بال Binary Search. لكن يوجد اكثر من نوع لخوارزمية البحث سنتاولهم في الفقرة القادمة.
انواع خوارزميات البحث وتعقيد الوقت لكل منهم
| Linear search | O(1) | O(N) |
| Binary search | O(1) | O(log N) |
