9. تحليل الوقت اللوغاريتمي: O(log N)

إن O(log N) فعال للغاية. وهذا يعني أنه مع نمو حجم المدخلات (N)، ينمو عدد العمليات المطلوبة ببطء شديد.

ما هو النمو اللوغاريتمي؟

تعمل الخوارزميات اللوغاريتمية عن طريق تقسيم حجم المشكلة باستمرار إلى النصف (أو جزء منه) في كل خطوة. إذا كان لديك 1024 عنصراً، فأنت تحتاج فقط إلى 10 خطوات لتقليل المشكلة إلى حجم 1 (لأن 2^10 = 1024).

قوة O(log N)

N = 1,000,000
O(N) = 1,000,000 عملية.
O(log N) ≈ 20 عملية.

مثال: البحث الثنائي (Binary Search)

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