📘 ترجمه کتاب grokking algorithms - An illustrated guide for programmers and other curious people

📘درک الگوریتم - راهنمای تصویری برای برنامه‌نویس‌ها و افراد کنجکاو

✏️ نویسنده: آدیتیا بهارگاوا

✒️ مترجم: مهران افشار نادری

📝 310 page

#book
#algorithm
#byteforge
@byteforge_chan 🛸



الگوریتم ها 🎳
‏binary search

باینری سرچ یا جستجوی دودویی، یه روش هوشمندانه و بسیار سریع برای پیدا کردن یه مقدار خاص در میان داده‌های مرتب‌شده هستش, داخل این الگوریتم، به‌جای بررسی دونه به دونه عناصر، داده‌ها رو مثل یک کتاب نصف می‌کنیم و فقط نیمه‌ای را نگاه می‌کنیم که احتمال وجود پاسخ در اون بیشتره . با هر بار نصف کردن، محدوده جستجو کوچک‌تر میشه تا جایی که یا جواب رو پیدا می‌کنیم یا مطمئن میشیم که وجود نداره , این تکنیک باعث میشه که در بدترین حالت، تعداد بررسی‌ها بسیار کم باشه چیزی در حدود لگاریتمی نسبت به اندازه کل داده‌ها .

فرض کنید تو دفترچه تلفنتون دنبال یه اسمی میگردین (خیلی خسته کننده س نه؟)
اون اسم مورد نظر شما فرض کنید با حرف x شروع میشه یه راهش اینه از اول لیست شروع کنید تموم اسم ها رو بررسی کنید تا به اسم مورد نظرتون میرسید یا اینکه بر این اساس که لیست ها با ترتیب الفبا ورودی هارو مرتب میکنند و شما با این اساس که میدونید حرف x در اخر لیست ها قرار میگره دیگه کل لیست رو بررسی نمیکنید و فقط اخر لیست رو نگاه میکنید و این روش خیلی سریعتره .

یه لیست داریم که از (1تا100) حالا شما یه عدد در این رنج در نظر بگیرید و میخوایم حدسش بزنیم .
خب شروع میکنیم به حدس زدن عدد 1 رو در نظر میگیریم .
ایا حدسم درست بود ؟ نه
خب 2 چی؟ نه 2 هم نیست
عدد 3 هم نیست؟ نخیر نیست
ای بابا کی میتونه عدس بزنه 😒

*****....100

نظر منو بخواید میگم این یه راهکار اشتباه و احمقانه س شما با هر بارحدس زدن یه عدد رو از لیست حذف میکنید فرض کنید عددی که شما در نظر گرفته بودین 99 بود خب من جونم در میاد باید 99 بار حدس بزنم تا به عدد مورد نظر برسم .

یه روش بهتر دارم عدد مورد نظر رو 57 بذارید .
انتخاب اول رو میذارم 50 خب با حدس اولم شما میگید که 50 نیس اون عدد مورد نظر بیشتره
خب من الان فکر میکنم به گفته شما و عدد پیشنهادیم رو میذارم رو
یه عدد بزرگتر .
بعدی رو من میگم 74 شما میگید نه کمتر
من اینبار میگم 62 بازم شما میگید کمتر
من اینبار میگم 57 و شما میگید که درسته عدد مورد نظرم 57 بود .

خب همین الان این الگوریتم رو یاد گرفتیم به این روش میگن جست و جوی باینری یا
‏ bainary search
شما در این روش در مثال بالا بجای 100 مرحله برای حدس عدد مورد نظر خیلی سریعتر تونستید با روش باینری حدس رو کامل کنید .

به طور معمول برای هر فهرستی از n , جست و جوی باینری ‏
‏ log 2^n
مرحله برای بدترین وضعیت نیازه که جست و جو تکمیل بشه درحالی که برای جست و جوی ساده n مرحله نیازه که جست و جو رو کامل کنیم .

لگاریتم :
لگاریتم یعنی چند بار باید یه عدد (پایه) رو در خودش ضرب کنیم تا به یه عدد خاص برسیم.
مثلاً log₂(8) = 3 یعنی 2 × 2 × 2 = 8.
در واقع لگاریتم، برعکس توانه .

10^2 = 100     ⇔     log₁₀(100) = 2  
10^3 = 1000    ⇔     log₁₀(1000) = 3  
2^3 = 8        ⇔     log₂(8) = 3  
2^4 = 16       ⇔     log₂(16) = 4  
3^5 = 243      ⇔     log₃(243) = 5

اینهمه گفتیم خوب به چه دردی میخوره ؟😁

جستجو در آرایه‌ها و لیست‌های مرتب‌شده
پایگاه داده‌ها (Database Indexing)
کتابخانه‌های استاندارد زبان‌های برنامه‌نویسی
حل مسائل الگوریتمی و برنامه‌نویسی رقابتی
در الگوریتم‌های Divide & Conquer
برنامه‌ریزی زمانی و مدیریت منابع
در موتورهای جستجو و سیستم فایل

#Algorithm
#binarysearch
#byteforge
@byteforge_chan 🛸