Etkinlik paylaşım problemi - Greedy Yaklaşımı

Etkinlik paylaşım problemi klasik bir açgözlü(greedy) yaklaşımı ile çözülen bir problemdir.Greedy kısaca parça parça çözüme ulaşılan ve her bir aşamada o anki en optimum seçeneği seçemedir.

Eğer bir problemi Greedy yaklaşımı ile çözebiliyorsak muhtemelen o problemin çözümü diğer çözüm yöntemlerine göre en optimum çözüm olacaktır fakat her durumda …

more ...

Üs alma işlemi (a^x) - Divide and Conquer

Üs alma işlemi kullanılan programlama dilinin standart olarak verdiği işlemler ile gayet kolay olarak yapılabilen bir işlemdir.En basit hali ile çözüm şu şekildedir.

def brute(num, x):
    result = 1
    for i in range(x):
        result *= num
    return result

Bu çözüm iteratif olarak yazılmış ve O(n) karmaşıklığına sahip hoş …

more ...

Neredeyse sıralı dizi içerisinde arama - Arama Algoritması

Ufak bir işlem sonrası sıralanmış dizinin bazı elemanlarının yerleri karıştırılıyor. Örneğin i. pozisyonda olması gereken eleman i-1 ya da i+1 pozisyonunda bulunuyor. Hedef olarak verilen sayının dizi içerisindeki pozisyonunun bulunması amaçlanıyor.

Örneğin;

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2

Input: arr[] =  {10, 3 …
more ...

Girilen sayıdan bir sonraki büyük sayıyı bulma - Matematik Problemi

String olarak verilen sayının bir sonraki büyük saıyı ekrana bastıran, eğer şartlar uygun değilse imkansız yazan problemi inceleyeceğiz.

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Imkansız"

Input: n = "534976"
Output: "536479"

Çözüm için;

  1. Eğer tüm sayılar azalan sırada ise 'Imkansız' basılır.
  2. Eğer tüm …
more ...

KMP Algoritmasi - String Algoritmaları

Bir diğer string arama algoritmalarından olan KMP algoritmasına bakacağız.

Örnek olarak;

txt =  "THIS IS A TEST TEXT"
pat = "TEST"
Output : 10

ve

txt =  "AABAACAADAABAAABAA"
pat = "AABA"
Output : 0, 9, 13

Bir önceki yazıda en kaba hali ile bir text içerisinde nasıl başka bir text aramasının yapılacağını incelemiştik. O algoritma O …

more ...

Sıralı dizi içerisinde hedef sayıya en yakın k sayı - Arama Algoritması

Sıralı olarak verilen bir dizi içerisinde, hedef olarak belirtilen sayıya en yakın(eşit değil) k tane elemanı elde etmeye yarayan problemdir.

Problemin basit olarak çözümü, k tane elemanın bulunması için diziyi lineer olarak aramaktan geçer.

  1. İlk elemandan başlayarak geçit alanına kadar gel(Geçit alanı: Sonraki elemanın büyük, üzerinde bulunan elemanın …
more ...

Hangi sıralama algoritması belleğe en az sayıda yazma yapar?

Hafızaya yazma işlemini azaltmak, büyük veri kümeeleri üzerinde uğraşmanın maliyetli olduğu EEPROMs ve ya flash gibi platformlar için kazançlıdır.

Sıralama algoritmaları arasında Selection Sort agoritmasının en az sayıda yazma işlemi yaptığını(O(n)) biliyoruz. Fakat Cycle Sort neredeyse her zaman Selection Sort algoritmasına göre daha az sayıda yazma işlemi yapar …

more ...


Sıralama algoritmalarında kararlılık nedir?

Sıralama algoritmalarında bazen kararlılık ile ilgili bir takım bilgiler görürüz.Kısaca açıklamak gerekirse, sırarısz bir dizide aynı değerlere sahip elemanların dizilişi, dizi sıralandığında da korunuyorsa algoritma kararlıdır.

Kararlı özelliğine sahip algoritmalar; Insertion sort, Merge sort, Bubble sort. Kararsız olanlar; Heap sort, Quick sort.

Ancak verilen kararlı olmayan aloritmalar kolayca kararlı …

more ...

Quick sort için en kötü durum nedir?

Quick sort ortalama zamanda çalıştığında en verimli çalışan ve en çok kullanılan algoritmalardan biridir. Pivot seçiminin ne kadar önemli olduğunu algoritmayı incelediğinizde göreceksiniz.

En kötü duruma sebebiyet veren şartlar aşağıdadır.

  1. Dizi zaten aynı yönde sıralıysa.
  2. Dizi ters yönde sıralıysa.
  3. Tüm elemanlar aynıysa
more ...