Her Programcının Bilmesi Gereken 7 Algoritma

Programlama meraklısı iseniz, eğitim hayatınız boyunca birçok farklı algoritma öğrenmişsinizdir. Farklı algoritmalarda yetkin olmak, herhangi bir programcı için kesinlikle gereklidir. Bu içeriğimizde de her programcının bilmesi gereken 7 algoritmadan bahsedeceğiz.

Bu kadar çok algoritma ile neyin gerekli olduğunu takip etmek zor olabilir. Bir röportaj için hazırlanıyorsanız veya sadece becerilerinizi tazeliyorsanız, bu liste işinizi nispeten kolaylaştıracaktır. Programcılar için en temel algoritmaları listelediğimiz için okumaya devam edin.

1. Dijkstra Algoritması

Edsger Dijkstra, zamanının en etkili bilgisayar bilimcilerinden biriydi ve işletim sistemleri, derleyici yapımı ve çok daha fazlası dahil olmak üzere bilgisayar biliminin birçok farklı alanına katkıda bulundu. Dijkstra’nın en dikkate değer katkılarından biri, Dijkstra’nın En Kısa Yol Algoritması olarak da bilinen grafikler için en kısa yol algoritmasının yaratıcılığıdır.

Dijkstra’nın algoritması, bir kaynaktan tüm grafik köşelerine kadar bir grafikteki en kısa yolu bulur. Algoritmanın her yinelemesinde, kaynaktan minimum uzaklıkta olan ve mevcut en kısa yolda bulunmayan bir tepe noktası eklenir. Bu, Djikstra’nın algoritması tarafından kullanılan açgözlü özelliktir.

Her Programcının Bilmesi Gereken 7 Algoritma

Algoritma tipik olarak bir küme kullanılarak uygulanır. Dijkstra’nın algoritması, Min Heap ile uygulandığında çok verimlidir; en kısa yolu sadece O(V+ElogV) zamanında bulabilirsiniz (V, verilen bir grafikteki köşe sayısı ve E kenar sayısıdır).

Dijkstra’nın algoritmasının sınırlamaları vardır; sadece pozitif ağırlıklı kenarları olan yönlendirilmiş ve yönsüz grafiklerde çalışır. Negatif ağırlıklar için Bellman-Ford algoritması tipik olarak tercih edilir.

Mülakat soruları genellikle Djikstra’nın algoritmasını içerir, bu nedenle karmaşık ayrıntılarını ve uygulamalarını anlamanızı şiddetle tavsiye ederiz.

2. Merge Sort (Bileştirme Sıralaması) Algoritması

Bu listede birkaç sıralama algoritmamız var ve birleştirme sıralama en önemli algoritmalardan biridir. Divide and Conquer programlama tekniğine dayalı verimli bir sıralama algoritmasıdır. En kötü durum senaryosunda, birleştirme sıralaması “n” sayıları yalnızca O(nlogn) zamanında sıralayabilir. Bubble Sort (O(n^2) zaman alan) gibi ilkel sıralama teknikleri ile karşılaştırıldığında , bileştirme sıralama mükemmel derecede verimlidir.

Bileştirmeli sıralamada, sıralanacak dizi, her bir alt dizi tek bir sayıdan oluşana kadar art arda alt dizilere bölünür. Özyinelemeli algoritma daha sonra alt dizileri tekrar tekrar birleştirir ve diziyi sıralar.

3. Quick Sort (Hızlı Sıralama) Algoritması

Quicksort, Divide and Conquer programlama tekniğine dayalı başka bir sıralama algoritmasıdır. Bu algoritmada, önce pivot olarak bir eleman seçilir ve tüm dizi daha sonra bu pivot etrafında bölümlenir.

Muhtemelen tahmin ettiğiniz gibi, verimli bir sıralama için iyi bir pivot çok önemlidir. Pivot, rastgele bir öğe, medya öğesi, ilk öğe veya hatta son öğe olabilir.

Hızlı sıralama uygulamaları, genellikle bir pivot seçme biçiminde farklılık gösterir. Ortalama durumda, hızlı sıralama, büyük bir diziyi yalnızca O(nlogn) zamanında iyi bir pivotla sıralar.

Quicksort’un genel sözde kodu, diziyi pivot üzerinde art arda bölümlere ayırır ve onu alt dizinin doğru konumuna konumlandırır. Ayrıca pivottan daha küçük öğeleri soluna ve pivottan daha büyük öğeleri sağına yerleştirir.

4. Derinlik Öncelikli Arama Algoritması

