books logarithmic time
If you do not find what you're looking for, you can use more accurate words.
وقت لوغاريتمي (Info)
ويقال إن الخوارزمية تأخذ وقت لوغاريتمي إذا كانت T ( n ) = O (log n ) . نظرًا لاستخدام نظام الأرقام الثنائي بواسطة أجهزة الكمبيوتر، فإن اللوغاريتم يكون في الغالب أساسًا 2 (أي log 2 n ، وأحيانًا مكتوبة lg n ). ومع ذلك، من خلال تغيير قاعدة لوغاريتمات، تسجيل و ن وتسجيل ب ن تختلف فقط من قبل مضاعف المستمر، والتي كبير-O يتم تجاهل التدوين. وهكذا يا (سجل ن) هو الترميز القياسي لخوارزميات الوقت اللوغاريتية بغض النظر عن أساس اللوغاريتم.
الخوارزميات التي تأخذ الوقت اللوغاريتمي موجودة بشكل شائع في العمليات على الأشجار الثنائية أو عند استخدام البحث الثنائي .
تعتبر خوارزمية O (log n) عالية الكفاءة، حيث تقل نسبة عدد العمليات إلى حجم المدخلات وتميل إلى الصفر عندما تزيد n . الخوارزمية التي يجب أن تصل إلى كل عناصر مدخلاتها لا يمكن أن تستغرق وقت لوغاريتمي، لأن الوقت المستغرق لقراءة مدخلات بالحجم n يكون بترتيب n .
يتم إعطاء مثال على الوقت اللوغاريتمي عن طريق البحث في القاموس. دعنا نفكر في قاموس يحتوي على مداخل n ، مرتبة حسب الترتيب الأبجدي. نحن نفترض أنه، بالنسبة لـ 1 ≤ k ≤ n
1 ≤ k ≤ n، يمكن للمرء الوصول إلى دخول ال k من القاموس في وقت ثابت. دعونا D[k] دلالة هذا ك دخول عشر. بموجب هذه الفرضيات، يمكن إجراء الاختبار إذا كانت الكلمة D في القاموس في زمن لوغاريتمي: فكر في المكان الذي يشير إلى دالة الكلمة . إذا تم الانتهاء من ذلك. عدا ذلك، إذا استمر البحث بنفس الطريقة في النصف الأيسر من القاموس، وإلا استمر بالمثل مع النصف الأيمن من القاموس. تشبه هذه الخوارزمية الطريقة المستخدمة غالبًا للعثور على إدخال في قاموس ورقي. دالتا الجزء الصحيح و السقف
