Her Programcının Bilmesi Gereken 7 Algoritma

Bir programlama öğrencisi olarak, kariyeriniz boyunca muhtemelen birçok farklı algoritma öğrenmişsinizdir. Farklı algoritmalarda yetkin olmak, herhangi bir programcı için kesinlikle gereklidir.

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 daha fazlası dahil olmak üzere birçok farklı bilgisayar bilimi alanı daha fazla. 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.

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. Sıralamayı Birleştir

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. gibi ilkel sıralama teknikleri ile karşılaştırıldığında Kabarcık Sıralaması (bu, O(n^2) zaman alır), birleştirme sıralaması mükemmel derecede verimlidir.

İlgili: Birleştirme Sıralama Algoritmasına Giriş

Birleş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. Hızlı sıralama

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

Derinlik İlk Arama (DFS), öğ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.

DFS geçişi herhangi bir rastgele düğümden başlayabilir ve her bitişik tepe noktasına dalar. Algoritma, ziyaret edilmemiş bir tepe noktası olmadığında veya bir çıkmaz sokak 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şlik-İlk Arama

Genişlik-İlk 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. Ikili arama

Ikili 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 halde 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 Yayılan Ağaç Algoritmaları

Bir grafiğin minimum yayılan ağacı (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.

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ı ayrıca 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.

Verimli Bir Programcı Algoritmalarda Uzmandır

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.

Kabuk Sıralama Algoritmasına Giriş

Kabuk sıralama en verimli yöntem olmasa da, yeni başlayanların pratik yaparak kazanacakları çok şey var.

Sonrakini Oku

Yazar hakkında