فصل 2: مبانی الگوریتم‌ها

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

انواع داده و ساختارهای داده

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

از طرف دیگر، ساختارهای داده راه‌هایی را برای سازماندهی و ذخیره داده در حافظه رایانه فراهم می‌کنند. آنها تعریف می‌کنند که داده چگونه مرتب و دسترسی پیدا می‌شوند، که می‌تواند تأثیر زیادی بر کارایی الگوریتم‌هایی که بر روی داده‌ها عمل می‌کنند، داشته باشد. برخی از ساختارهای داده رایج شامل آرایه‌ها، لیست‌های پیوندی، درخت‌ها و جداول هش هستند.

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

کیسه‌ها، صف‌ها و پشته‌ها

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

کیسه‌ها

کیسه یک مجموعه بی‌ترتیب از عناصر است که امکان وجود تکراری‌ها را دارد. عملیات اصلی پشتیبانی شده توسط یک کیسه عبارتند از:

• add(item): افزودن یک آیتم به کیسهاینجا ترجمه فارسی فایل markdown "bag" است. برای کد، فقط نظرات را ترجمه کرده‌ایم.

• isEmpty(): بررسی اینکه آیا کیسه خالی است یا خیر.

• size(): بازگرداندن تعداد آیتم‌های موجود در کیسه.

کیسه‌ها زمانی مفید هستند که نیاز داریم مجموعه‌ای از آیتم‌ها را بدون توجه به ترتیب یا یکتایی آن‌ها نگه داریم.

صف‌ها

صف یک مجموعه از عناصر است که از اصل اول وارد، اول خارج (FIFO) پیروی می‌کند. عملیات اصلی پشتیبانی شده توسط یک صف عبارتند از:

• enqueue(item): افزودن یک آیتم به انتهای صف.
• dequeue(): حذف و بازگرداندن آیتم از ابتدای صف.
• isEmpty(): بررسی اینکه آیا صف خالی است یا خیر.
• size(): بازگرداندن تعداد آیتم‌های موجود در صف.

صف‌ها اغلب در سناریوهایی استفاده می‌شوند که آیتم‌ها باید به ترتیب ورود پردازش شوند، مانند排程任务 یا جستجوی عرضی.

پشته‌ها

پشته یک مجموعه از عناصر است که از اصل آخرین وارد، اولین خارج (LIFO) پیروی می‌کند. عملیات اصلی پشتیبانی شده توسط یک پشته عبارتند از:

• push(item): افزودن یک آیتم به بالای پشته.
• pop(): حذف و بازگرداندن آیتم از بالای پشته.
• isEmpty(): بررسی اینکه آیا پشته خالی است یا خیر.
• size(): بازگرداندن تعداد آیتم‌های موجود در پشته.

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

کیسه‌ها، صف‌ها و پشته‌ها می‌توانند با استفاده از ساختارهای داده مختلف، مانند آرایه‌ها یا لیست‌های پیوندی، بسته به نیازهای خاص برنامه پیاده‌سازی شوند.

تحلیل الگوریتم‌ها

تحلیل کارایی الگوریتم‌ها برای درک ویژگی‌های عملکردی آن‌ها و اتخاذ تصمیم‌های آگاهانه در انتخاب الگوریتم‌ها برای مسائل خاص بسیار مهم است. تحلیل الگوریتم‌ها شامل بررسی پیچیدگی زمانی و فضایی یک الگوریتم است.

پیچیدگی زمانی به مقدار زمانی که یک الگوریتم برای حل یک مسئله نیاز دارد به عنوان تابعی از اندازه ورودی اشاره دارد. این معمولاً با استفاده از نوتاسیون بزرگ-O بیان می‌شود، که یک حد بالا برای نرخ رشد زمان اجرای الگوریتم ارائه می‌دهد. به عنوان مثال، یک الگوریتم با پیچیدگی زمانی O(n) به طور خطی با اندازه ورودی افزایش می‌یابد.اینجا ترجمه فارسی فایل مارک‌داون است:

