دنیای زبانهای کدنویسی و توسعه نرمافزار
ضرب دو ماتریس یک عملیات بنیادین در علوم کامپیوتر است، و رویکرد ساده بسیار دور از بهینه است. این راهنمای جامع الگوریتم استاندارد ضرب ماتریس با زمان مکعبی را توضیح میدهد، نشان میدهد چگونه یک رویکرد تقسیموغلبه ساده در بهبود آن شکست میخورد، و الگوریتم قابلتوجه اشتراسن که به یک زمان اجرای مجانبی واقعاً سریعتر میرسد را مرور میکند.
زمان اجرای هر الگوریتم تقسیموغلبه توسط یک رابطه بازگشتی توصیف میشود، و حل آن رابطه برای درک کارایی الگوریتم ضروری است. این راهنمای جامع سه تکنیک استاندارد برای حل رابطههای بازگشتی را پوشش میدهد: روش substitution برای اثبات یک کران حدسزدهشده، روش recursion-tree برای تولید یک حدس، و روش استاد بهعنوان یک میانبر سریع برای یک دسته رایج از رابطههای بازگشتی.
برخی الگوریتمها در حین اجرا انتخابهای تصادفی میکنند، و تحلیل رفتار مورد انتظارشان نیازمند جعبهابزاری متفاوت از تحلیل بدترینحالت بهتنهایی است. این راهنمای جامع تحلیل احتمالاتی را از طریق مسئله کلاسیک استخدام معرفی میکند، متغیرهای تصادفی نشانگر را بهعنوان یک ابزار تحلیلی قدرتمند توضیح میدهد، و نشان میدهد تصادفیسازی چگونه میتواند کارایی مورد انتظار یک الگوریتم را بهبود بخشد.
هیپ دودویی یکی از ظریفترین ساختارهای داده در علوم کامپیوتر است، که هم یک الگوریتم مرتبسازی کارآمد درجا و هم انتزاع صف اولویت مورد استفاده در سراسر طراحی الگوریتم را ممکن میسازد. این راهنمای جامع ویژگیهای هیپ و نمایش آرایهای، عملیات اصلی heapify، ساخت یک هیپ از یک آرایه مرتبنشده، الگوریتم کامل heapsort، و عملیاتهای صف اولویت ساختهشده روی هیپها را پوشش میدهد.
Quicksort یکی از پراستفادهترین الگوریتمهای مرتبسازی در عمل است، که بهخاطر کارایی عالی حالتمیانگین و عملیات درجا ارزشمند است، با وجود داشتن بدترینحالت نظری ضعیف. این راهنمای جامع الگوریتم مبتنی بر partition را با جزئیات پوشش میدهد، هم زمان اجرای بدترینحالت و هم مورد انتظار آن را تحلیل میکند، و توضیح میدهد تصادفیسازی چگونه آن را به یک الگوریتم بهطور قابلاعتماد کارآمد صرفنظر از ترتیب ورودی تبدیل میکند.
هر الگوریتم مرتبسازی مبتنی بر مقایسه در بدترینحالت حداقل به زمان Ω(n log n) نیاز دارد، اما الگوریتمهایی که کاملاً از مقایسه اجتناب میکنند میتوانند تحت شرایط درست در زمان خطی مرتب کنند. این راهنمای جامع کران پایین مرتبسازی مبتنیبرمقایسه را با استدلال درخت تصمیم اثبات میکند، سپس سه الگوریتم زمان-خطی — counting sort، radix sort، و bucket sort — را همراه با فرضیات ورودی خاصی که هرکدام نیاز دارند توضیح میدهد.
یافتن k-امین کوچکترین عنصر در یک آرایه مرتبنشده نیازمند هزینه کامل Θ(n log n) مرتبسازی نیست؛ میتواند در زمان خطی انجام شود. این راهنمای جامع مورد بدیهی یافتن حداقل یا حداکثر، یک الگوریتم انتخاب تصادفی ظریف با زمان مورد انتظار خطی، و یک الگوریتم قطعی پیچیدهتر که زمان خطی را حتی در بدترینحالت تضمین میکند را پوشش میدهد.
پیش از پرداختن به ساختارهای داده پیشرفته، تسلط بر بلوکهای سازنده ابتدایی ضروری است، چون تقریباً هر ساختار پیچیدهای از این پایهها ساخته میشود. این راهنمای جامع پشتهها و صفهای مبتنی بر آرایه، لیستهای پیوندی تکی و دوگانه، و تکنیکهای استاندارد نمایش درختهای ریشهدار را پوشش میدهد، شامل نمایش ظریف فرزند-چپ راهبر-راست برای درختهایی با شاخهبندی نامحدود.
جداول هش جستجو، درج، و حذف زمان-ثابت مورد انتظار فراهم میکنند، که آنها را به یکی از پراستفادهترین ساختارهای داده در عمل تبدیل میکند. این راهنمای جامع ایده آدرسدهی مستقیم که هشینگ را انگیزه میدهد، نحوه مدیریت برخوردها از طریق زنجیرهبندی، ویژگیهای توابع هش خوب، آدرسدهی باز بهعنوان یک جایگزین کارآمد از نظر حافظه، و ملاحظات عملی برای پیادهسازیهای جدول هش دنیای واقعی را پوشش میدهد.
یک درخت جستجوی دودویی عناصر را به ترتیب مرتبشده نگه میدارد در حالی که جستجو، درج، و حذف کارآمد را پشتیبانی میکند، همگی در زمانی متناسب با ارتفاع درخت. این راهنمای جامع ویژگی تعریفکننده درخت-جستجوی-دودویی، عملیاتهای اصلی پرسوجو شامل جستجو، حداقل، حداکثر، و جانشین، و رویههای جزئیتر درج و حذف که باید ساختار درخت را با دقت حفظ کنند را پوشش میدهد.
درخت جستجوی دودویی ساده که پیشتر در این مجموعه پوشش داده شد، میتواند تحت ترتیبهای درج بدشانس به ارتفاع خطی تنزل یابد. درختهای قرمز-سیاه این را با حفظ پنج ناوردای ساده که از نظر ریاضی ارتفاع لگاریتمی را صرفنظر از ترتیب درج تضمین میکنند حل میکنند. این راهنمای جامع ویژگیهای قرمز-سیاه، عملیات چرخش که ساختار درخت-جستجو را حین بازساختاردهی درخت حفظ میکند، و اینکه درج و حذف چگونه با منطق تعادلمجدد گسترش مییابند تا این تضمینها را حفظ کنند را پوشش میدهد.
برنامهنویسی پویا مسائل پیچیده را با شکستن آنها به زیرمسئلههای همپوشان و ذخیره راهحلها برای اجتناب از محاسبه زائد حل میکند. این راهنمای جامع تکنیک را از طریق مسئله کلاسیک برش میله معرفی میکند، آن را به مسئله جزئیتر ضرب زنجیرهای ماتریس گسترش میدهد، و دو ویژگی ضروری — زیرساختار بهینه و زیرمسئلههای همپوشان — که تعیین میکنند چه زمانی برنامهنویسی پویا اعمال میشود را استخراج میکند.
