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