به عنوان یک دانشجو یا کارآموز برنامه نویسی، احتمالاً الگوریتم های مختلف زیادی را در طول دوره حرفه ای خود یاد گرفته اید. مهارت در الگوریتم های مختلف برای هر برنامه نویسی کاملا ضروری است. در این مقاله به بررسی مهمترین الگوریتم های برنامه نویسی می پردازیم.
مهمترین الگوریتم های برنامه نویسی
با الگوریتم های فراوان موجود، پیگیری موارد ضروری می تواند مشکل باشد. اگر برای مصاحبه آماده می شوید یا مهارت های خود را تقویت می کنید، این لیست کار را نسبتاً آسان می کند. ادامه مقاله را بخوانید زیرا ما ضروری ترین الگوریتم ها را برای برنامه نویسان لیست می کنیم.
الگوریتم Dijkstra
Edsger Dijkstra یکی از تأثیرگذارترین دانشمندان کامپیوتر زمان خود بود و در بسیاری از زمینه های مختلف علوم محاسباتی از جمله سیستم های عامل، ساخت کامپایلر و بسیاری موارد دیگر مشارکت داشت. یکی از برجسته ترین مشارکت های Dijkstra، الگوریتم کوتاه ترین مسیر او برای نمودارها است که به نام الگوریتم کوتاه ترین مسیر Dijkstra نیز شناخته می‌شود.
الگوریتم Dijkstra کوتاه ترین مسیر را در گراف از یک منبع تا همه رئوس نمودار پیدا می کند. در هر تکرار الگوریتم، یک راس با حداقل فاصله از منبع و یکی که در کوتاه ترین مسیر فعلی وجود ندارد، اضافه می‌شود. این خاصیت توسط الگوریتم Djikstra استفاده می شود.
الگوریتم معمولاً با استفاده از یک مجموعه پیاده سازی می شود. الگوریتم Dijkstra هنگامی که با Min Heap پیاده سازی شود بسیار کارآمد است. می‌توانید کوتاه ترین مسیر را فقط در O(V+ElogV) بیابید (V تعداد رئوس و E تعداد یال های یک گراف است).
الگوریتم Dijkstra محدودیت های خود را دارد. فقط بر روی نمودارهای جهت دار و غیر جهت دار با لبه های وزن مثبت کار می کند. برای وزن های منفی، الگوریتم Bellman-ford معمولاً ترجیح داده می شود.
سؤالات مصاحبه معمولاً شامل الگوریتم Djikstra است، بنابراین ما به شدت توصیه می کنیم جزئیات و کاربردهای پیچیده آن را مطالعه و درک کنید.
الگوریتم Merge Sort
ما در این لیست چند الگوریتم مرتب سازی داریم و Merge Sort یکی از مهم ترین الگوریتم ها است. این الگوریتم مرتب سازی کارآمد بر اساس تکنیک برنامه نویسی Divide and Conquer است. در بدترین حالت، Merge Sort می تواند اعداد “n” را فقط در زمان O(nlogn) مرتب کند. در مقایسه با تکنیک های مرتب سازی اولیه مانند مرتب سازی حبابی (که زمان O(n^2) را می‌گیرد)، Merge Sort بسیار کارآمد است.
در Merge Sort، آرایه ای که باید مرتب سازی شود، بار ها به زیرآرایه ها تقسیم می‌شود تا زمانی که هر زیرآرایه از یک عدد واحد تشکیل شود. سپس الگوریتم بازگشتی به طور مکرر زیرآرایه ها را ادغام کرده و آرایه را مرتب می کند.
الگوریتم QuickSort
Quicksort یکی دیگر از الگوریتم های مرتب سازی بر اساس تکنیک برنامه نویسی Divide and Conquer است. در این الگوریتم ابتدا یک عنصر به عنوان محور انتخاب می شود و سپس کل آرایه حول این محور تقسیم می شود.
همانطور که احتمالاً حدس زده اید، یک محور خوب برای یک Quicksort مهم است. محور می تواند یک عنصر تصادفی، عنصر رسانه، اولین عنصر یا حتی آخرین عنصر باشد.
پیاده سازی های Quicksort اغلب در نحوه انتخاب یک محور متفاوت است. در حالت متوسط، Quicksort یک آرایه بزرگ را با یک محور خوب فقط در زمان O(nlogn) مرتب می کند.
کد کلی Quicksort مرتبا آرایه را روی محور تقسیم می کند و آن را در موقعیت صحیح زیرآرایه قرار می دهد. همچنین عناصر کوچک تر از محور را در سمت چپ و عناصر بزرگ تر از محور را در سمت راست خود قرار می دهد.
الگوریتم Depth First Search
Depth First Search (DFS) یکی از اولین الگوریتم های نموداری است که به دانش آموزان آموزش داده می شود. DFS یک الگوریتم کارآمد است که برای پیمایش یا جستجوی یک نمودار استفاده می شود. همچنین می توان آن را برای استفاده در پیمایش تغییر داد.
پیمایش DFS می تواند از هر گره دلخواه شروع شود و در هر راس مجاور فرو رود. زمانی که هیچ راس بازدید نشده ای وجود نداشته باشد یا بن بست وجود داشته باشد، الگوریتم به عقب برمی گردد. DFS معمولاً با یک پشته و یک آرایه برای پیگیری گره های بازدید شده پیاده سازی می شود. اجرای DFS ساده و فوق العاده کارآمد است. (V+E)، که در آن V تعداد رئوس و E تعداد یال ها است.
کاربرد های معمول پیمایش DFS شامل مرتب سازی توپولوژیکی، تشخیص چرخه ها در یک نمودار، مسیریابی و یافتن اجزای قوی مرتبط است.
الگوریتم Breadth-First Search
Breadth-First Search (BFS) به عنوان پیمایش ترتیب سطح برای درختان شناخته می شود. BFS در O(V+E) مشابه الگوریتم DFS کار می کند. با این حال، BFS از یک صف به جای پشته استفاده می کند. DFS در نمودار پایین می رود، در حالی که BFS نمودار را به طور گسترده طی می کند.
الگوریتم BFS از یک صف برای پیگیری رئوس استفاده می کند. رئوس مجاور بازدید نشده بازدید، علامت گذاری و در صف قرار می گیرند. اگر هیچ راس مجاوری نداشته باشد، یک راس از صف حذف شده و مورد بررسی قرار می گیرد.
BFS معمولاً در شبکه های همتا به همتا، کوتاه ترین مسیر یک نمودار برای یافتن حداقل درخت پوشا spanning tree استفاده می‌شود.
الگوریتم Binary Search
Binary Search یک الگوریتم ساده برای یافتن عنصر مورد نیاز در یک آرایه مرتب شده است. با تقسیم مکرر آرایه به نصف، کار می کند. اگر عنصر مورد نیاز کوچک تر از میانی ترین عنصر باشد، سمت چپ عنصر میانی بیشتر پردازش می شود. در غیر این صورت، سمت راست نصف شده و دوباره جستجو می شود. این روند تا زمانی که عنصر مورد نیاز پیدا شود تکرار می شود.
بدترین حالت پیچیدگی زمانی Binary Search، O(logn) است که آن را در جستجوی آرایه های خطی بسیار کارآمد می کند.
الگوریتم Minimum Spanning Tree Algorithms
Minimum Spanning Tree (MST) یک گراف دارای حداقل هزینه در بین همه درختان پوشا ممکن است. هزینه یک درخت پوشا بستگی به وزن لبه های آن دارد. مهم است که توجه داشته باشید که می تواند بیش از یک درخت پوشا وجود داشته باشد. دو الگوریتم اصلی MST به نام های Kruskal و Prim وجود دارد.
الگوریتم Kruskal، MST را با افزودن لبه با حداقل هزینه به مجموعه در حال رشد ایجاد می کند. الگوریتم ابتدا لبه ها را بر اساس وزن آنها مرتب می کند و سپس با شروع یال ها را به MST اضافه می کند.
توجه به این نکته مهم است که الگوریتم لبه هایی را که یک چرخه را تشکیل می دهند اضافه نمی کند. الگوریتم Kruskal برای نمودارهای پراکنده ترجیح داده می شود.
الگوریتم Prim نیز از یک ویژگی حریصانه استفاده می کند و برای نمودارهای متراکم ایده آل است. ایده اصلی در MST Prim این است که دو مجموعه متمایز از رئوس داشته باشیم. یک مجموعه حاوی MST در حال رشد است، در حالی که دیگری شامل رئوس استفاده نشده است. در هر تکرار، حداقل وزنی که این دو مجموعه را به هم متصل می کند انتخاب می شود.
الگوریتم های درخت پوشا حداقل برای تحلیل خوشه ای، طبقه بندی و شبکه های پخش ضروری هستند.
یک برنامه نویس کارآمد به الگوریتم ها مسلط است
برنامه نویسان به طور مداوم مهارت های خود را توسعه می دهند و مهارت های جدید یاد می‌گیرند. ضروریاتی وجود دارد که همه باید در آنها مهارت داشته باشند. یک برنامه نویس ماهر الگوریتم های مختلف، مزایا و معایب هر کدام را می داند و اینکه کدام الگوریتم برای یک سناریوی خاص مناسب تر است.
منبع : makeuseof
