Big-O gösterimi: bellek karmaşıklığı

Java'da Kod Optimizasyonu

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Bellek karmaşıklığı nedir?

Zaman karmaşıklığı, girdi boyutunun çalışma süresini nasıl etkilediğini açıklar
Bellek karmaşıklığı, girdi boyutunun bellek kullanımını nasıl etkilediğini açıklar

Bellek karmaşıklığını anlamak, aşağıdakileri sağlayan uygulamalar geliştirmek için kritiktir:

Gerektiği kadar bellek kullanır, fazlasını değil
OutOfMemoryError gibi hatalarla çökmez

Big-O Gösterimi

Gösterim, zaman karmaşıklığı ile aynıdır.

Yaygın karmaşıklık sınıfları:

O(1): Sabit — boyuttan bağımsız
O(n): Doğrusal — girdi ile artar
O(n²): Karesel — karesel artar

Maksimum bulan yöntem

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Tamsayı dizimiz 10 eleman da olsa 10 milyon da olsa, yalnızca max adlı tek bir değişken için bellek kullanırız
Bellek karmaşıklığı O(1) yani sabittir

İkiye katlama yöntemi

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

Girdide n eleman varsa, ek olarak n elemanlık alana ihtiyaç duyarız
Bellek karmaşıklığı O(n)’dir; gereken ek bellek girdiyle doğrusal artar

Çarpım tablosu yöntemi

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

n 10 ise 100 hücre; n 100 ise 10.000 hücre gerekir
Bu, O(n²) olarak sınıflandırılır

Bellek karmaşıklığı neden önemlidir?

Bellek sonlu bir kaynaktır!

Önceki örneklerimizin, 10.000 elemanlık girdi için davranışı:

findMax, O(1) -> sadece birkaç bayt ek bellek
doubleValues, O(n) -> yaklaşık 40 KB ek bellek
multiplicationTable, O(n²) -> yaklaşık 400 MB ek bellek

findMax için 8 bayt, doubleValues için 40 KB ve multiplicationTable için 400 MB bellek artışını gösteren çubuk grafiği

Bellek karmaşıklığı vs. zaman karmaşıklığı

Unutmayın:

Bazen zamanı bellekle takas ederiz
Bazen belleği zamanla takas ederiz
Doğru seçim, özel kısıtlarınıza bağlıdır

Zaman ile bellek arasındaki takası simgeleyen grafikler

Hadi pratik yapalım!

Java'da Kod Optimizasyonu