چرا جست‌وجوی دودویی لگاریتمی است: نصف‌کردن مسئله و سقف تعداد گام‌ها.
شرایط اعتبار
هر گام مسئله را نصف می‌کند: وسط را ببین، نصفِ نامربوط را دور بینداز، تکرار.
برای یک میلیون عضو مرتب فقط ۲۰ گام کافی است ()؛ جست‌وجوی خطی در بدترین حالت یک میلیون گام می‌خواست. قیمت این سرعت: داده باید مرتب باشد و مرتب‌نگه‌داشتنش خودش هزینه دارد.
رابطهٔ بازگشتیِ هزینه هم همین نصف‌شدن را نشان می‌دهد:
از همین بخش و با برچسب‌های مشترک
این مطلب را خواندید؟ آن را علامت بزنید تا پیشرفت شما روی همین دستگاه ذخیره شود.
t.me/danialrashidi_projects
پروژهها، وبسایتهای آموزشی تازه و خبرهای دوره را در کانال تلگرام اعلام میکنم. اگر دوست دارید گمشان نکنید، عضو شوید.
هر ۳۰ روز حداکثر یکبار نشان داده میشود.