Derinlik Öncelikli Arama (Depth-first SearchDFS), öğrencilere öğretilen ilk grafik algoritmalarından biridir. DFS, bir grafiği geçmek veya aramak için kullanılan verimli bir algoritmadır. Ayrıca ağaç geçişinde kullanılmak üzere değiştirilebilir.

Programcının Bilmesi gereken 7 algoritma

Her Programcının Bilmesi Gereken 7 Algoritma

DFS geçişi herhangi bir rastgele düğümden başlayabilir ve her bitişik tepe noktasına dalar. Algoritma, ziyaret edilmeyen bir tepe noktası olmadığında veya bir çıkmaz olduğunda geri döner. DFS, ziyaret edilen düğümleri takip etmek için tipik olarak bir yığın ve bir boole dizisi ile uygulanır. DFS’nin uygulanması basittir ve son derece verimlidir; çalışır (V+E), burada V köşe sayısı ve E kenar sayısıdır.

DFS geçişinin tipik uygulamaları arasında topolojik sıralama, bir grafikteki döngüleri algılama, yol bulma ve güçlü bağlantılı bileşenleri bulma yer alır.

5. Geniş Öncelikli Arama Algoritması

Geniş Öncelikli Arama (BFS), ağaçlar için bir düzey sırası geçişi olarak da bilinir. BFS, bir DFS algoritmasına benzer şekilde O(V+E)’de çalışır. Ancak, BFS yığın yerine bir kuyruk kullanır. DFS grafiğin içine dalar, BFS ise grafiği enine doğru hareket ettirir.

BFS algoritması, köşeleri takip etmek için bir kuyruk kullanır. Ziyaret edilmeyen bitişik köşeler ziyaret edilir, işaretlenir ve sıraya alınır. Köşenin bitişik bir köşesi yoksa, kuyruktan bir köşe çıkarılır ve araştırılır.

BFS, eşler arası ağlarda, ağırlıksız bir grafiğin en kısa yolunda ve minimum yayılan ağacı bulmak için yaygın olarak kullanılır.

6. İkili Arama (Binary Search) Algoritması

İkili Arama , sıralanmış bir dizide gerekli öğeyi bulmak için basit bir algoritmadır. Diziyi tekrar tekrar ikiye bölerek çalışır. Gerekli eleman en ortadaki elemandan daha küçükse, orta elemanın sol tarafı daha fazla işlenir; aksi takdirde sağ taraf yarıya bölünür ve tekrar aranır. Gerekli eleman bulunana kadar işlem tekrarlanır.

İkili aramanın en kötü zaman karmaşıklığı O(logn)’dur, bu da onu doğrusal dizileri aramada çok verimli kılar.

7. Minimum Kapsamlı Ağaç Algoritmaları

Bir grafiğin minimum kapsamlı ağaç (MST), tüm olası yayılan ağaçlar arasında minimum maliyete sahiptir. Yayılan bir ağacın maliyeti, kenarlarının ağırlığına bağlıdır. Birden fazla minimum kapsayan ağaç olabileceğini not etmek önemlidir. Kruskal’s ve Prim’s olmak üzere iki ana MST algoritması vardır.

Programcının Bilmesi gereken 7 algoritma

Her Programcının Bilmesi Gereken 7 Algoritma

Kruskal’ın algoritması, büyüyen bir kümeye minimum maliyetle kenar ekleyerek MST’yi oluşturur. Algoritma önce kenarları ağırlıklarına göre sıralar ve ardından minimumdan başlayarak MST’ye kenarları ekler.

Algoritmanın bir döngü oluşturan kenarlar eklemediğine dikkat etmek önemlidir. Seyrek grafikler için Kruskal algoritması tercih edilir.

Prim Algoritması da açgözlü bir özellik kullanır ve yoğun grafikler için idealdir. Prim’in MST’sindeki ana fikir, iki farklı köşe kümesine sahip olmaktır; bir küme büyüyen MST’yi içerirken diğeri kullanılmayan köşeleri içerir. Her yinelemede, iki kümeyi birbirine bağlayacak minimum ağırlık kenarı seçilir.

Minimum yayılan ağaç algoritmaları, küme analizi, sınıflandırma ve yayın ağları için gereklidir.

Programcılar sürekli olarak becerilerini öğrenir ve geliştirirler ve herkesin yetkin olması gereken bazı temel unsurlar vardır. Yetenekli bir programcı farklı algoritmaları, her birinin yararlarını ve dezavantajlarını ve belirli bir senaryo için hangi algoritmanın en uygun olacağını bilir.

 


Yorumlar

POPÜLER HABERLER