ریاضیات پشت O(log n): جستجوی دودویی، لگاریتم و دلیل برتری نصف‌کردن

اصل ماجرا

مقاله مفهوم لگاریتم را به‌عنوان تعداد تقسیم‌های متوالی عدد به نصف تعریف می‌کند و نشان می‌دهد که الگوریتم‌های O(log n) مثل جستجوی دودویی، درخت‌های متوازن، هیپ‌ها و تقسیم‑و‑غلبه همگی بر پایهٔ این نیمه‌کردن هستند. همچنین تأکید می‌کند که پایهٔ لگاریتم در تجزیه‑و‑تحلیل بزرگ‑O اهمیتی ندارد و فقط ثابت است.

متن کامل ترجمه‌شده

شما O(log n) صد بار خوانده شده است. جستجوی باینری O(log n) است. یک جستجوی BST متوازن O(log n) است. انبوه انبوه O(log n) است. ما در طول می کشد - log n به معنای “بسیار” - و ادامه می دهیم. اما چه چیزی است که لگواریت واقعا حساب می کند؟ هنگامی که آن را کلیک می کند، یک خانواده کامل از الگوریتم ها متوقف می شود که شما یاد شده است و تبدیل به یک ایده است که شما درک می کنید. یک لگواریت حساب می کند نیمی از مرحله ها را فراموش کنید تعریف کتاب درس برای یک ثانیه. در اینجا یکی است که برای الگوریتم ها مهم است: log2(n) تعداد بار شما می توانید نصف N قبل از رسیدن به 1 است. این است. شروع با n، به اشتراک گذاری 2،هر مقایسه نیمی از آنچه باقی مانده را از بین می برد: def binary_search(arr, target): lo, hi = 0, len(arr) - 1 مرحله = 0 در حالی که lo <= hi: مراحل += 1 نیمه = (lo + hi) // 2 اگر arr[mid] == هدف: بازگشت نیمی، مراحل elif arr[mid] < target: lo = mid + 1 # نیمی پایین دیگر را از بین می برد: hi = mid - 1 # نیمی بالا را از بین می برد -1, مراحل آن را بر روی مجموعه ای از یک میلیون کل و مراحل هرگز بیش از 20 - هر کدام عنصر را که شما جستجو می کنید. یک اسکن خطی به طور متوسط 500،000 مقایسه خواهد کرد. همان داده ها، همان ماشین، 25،000× تفاوت در کار worst-case. تنها چیزی که تغییر کرده است جستجوی باینری در حالی که نیمی از اسکنهنگامی که شما O(log n) را به عنوان “فقط” می بینید، شروع به مشاهده حرکت مشابه در همه جا می کنید: - درختان متوازن (AVL، قرمز سیاه، درختان B): هر سطح کلید های باقی مانده را به دو تقسیم می کند، بنابراین درخت ~log2(n) عمیق است. یک درخت B با یک عامل فزاینده بالا bislog_b(n)deep. - تقسیم و غلبه کنید: یک ایده مشابه، فزاینده چربی است. به همین دلیل است که یک درخت 4 سطح B می تواند میلیون ها رده را ثبت کند. - بافت های باینری: Sift-up و Sift-down یک مسیر ریشه-در-فزاینده. طول راه = ارتفاع درخت = O(log n)deep. - تقسیم و غلبه کنید: مجموعه ترکیبی تقسیم در نیمه هر سطح،“اما داده های من قدرت دو نیست” واردات واقعی قدرتهای خالص 2 نیستند، و پایه همیشه 2 نیست - یک تقسیم تریری log3 است، یک درخت B با عامل فشرده سازی 256 است log256. هنگامی که شما نیاز به ارزش واقعی برای یک ارزیابی پشت فشرده سازی است، شما بر روی فرمول تغییر از پایه: log_b(n) = ln(n) / ln(b) = log10(n) / log10(b) شما می توانید در سه سطوح ضربه بزنید که در هر یک از محاسبات منطقی که یک پایه خودرویی برای دستیابی به ریاضیات یک زبان است پشتیبانی می کند.log(xlog) با عوامل فشرده سازی 256 است log256(10,000) = ln(10,000) / ln(256) ≈ 16.1 / 5.55 ≈ 2.9 سطح. شما می توانیدبه همین دلیل است که ما O(log n) را با هیچ پایه ای نوشته ایم - وجود نصف کردن چیزی است که ما ادعا می کنیم، نه طعم آن. The takeaway زمانی که شما O(log n) را بخوانید، آن را به “بسیار” ترجمه نکنید. ترجمه آن را به “این الگوریتم هر مرحله مشکل را نصف می کند” و بپرسید که در کجا نصف شدن اتفاق می افتد - مقایسه، سطح درخت، تقسیم تکراری، حافظه دوگانه. که یک بازگرداندن تنها جستجو دوگانه، درختان متعادل، جمع آوری، و تقسیم-و-قیمت به تغییرات بر روی یک موضوع به جای چهار چیز برای یادگیری. نصف کردن ارزان ترین قدرت در علوم کامپیوتر است.

چرا مهمه؟

درک این اصل باعث می‌شود تا به‌سرعت ساختارهای داده مقیاس‌پذیر طراحی شوند و هزینهٔ پردازش بزرگ‌ترین داده‌ها را به‌طور چشمگیری کاهش دهند.

به درد کی می‌خوره؟

developers, tech_leads, data_scientists

تو عمل چی کار کنیم؟

توسعه‌دهندگان می‌توانند با تشخیص الگوی نیمه‌کردن، طراحی ساختارهای داده و الگوریتم‌های بهینه‌تری ارائه دهند و هزینهٔ محاسبه را به‌صورت نمایی کاهش دهند.

نظر Blue IT News

درک لگاریتم به عنوان شمارش تقسیم به نصف، تمام الگوریتم‌های O(log n) را به یک ایدهٔ واحد تبدیل می‌کند؛ این نگاه باعث می‌شود تا به‌جای حفظ جزئیات، به‌سرعت نقاط «نیمه‌کردن» در ساختارها پی ببریم.

<div class=“disclosure”> این صفحه ترجمه و تفسیر کاملی از گزارش اصلی Dev است که توسط تیم تحریریه بلو آی تی نیوز به فارسی ترجمه و تحلیل شده. برای مشاهده نسخه اصلی، به منبع مراجعه کنید. </div>