۱. الگوریتم دیکسترا (Dijkstra’s Algorithm)

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

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

الگوریتم به طور معمول با استفاده از یک مجموعه اجرا می‌شود. الگوریتم Dijkstra هنگامی که با Min Heap اجرا می‌شود بسیار کارآمد است. شما می‌توانید کوتاه‌ترین مسیر را فقط در زمان O (V+ElogV) پیدا کنید (V تعداد رئوس و E تعداد لبه‌های یک نمودار مشخص است).

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

سؤالات مصاحبه معمولاً شامل الگوریتم Djikstra است، بنابراین توصیه می‌کنیم جزئیات و برنامه‌های پیچیده آن را درک کنید.

۲. ادغام مرتب سازی (Merge Sort)

ما چند الگوریتم مرتب سازی در این لیست داریم و Merge Sort یکی از مهمترین الگوریتم‌ها است. این یک الگوریتم مرتب سازی کارآمد بر اساس تکنیک برنامه نویسی تقسیم و تسخیر است. در بدترین حالت، مرتب سازی ادغام می‌تواند اعداد “n” را فقط در زمان O (nlogn) مرتب کند. در مقایسه با تکنیک‌های مرتب سازی اولیه مانند مرتب سازی حبابی (که زمان O (n^2) می‌گیرد)، این روش مرتب سازی بسیار کارآمد است.

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

۳. Quicksort

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

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

پیاده سازی quicksort اغلب در نحوه انتخاب محور متفاوت است. در حالت عادی، quicksort یک آرایه بزرگ را با یک محور خوب فقط در زمان O (nlogn) مرتب می‌کند.

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

۴. Depth First Search (عمق اول جستجو)

جستجوی عمق اول (DFS) یکی از اولین الگوریتم های نمودار است که به دانش آموزان برنامه نویسی آموزش داده می شود. DFS یک الگوریتم کارآمد است که برای پیمایش یا جستجوی نمودار استفاده می شود. همچنین می توان آن را تغییر داد تا در تراورس درخت استفاده شود.

پیمایش DFS می تواند از هر گره دلخواه شروع شود و در هر رأس مجاور شیرجه می زند. این الگوریتم زمانی عقب می افتد که هیچ راس بازدید نشده ای وجود داشته باشد ، یا یک بن بست وجود داشته باشد. DFS معمولاً با یک پشته و یک آرایه بولی برای پیگیری گره های بازدید شده پیاده سازی می شود. پیاده سازی DFS ساده و بسیار کارآمد است.با  (V+E) کار می کند ، جایی که V تعداد رأس و E تعداد لبه ها است.

کاربردهای معمول پیمایش DFS شامل مرتب سازی توپولوژیکی ، تشخیص چرخه ها در نمودار ، تعیین مسیر و یافتن اجزای قوی به هم پیوسته است.

۵. Breadth-First Search

Breadth-First Search (BFS) همچنین به عنوان پیمایش سطح سطح برای درختان شناخته می شود. BFS شبیه به الگوریتم DFS در O (V+E) کار می کند. با این حال ، BFS از یک صف به جای پشته استفاده می کند. DFS در نمودار غوطه ور می شود ، در حالی که BFS نمودار را در عرض وسیع طی می کند.

الگوریتم BFS از یک صف برای ردیابی رئوس استفاده می کند. رأس های مجاور بازدید نشده ، بازدید ، علامت گذاری و صف می شوند. اگر راس هیچ راس مجاور نداشته باشد ، یک راس از صف حذف شده و کاوش می شود.

BFS معمولاً در شبکه های همتا به همتا ، کوتاهترین مسیر نمودار بدون وزن و برای یافتن حداقل درخت پوشاننده استفاده می شود.

۶. Binary Search (جستجوی دودویی)

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

بدترین پیچیدگی زمانی جستجوی دودویی O (logn) است که آن را در جستجوی آرایه های خطی بسیار کارآمد می کند.

۷. Minimum Spanning Tree Algorithms (درخت پوشای مینیمم توزیع شده)

حداقل درخت پهن (MST) یک نمودار دارای حداقل هزینه در بین همه درختان پوشاننده ممکن است. هزینه درخت پهن بستگی به وزن لبه های آن دارد. توجه به این نکته ضروری است که می تواند بیش از یک درخت حداقل پهن داشته باشد. دو الگوریتم اصلی MST وجود دارد ، یعنی Kruskal’s و Prim’s.

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

توجه به این نکته ضروری است که الگوریتم لبه‌هایی را که یک چرخه را تشکیل می‌دهند اضافه نمی‌کند. الگوریتم کروسکال برای نمودارهای پراکنده ترجیح داده می‌شود.

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

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

یک برنامه نویس کارآمد مهارت بالایی در  کار با الگوریتم ها دارد

برنامه نویسان دائماً مهارت های خود را می آموزند و توسعه می دهند ، و برخی از ضروریات اساسی وجود دارد که همه باید در آن مهارت داشته باشند. یک برنامه نویس ماهر الگوریتم های مختلف ، مزایا و معایب هریک را می شناسد و می داند کدام الگوریتم برنامه نویسی برای سناریوی معین مناسب ترین است.