انتخاب ساختار داده و الگوریتم مناسب
راهنمای جامع تصمیم‌گیری: جدول انتخاب ساختار داده بر اساس عملیات و انتخاب الگوریتم بر اساس نوع مسئله
جمع‌بندی هنر انتخاب
مهم‌ترین مهارت DSA، حفظ‌کردن پیاده‌سازی‌ها نیست؛ انتخاب درست است. این مبحث، نقشه تصمیم‌گیری نهایی را ارائه می‌دهد.
جدول انتخاب ساختار داده
| الگوی عملیات غالب | ساختار | پیچیدگی کلیدی |
|---|---|---|
| دسترسی با موقعیت | آرایه | O(1) |
| درج/حذف مکرر ابتدا | لیست پیوندی / deque | O(1) |
| آخرین عمل مهم (Undo) | پشته | O(1) |
| ترتیب ورود (نوبت) | صف | O(1) |
| جستجو/درج/حذف با کلید | جدول هش | O(1) میانگین |
| جستجو + ترتیب حفظ شود | BST متوازن | O(log n) |
| min/max مکرر | هیپ | O(1) peek |
| روابط چندبه‌چند | گراف | O(V+E) |
| سلسله‌مراتب | درخت | O(log n) |
جدول انتخاب الگوریتم جستجو
| وضعیت داده | الگوریتم | پیچیدگی |
|---|---|---|
| نامرتب / کوچک | خطی | O(n) |
| مرتب | دودویی | O(log n) |
| جستجوی مکرر با کلید | جدول هش بساز | O(1) میانگین |
| محدوده کوچک صحیح | آرایه شمارش | O(1) |
جدول انتخاب مرتب‌سازی
| سناریو | الگوریتم |
|---|---|
| عمومی و عملی | Quick Sort / sort آماده |
| تضمین O(n log n) / پایداری | Merge Sort |
| تقریباً مرتب / کوچک | Insertion Sort |
| صحیح با بازه کم | Counting Sort |
| حافظه نوشتن گران | Selection Sort |
جدول انتخاب تکنیک طراحی
| مشخصه مسئله | تکنیک |
|---|---|
| زیرمسئله‌های مستقل | تقسیم و حل |
| زیرمسئله‌های همپوشان | برنامه‌نویسی پویا |
| انتخاب محلی = بهینه سراسری (اثبات‌شده) | حریصانه |
| ساختار خودمتشابه | بازگشت |
| کوتاه‌ترین مسیر بدون وزن | BFS |
| کوتاه‌ترین مسیر وزن‌دار | دایکسترا |
| اتصال کم‌هزینه همه | MST (Prim/Kruskal) |
چک‌لیست تصمیم‌گیری
- حجم داده چقدر است؟ (n کوچک = هرچیزی کار می‌کند!)
- کدام عملیات بیشتر انجام می‌شود؟
- داده مرتب است یا قابل مرتب‌کردن؟
- حافظه اضافی مجاز است؟
- پایداری مهم است؟
- بدترین حالت چقدر حیاتی است؟
نکته طلایی مصاحبه: اول راه‌حل ساده و درست بگو، Big O آن را تحلیل کن، بعد بهینه کن. مسیر تفکرت مهم‌تر از جواب نهایی است!
جمع‌بندی
- انتخاب = تابع الگوی عملیات + حجم داده + محدودیت‌ها
- جدول‌های این مبحث را مرجع نگه دارید
- با تمرین، این تصمیم‌ها شهودی می‌شوند
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.