Java’da Özyinelemeli Fonksiyonlar ve Büyük O Gösterimi Örneği

Big O Notions

Merhaba arkadaşlar! Bu makalede, Java dilinde “Cracking the Coding Interview” kitabında yer alan eğitici bir soruyu ele alacağız ve içerisindeki kodları ayrıntılı bir şekilde açıklayarak recursive (özyinelemeli) fonksiyonları ve Big O notasyonunun önemini anlayacağız. Aynı zamanda, bu kitap üzerinde çalışarak önemli kavramları öğrenmek ve paylaşmak istediğimizi vurgulamak isterim.

Sorunun Tanımı:
— — — — — — — — — — — — — — — — — -

Kitaptan aldığımız soru, verilen bir string içindeki karakterleri kullanarak sıralanmış tüm kombinasyonları bulup ekrana yazdıran bir programı içermektedir.

public class RecursiveCombination {

    static int numChars = 26;
    static void printSortedString(int remaining) {
        printSortedString(remaining, "");
    }
    static void printSortedString(int remaining, String prefix) {
        if (remaining == 0) {
            if (isInOrder(prefix)) {
                System.out.println(prefix);
            }
        } else {
            for (int i = 0; i < numChars; i++) {
                char c = ithLetter(i);
                printSortedString(remaining - 1, prefix + c);
            }
        }
    }
    static boolean isInOrder(String s) {
        for (int i = 1; i < s.length(); i++) {
            int prev = ithLetter(s.charAt(i - 1));
            int curr = ithLetter(s.charAt(i));
            if (prev > curr)
                return false;
        }
        return true;
    }
    static char ithLetter(int i) {
        return (char) ('a' + i);
    }
    public static void main(String[] args) {
        int n = 3; // Örnek olarak, 3 karakterli kombinasyonları oluşturacağız
        System.out.println("Tüm Sıralanmış Kombinasyonlar:");
        printSortedString(n);
    }
}

Kod ve Açıklamalar:
— — — — — — — — — — — — — — — — — -

Yukarıda verilen Java kodu, verilen bir string içindeki karakterleri kullanarak tüm sıralanmış kombinasyonları oluşturan bir özyinelemeli fonksiyon içermektedir. Kodu adım adım inceleyelim:

printSortedString(int remaining) Fonksiyonu

• Bu fonksiyon, kullanıcıya daha kolay bir kullanım sunmak için yardımcı bir metottur.
• İçerisinde printSortedString(int remaining, String prefix) fonksiyonunu çağırarak işlemi gerçekleştirir.

printSortedString(int remaining, String prefix) Fonksiyonu

• Bu fonksiyon, verilen remaining parametresine göre sıralanmış tüm kombinasyonları oluşturur ve ekrana yazdırır.
• remaining parametresi, kaç karakterin kaldığını belirtir. Başlangıçta bu değer 26 olarak tanımlanır (alfabe uzunluğu).
• prefix parametresi, halihazırda oluşturulmuş karakter kombinasyonlarını temsil eder.
• Eğer remaining değeri sıfır olduğunda ve isInOrder fonksiyonu true döndüğünde, oluşturulan kombinasyonu ekrana yazdırır.
• Eğer remaining değeri sıfır değilse, her karakteri prefix ile birleştirerek tekrar printSortedString fonksiyonunu çağırır.

isInOrder(String s) Fonksiyonu

• Bu fonksiyon, verilen bir string’in alfabetik sıraya uygun olup olmadığını kontrol eder.
• String içindeki karakterler sıralı ise true, değilse false döndürür.

ithLetter(int i) Fonksiyonu

• Bu fonksiyon, verilen bir indekse göre alfabetik sırada ilgili karakteri döndürür.

Örnek Çıktı:

Örneğin, n = 3 olarak aldığımızda, aşağıdaki örnek çıktıyı elde ederiz:

abc
acb
bac
bca
cab
cba

Big O Notasyonu Analizi:
— — — — — — — — — — — — — — — —

Örnek kodumuzda, `printSortedString(int remaining, String prefix)` fonksiyonu özyinelemeli bir yapıya sahiptir ve her çağrıda iki alt çağrı yapmaktadır. İlk çağrıda `remaining` değeri 1 azaltılarak tekrar kendisini çağırmakta ve ikinci çağrıda `remaining` değeri sabit tutularak bir sonraki karakterle birleştirilmiş `prefix` ile kendisini çağırmaktadır.

Her bir çağrıda iki alt çağrı yapılması, her alt çağrının da iki alt çağrı yapması gibi işlem devam eder. Bu durum, her seviyede çağrılan alt fonksiyonların sayısının iki katı olarak artması anlamına gelir.

Özyinelemeli bir fonksiyonda, çağrılan alt fonksiyonların sayısı giriş boyutuna (remaining) bağlı olarak değişir. `remaining` değeri her bir çağrıda 1 azaltıldığından, özyineleme derinliği n kez artar. Yani, fonksiyonun çağrıldığı her seviyede alt fonksiyonlar 2 katına çıkar.

Bu nedenle, özyinelemeli fonksiyonun zaman karmaşıklığı 2^n olarak ifade edilir. Bu, giriş boyutu (remaining) arttıkça fonksiyonun çalışma süresinin hızla artacağı anlamına gelir. Dolayısıyla, bu tür özyinelemeli fonksiyonlar genellikle yüksek giriş boyutlarında yavaş çalışabilir ve performans sorunlarına neden olabilir.

Örneğin, `n = 3` için, fonksiyon ²³ = 8 alt çağrı yapacaktır. Eğer `n = 4` olsaydı, fonksiyon ²⁴ = 16 alt çağrı yapacaktı. Her bir alt çağrının içinde de alt fonksiyonlar çağrıldığı için, sürekli olarak artan alt çağrı sayısı, giriş boyutunun arttıkça fonksiyonun çalışma süresini büyük ölçüde etkileyecektir.

Bu nedenle, özyinelemeli yapıya sahip bir fonksiyonun zaman karmaşıklığını ifade etmek için Big O notasyonu olarak O(2^n) kullanılır.

Sonuç:
— — — — — — -

Bu yazımızda “Cracking the Coding Interview” kitabından bir eğitici soruyu ele alarak Java dilinde recursive fonksiyonların ve Big O notasyonunun önemini anlamaya çalıştık.

Özyinelemeli fonksiyonların kullanımı ve Big O notasyonunun zaman karmaşıklığını analizdeki önemini vurgulayarak, projelerinizde daha etkili ve optimize edilmiş kodlar oluşturabilirsiniz. Kitap üzerinde çalışarak, gelecekteki programlama çalışmalarınızda daha başarılı olmanızı dilerim. Mutlu kodlamalar!

Kaynaklar:

1. Gayle Laakmann McDowell, “Cracking the Coding Interview: 189 Programming Questions and Solutions”, CareerCup LLC, 2015. Kitap Linki
2. GeeksforGeeks, “Big O notation”, GeeksforGeeks. Kaynak Linki
3. Java Documentation, Oracle, “The Java™ Tutorials”. Kaynak Linki

Bu kaynaklar, özyinelemeli fonksiyonların analizi ve Big O notasyonunun anlaşılmasına yardımcı olacak değerli bilgiler ve örnekler içermektedir. Bu kaynakları inceleyerek daha fazla bilgi edinebilir ve programlama becerilerinizi geliştirebilirsiniz. İyi çalışmalar!