ماذا يعني "logarithmic" في الخوارزميات وهياكل البيانات؟ شرح مبسط
حين نقول إن خوارزمية ما تعمل بزمن لوغاريتمي (logarithmic time)، فالمقصود ببساطة أن عدد الخطوات اللازمة لإنجاز العمل ينمو ببطء شديد مقارنةً بحجم البيانات: كلما تضاعف حجم المدخلات، زاد عدد الخطوات بمقدار خطوة واحدة فقط. نكتب هذا رياضيًا بالصيغة O(log n)، حيث n هو حجم البيانات. هذه الكفاءة العالية هي سبب اعتماد أنظمة ضخمة كقواعد البيانات ومحركات البحث على هذا النوع من الخوارزميات.
من أين تأتي كلمة "لوغاريتمي"؟
اللوغاريتم هو ببساطة السؤال العكسي للأس: "إلى أي قوة أرفع الأساس لأحصل على هذا العدد؟". فاللوغاريتم للعدد 8 بالأساس 2 يساوي 3، لأن 2³ = 8.
في علوم الحاسوب نستخدم الأساس 2 غالبًا، لأن كثيرًا من الخوارزميات تقسم المشكلة إلى نصفين في كل خطوة. والفكرة الجوهرية هي: كم مرة يمكنني قسمة العدد n على 2 حتى أصل إلى 1؟ الجواب هو log₂(n) تقريبًا.
انظر إلى هذه الأرقام لتدرك مدى القوة:
- مليون عنصر (2²⁰) ← نحو 20 خطوة فقط.
- مليار عنصر (2³⁰) ← نحو 30 خطوة فقط.
بمعنى أنك لو ضاعفت البيانات من مليون إلى ملياري عنصر، فلن تحتاج إلا لخطوة أو خطوتين إضافيتين. هذا هو جمال الزمن اللوغاريتمي.
المثال الأشهر: البحث الثنائي (Binary Search)
تخيّل أنك تبحث عن كلمة في معجم ورقي. لا تبدأ من الصفحة الأولى وتقلّب صفحة صفحة (هذا بحث خطي O(n)). بل تفتح المعجم من المنتصف، وتقرر: هل كلمتي قبل هذه الصفحة أم بعدها؟ ثم تتجاهل النصف الآخر تمامًا وتكرر.
خطوات البحث الثنائي على قائمة مرتبة:
- حدّد العنصر في منتصف القائمة.
- إن كان هو المطلوب، انتهى البحث.
- إن كان المطلوب أصغر، أكمل في النصف الأيسر فقط.
- إن كان أكبر، أكمل في النصف الأيمن فقط.
- كرّر حتى تجده أو تفرغ القائمة.
لأنك تُلغي نصف الاحتمالات في كل خطوة، فإن عدد الخطوات لوغاريتمي. الشرط الجوهري هنا هو أن تكون القائمة مرتبة مسبقًا؛ فالبحث الثنائي لا يعمل على بيانات عشوائية غير مرتبة، وهذا خطأ شائع يقع فيه المبتدئون.
أين نصادف الزمن اللوغاريتمي عمليًا؟
- الأشجار الثنائية المتوازنة مثل شجرة AVL و Red-Black Tree: البحث والإدراج والحذف كلها
O(log n)طالما بقيت الشجرة متوازنة. - الأكوام (Heaps) المستخدمة في طوابير الأولوية: إضافة عنصر أو إخراج الأصغر يتم بزمن لوغاريتمي.
- فهارس قواعد البيانات (Indexes): تعتمد بنية B-Tree ليصل الاستعلام إلى السجل المطلوب دون مسح الجدول كله.
ملاحظة مهمة: شجرة البحث الثنائية تعطي O(log n) في المتوسط، لكنها قد تتدهور إلى O(n) إذا أُدخلت البيانات بترتيب سيّئ يجعلها تشبه القائمة. لهذا اختُرعت الأشجار المتوازنة التي تضمن البقاء لوغاريتمية دائمًا.
مقارنة: كيف يقف اللوغاريتمي بين أنواع التعقيد؟
الجدول التالي يوضح عدد الخطوات التقريبي لكل نوع مع مدخلات بحجم مليون عنصر، من الأسرع إلى الأبطأ:
| نوع التعقيد | الصيغة | الخطوات لمليون عنصر | مثال |
|---|---|---|---|
| ثابت | O(1) | خطوة واحدة | الوصول لعنصر بمصفوفة عبر رقمه |
| لوغاريتمي | O(log n) | نحو 20 | البحث الثنائي |
| خطي | O(n) | مليون | البحث في قائمة غير مرتبة |
| شبه خطي | O(n log n) | نحو 20 مليون | خوارزميات الفرز الجيدة |
| تربيعي | O(n²) | تريليون | الفرز الفقاعي |
يتضح أن اللوغاريتمي أبطأ قليلًا من الثابت، لكنه أسرع بمراحل هائلة من الخطي، ويصبح الفرق فلكيًا كلما كبرت البيانات.
نصيحة عملية لا تغفلها
الزمن اللوغاريتمي ليس سحرًا مجانيًا؛ له ثمن مسبق. البحث الثنائي يتطلب قائمة مرتبة، والفرز نفسه يكلّف O(n log n). لذا إن كنت ستبحث مرة واحدة فقط في بيانات صغيرة، قد يكون البحث الخطي البسيط أنسب. أما إن كنت ستبحث آلاف المرات في البيانات نفسها، فترتيبها مرة واحدة ثم استخدام البحث الثنائي يوفّر وقتًا ضخمًا. القاعدة: احسب تكلفة التحضير مقابل عدد مرات الاستخدام قبل أن تختار.
الأسئلة الشائعة
هل يهم أساس اللوغاريتم (2 أم 10) في تحليل الخوارزميات؟
لا يهم عمليًا. تغيير الأساس يضرب النتيجة في ثابت فقط، وفي تدوين Big O نتجاهل الثوابت، لذا نكتب O(log n) دون تحديد الأساس.
ما الفرق بين O(log n) و O(n log n)؟ الأولى تقطع البيانات إلى النصف مرة واحدة (كالبحث). الثانية تكرر عملية لوغاريتمية عبر كل عنصر، وهي تعقيد خوارزميات الفرز الفعّالة مثل Merge Sort و Heap Sort.
هل البحث الثنائي دائمًا أسرع من الخطي؟ ليس دائمًا. على قوائم صغيرة جدًا قد يتفوق البحث الخطي بسبب بساطته وقلة الحسابات، كما أن البحث الثنائي يشترط ترتيب البيانات أولًا.
هل يمكن أن يكون شيء أسرع من اللوغاريتمي؟
نعم، الزمن الثابت O(1) أسرع، إذ ينجز العمل في خطوة واحدة بغض النظر عن حجم البيانات، كما في جداول التجزئة (Hash Tables) للوصول المباشر.