انواع الگوریتم در علوم کامپیوتر به عنوان مجموعه‌ای از گام‌ها یا مراحل مشخص برای حل یک مسئله تعریف می‌شود. از جمله الگوریتم‌های مهم در علوم کامپیوتر می‌توان به الگوریتم‌های جستجو، مرتب‌سازی، پیمایش گراف، و الگوریتم‌های بازگشتی اشاره کرد. در این مقاله، برخی از الگوریتم‌های معروف مورد بررسی قرار گرفته‌اند که هرکدام ویژگی‌ها و کاربردهای خاص خود را دارند. با ما همراه باشید.
Linear Search یا جستجوی خطی
هر عنصر آرایه را جستجو می‌کند تا عنصر مورد نیاز را پیدا کند.
پیچیدگی زمانی: O(n)
Binary Search یا جستجوی دودویی
عنصر را با مقایسه با آیتم میانی آرایه مرتب شده جستجو می‌کند. اگر تطابق رخ دهد، فهرست برگردانده می شود، در غیر این صورت منطقه جستجو به طور مناسب به نیمه بالایی یا نیمه پایینی آرایه کاهش پیدا می‌کند.
پیچیدگی زمانی: O(Log n)
Bubble Sort یا مرتب‌سازی حبابی
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی ساده است که معمولا برای مرتب کردن عناصر در یک لیست یا آرایه استفاده می‌شود. این کار با مقایسه مکرر عناصر مجاور و تعویض آن‌ها در صورت عدم ترتیب کار می‌کند. این الگوریتم چندین بار در لیست تکرار می‌شود تا زمانی که دیگر نیازی به مبادله نباشد و در نتیجه یک دنباله مرتب شده است.
بیشتر بخوانید: ایده‌های پروژه جنگو برای مبتدیان
پیچیدگی زمانی: O(n2)
Insertion Sort یا مرتب‌سازی درجی
آرایه به بخش‌های مرتب شده و مرتب نشده تقسیم می‌شود. عناصر مرتب نشده انتخاب می‌شوند و در موقعیت صحیح خود در قسمت مرتب شده قرار می‌گیرند.
پیچیدگی زمانی: O(n2)
Selection Sort یا مرتب‌سازی انتخابی
کوچکترین مقدار در بین عناصر مرتب نشده آرایه در هر گذر انتخاب و در موقعیت مناسب خود در آرایه درج می‌شود.
پیچیدگی زمانی: O(n2)
Heap Sort یا مرتب‌سازی هرمی
الگوریتم مرتب‌سازی هرمی (Heap Sort)، یک تکنیک مرتب‌سازی بر اساس مقایسه مبتنی بر ساختار داده دودویی هیپ است. Heap Sort شبیه به الگوریتم مرتب‌سازی انتخابی است. در این الگوریتم ابتدا بزرگترین عنصر پیدا شده و در انتهای آرایه قرار می‌گیرد. همین روند برای باقی عناصر تکرار می‌شود تا آرایه به طور کامل مرتب شود.
پیچیدگی زمانی: O(nlog n)
Merge Sort یا مرتب‌سازی ادغامی
روش مرتب‌سازی ادغامی (Merge Sort)، یک روش مرتب‌سازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل شده است:
- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کنید
- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کنید
- دو زیرآرایه مرتب‌شده را ادغام کنید.
پیچیدگی زمانی: O(nlogn)
Quick Sort یا مرتب‌سازی سریع
یکی از الگوریتم‌های مرتب‌سازی است که به دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده‌سازی ساده بسیار مورد قبول واقع شده است.
این الگوریتم مانند الگوریتم Merge Sort، به روش تقسیم و غلبه (Divide and Conquer) عمل می کند. در این الگوریتم یک عنصر به عنوان محور انتخاب می‌شود و آرایه با توجه به آن عنصر تقسیم می‌شود. روش انتخاب عنصر محوری در نسخه‌های مختلف الگوریتم مرتب‌سازی سریع، متفاوت است.
- همیشه عنصر اول به عنوان عنصر محوری انتخاب می‌شود
- همیشه عنصر آخر به عنوان عنصر محوری انتخاب می‌شود (در زیر پیاده‌سازی شده است)
- یک عنصر تصادفی به عنوان عنصر محوری انتخاب می‌شود
- عنصر میانی به عنوان عنصر محوری انتخاب می‌شود
عملیات اصلی در الگوریتم مرتب‌سازی سریع، پارتیشن‌بندی است. هدف از پارتیشن بندی این است که در آرایه داده شده، یک عنصر به عنوان عنصر محوری انتخاب و در موقعیت مناسب قرار داده شود. سپس عناصری که از این عنصر کوچکتراند، به قبل از آن و عناصری که بزرگتراند، به بعد از آن انتقال پیدا کنند.
پیچیدگی زمانی : O(n*logn)
Breadth First Search (BFS) and Depth First Search (DFS)
Breath First Search با استفاده از صف اجرا می‌شود و از یک راس داده شده شروع می‌شود و همه رئوس مجاور آن ابتدا قبل از رفتن به راس بعدی بازدید می‌شوند.
Depth First Search با استفاده از یک پشته اجرا می‌شود و از یک راس معین شروع می‌شود و جستجوی خود را از طریق رئوس مجاور ادامه می‌دهد تا زمانی که هیچ راس دیگری باقی نماند.
پیچیدگی زمانی هر دو الگوریتم: O(V+E)
بیشتر بخوانید: بهترین زبان‌های برنامه نویسی برای یادگیری
Dijkstra’s Algorithm یا الگوریتم دایجسترا
برای پیدا کردن کوتاه‌ترین مسیر بین دو راس در یک گراف استفاده می‌شود. این یک الگوریتم حریصانه (Greedy algorithm) است.
پیچیدگی زمانی: O(N2)
Inorder Traversal
پیمایش از زیر درخت سمت چپ به سمت گره ریشه شروع می شود و سپس زیر درخت سمت راست پیمایش می‌کند.
پیچیدگی زمانی: O(n)
Preorder Traversal
از گره ریشه شروع می‌کند و زیر درخت سمت چپ و سپس زیر درخت سمت راست را پیمایش می کند.
پیچیدگی زمانی: O(n)
Postorder Traversal
زیر درخت سمت چپ و سپس زیر درخت سمت راست را پیمایش می کند و سپس گره ریشه را پیمایش می کند.
پیچیدگی زمانی: O(n)
Kruskal’s Algorithm یا الگوریتم کروسکال
برای یافتن حداقل درخت پوشا (spanning tree)، با مرتب‌سازی لبه‌ها به ترتیب نزولی و افزودن کوچکترین لبه‌ای که هنوز اضافه نشده است برای تشکیل درختی با تمام گره‌ها استفاده می‌شود.
Floyd-Warshall Algorithm یا الگوریتم فلوید وارشال
Floyd-Warshall الگوریتمی برای پیدا کردن کوتاه‌ترین مسیر بین تمام جفت رئوس در یک نمودار وزنی است. این الگوریتم مبتنی بر برنامه‌‌نویسی پویا است.
Backtracking Algorithm یا الگوریتم عقبگرد
Backtracking یک تکنیک الگوریتمی برای حل مشکلات به صورت بازگشتی با تلاش برای ساختن یک راه حل تدریجی، یک تکه در یک زمان، حذف آن دسته از راه حل‌هایی است که نمی‌توانند محدودیت‌های مسئله را در هر نقطه‌ای از زمان برآورده کنند (براساس زمان، در اینجا، به زمان سپری شده تا رسیدن به هر سطحی از درخت جستجو)
انواع الگوریتم عقبگرد
- سه نوع مسئله در Backtracking وجود دارد
- مشکل تصمیم‌گیری (Decision Problem): ما دنبال یک راه حل عملی هستیم.
- مشکل بهینه‌سازی (Optimization Problem): بهترین راه حل را جستجو می‌کنیم.
- مشکل شمارش (Enumeration Problem): همه راه حل‌های ممکن را پیدا می‌کنیم.
- سوالات استاندارد برای backtracking شامل مسئله N-queens، مسئله Sum of Subsets ها، Graph coloring و چرخه همیلتونی (Hamiltonian cycles) است.
چه زمانی می‌توان از الگوریتم Backtracking استفاده کرد؟
به عنوان مثال، مسئله حل Sudoku را در نظر بگیرید، ما سعی می کنیم ارقام را یکی یکی پر کنیم. هر زمان که متوجه شدیم رقم فعلی نمی‌تواند به یک راه حل منجر شود، آن را حذف می‌کنیم (بازگشت) و رقم بعدی را امتحان می‌کنیم. (تولید تمام ترکیب‌های ممکن از ارقام و سپس امتحان کردن هر ترکیب یک به یک)؛ زیرا هر زمان که به عقب برگردد مجموعه ای از جایگشت‌ها را حذف می‌کند.
سخن پایانی
در این مقاله، ما با چندین الگوریتم مهم و پرکاربرد در علوم کامپیوتر آشنا شدیم. الگوریتم‌های جستجوی خطی و دودویی با پیچیدگی‌های زمانی متفاوت، الگوریتم‌های مرتب‌سازی حبابی، درجی، انتخابی، هرمی، و ادغامی که هرکدام ویژگی‌های منحصر به فرد خود را دارند و الگوریتم‌های پیمایش گراف مانند BFS و DFS که در کاربردهای مختلف مسائل گرافی مورد استفاده قرار می‌گیرند.
همچنین، الگوریتم‌های دایجسترا و فلوید وارشال که در مسائل مسیریابی و کوتاه‌ترین مسیرها کاربرد دارند و الگوریتم عقبگردان که در حل مسائل تصمیم‌گیری، بهینه‌سازی و شمارش با استفاده از تکنیک بازگشتی اجرا می‌شود، هم مورد بررسی قرار گرفتند.
با استفاده از این الگوریتم‌ها، محققان و توسعه‌دهندگان قادرند به بهبود عملکرد و کارایی سیستم‌ها، حل مسائل پیچیده و بهینه‌سازی فرآیندهای مختلف بپردازند. به طور کلی، درک و تسلط بر این الگوریتم‌ها، اساسی برای هر کسی است که به طراحی و توسعه نرم‌افزارها و سیستم‌های پیچیده علاقه‌مند است.
دیدگاهتان را بنویسید