الگوریتمی با پیچیدگی زمانی O(n) به این معنی است که زمان اجرای آن به طور خطی با اندازه ورودی افزایش می‌یابد.

پیچیدگی فضایی، از طرف دیگر، به مقدار حافظه‌ای که یک الگوریتم برای حل یک مسئله به عنوان تابعی از اندازه ورودی نیاز دارد، اشاره دارد. این نیز با استفاده از نوتاسیون بزرگ-O بیان می‌شود و نشان می‌دهد که چقدر حافظه اضافی یک الگوریتم به اندازه ورودی نیاز دارد.

هنگام تحلیل الگوریتم‌ها، معمولاً به سناریوهای بدترین حالت، متوسط و بهترین حالت توجه می‌کنیم. سناریوی بدترین حالت حداکثر زمان یا فضای مورد نیاز یک الگوریتم برای هر ورودی با اندازه داده شده را نشان می‌دهد، در حالی که سناریوی بهترین حالت حداقل زمان یا فضای مورد نیاز را نشان می‌دهد. سناریوی متوسط نیز زمان یا فضای مورد انتظار برای یک ورودی معمولی را نشان می‌دهد.

مهم است توجه داشته باشیم که زمان اجرای واقعی یک الگوریتم به عوامل مختلفی مانند زبان برنامه‌نویسی، سخت‌افزار و بهینه‌سازی‌های کامپایلر بستگی دارد. با این حال، نوتاسیون بزرگ-O راهی استاندارد برای مقایسه کارایی الگوریتم‌های مختلف بدون در نظر گرفتن این عوامل فراهم می‌کند.

مطالعه موردی: اتحاد-یافتن

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

• union(p, q): ادغام مجموعه‌های حاوی عناصر p و q.
• find(p): یافتن مجموعه‌ای که عنصر p در آن قرار دارد.

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

الگوریتم‌های مختلفی برای پیاده‌سازی ساختار داده اتحاد-یافتن وجود دارد، هر کدام با تجارت‌های متفاوتی بین پیچیدگی زمانی عملیات union و find. برخی از پیاده‌سازی‌های رایج عبارتند از:

• یافتن سریع: عملیات find زمان ثابت دارد، اما عملیات union زمان خطی دارد.
• اتحاد سریعترجمه فارسی:

نکته: عملیات union سریعتر از quick-find است، اما عملیات find در بدترین حالت می‌تواند زمان خطی داشته باشد.

• weighted quick-union: بهبودی بر روی quick-union که درختان را بر اساس اندازه متعادل می‌کند، باعث می‌شود که هر دو عملیات union و find در بدترین حالت لگاریتمی باشند.
• weighted quick-union با فشرده‌سازی مسیر: بهینه‌سازی بیشتر که ساختار درخت را در طی عملیات find مسطح می‌کند، منجر به پیچیدگی زمانی تقریباً ثابت برای هر دو عملیات union و find می‌شود.

مطالعه موردی اتحاد-یافتن (union-find) اهمیت انتخاب ساختارهای داده و الگوریتم‌های مناسب بر اساس نیازهای مسئله و ملاحظات عملکرد را برجسته می‌کند.

نتیجه‌گیری

در این فصل، مفاهیم اساسی انواع داده، ساختارهای داده و انواع داده انتزاعی را با تمرکز بر کیسه‌ها (bags)، صف‌ها (queues) و پشته‌ها (stacks) بررسی کردیم. همچنین تحلیل الگوریتم‌ها و اهمیت در نظر گرفتن پیچیدگی زمانی و فضایی در طراحی و انتخاب الگوریتم‌ها را مورد بحث قرار دادیم. مطالعه موردی اتحاد-یافتن نشان داد که چگونه این مفاهیم می‌توانند برای حل مؤثر مسائل واقعی به کار گرفته شوند.

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