Koddan Time Complexity Çıkarmak: Döngüler, log n ve Recursion

Sürüm notu: Bu yazıdaki kodlar .NET 10 (C# 14) ile derlenip denenmiştir; ölçümler BenchmarkDotNet 0.15.8, testler xUnit v3 4.0.2 ile alınmıştır.

Önce Tahmin Et

Bookstore'un gün sonu raporu her siparişin yanına müşterinin adını yazıyor. Kodu yıllar önce biri yazmış ve hâlâ çalışıyor:

public static List<OrderLine> Naive(List<Order> orders, List<Customer> customers)
{
    var lines = new List<OrderLine>(orders.Count);
    foreach (var order in orders)
    {
        var customer = customers.First(c => c.Id == order.CustomerId);
        lines.Add(new OrderLine(order.Id, customer.Name, order.Total));
    }
    return lines;
}

1.000 sipariş ve 1.000 müşteri ile bu method 220 mikrosaniyede bitiyor. Şirket büyüyor; aynı rapor 10.000 sipariş ve 10.000 müşteri ile çalışacak. Süre 10 katına mı çıkar, 100 katına mı, yoksa başka bir şey mi olur? Kodda tek bir döngü görünüyor; bu, cevabını etkiliyor mu?

Önceki yazıda Big-O'nun dilini kurduk ama adımları elle saydık. Bu yazıda o sayımı koddan okumayı öğreneceğiz. Sonunda bu sorunun cevabını hem kâğıt üzerinde hem BenchmarkDotNet ile vereceğiz.

Ardışık Bloklar Toplanır, İç İçe Döngüler Çarpılır

Koddan complexity çıkarmanın iki temel kuralı var. Arka arkaya çalışan bloklar toplanır; biri diğerinin içinde çalışan bloklar çarpılır. Dört döngü şekli yazıp her birinin iç gövdesinin kaç kez çalıştığını sayalım:

public static class LoopShapes
{
    // Arka arkaya iki döngü: n + n = 2n adım -> O(n)
    public static long Sequential(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++) steps++;
        for (var j = 0; j < n; j++) steps++;
        return steps;
    }

    // Döngü içinde döngü: n * n adım -> O(n^2)
    public static long Nested(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < n; j++)
                steps++;
        return steps;
    }

    // İç döngü dıştakine bağlı: n(n-1)/2 adım -> yine O(n^2)
    public static long Triangular(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < i; j++)
                steps++;
        return steps;
    }

    // Kalan aralık her adımda yarıya iner -> O(log n)
    public static long Halving(int n)
    {
        long steps = 0;
        for (var remaining = n; remaining > 1; remaining /= 2) steps++;
        return steps;
    }
}

n = 1.000 ve n = 2.000 için gerçek çıktı:

n= 1000: sequential=    2,000 nested=  1,000,000 triangular=    499,500 halving=  9
n= 2000: sequential=    4,000 nested=  4,000,000 triangular=  1,999,000 halving= 10

n iki katına çıkınca Sequential iki katına, Nested dört katına çıktı. Asıl ilginç olan Triangular. İç döngü j < i diye yazıldığı için ilk turda hiç, son turda n − 1 kez çalışıyor. Toplam 0 + 1 + … + (n − 1) = n(n − 1)/2. Bu, Nested'ın yaklaşık yarısı; ama yarı sabit bir çarpan, n² terimi duruyor. n iki katına çıkınca o da dört katına çıktı: Θ(n²).

Bu şekil gerçek kodda çok sık çıkar. "Her kitabı kendinden sonraki kitaplarla karşılaştır" diye yazılan kopya kontrolü, "her siparişi önceki siparişlerle kıyasla" diye yazılan fraud kontrolü, hepsi üçgen döngü. "İç döngü her seferinde daha kısa, o zaman n² değildir" düşüncesi en yaygın analiz hatalarından biri.

Kuralların bir sonucu daha var: toplamada baskın terim kazanır. Bir method önce listeyi sıralıyor (O(n log n)), sonra bir kez geziyorsa (O(n)) toplam O(n log n + n) = O(n log n) olur. Yavaş parçayı hızlandırmadıkça hızlı parçayı optimize etmek complexity'yi değiştirmez.

Her Adımda Yarıya İnen Döngü: log n

Halving'de n'i iki katına çıkarmak yalnızca bir adım ekledi. Döngü değişkeni sabit bir miktar artmıyor, sabit bir oranla küçülüyor. n'den başlayıp k kez ikiye böldüğünde n/2ᵏ kalır; bu 1'e indiğinde döngü biter, yani k = log₂ n. 1.000 için ⌊log₂ 1.000⌋ = 9, 2.000 için 10.

Bu şekli binary search'te, balanced tree'lerde yükseklikte, sayının basamaklarını tek tek almakta (her adımda 10'a bölmek) görürsün. Logaritmanın tabanı Big-O'da önemli değil: log₁₀ n = log₂ n / log₂ 10 ve aradaki fark sabit bir çarpan. O yüzden O(log n) yazarken tabanı belirtmeyiz.

Küçük bir uyarı: döngü değişkeni çarpılarak büyüyorsa (i *= 2) o da log n'dir. Ama i += 2 ile büyüyorsa n/2 adım atar ve O(n)'dir. Bir döngünün log n olup olmadığını anlamak için değişkenin nasıl değiştiğine bak: toplama ve çıkarma lineer, çarpma ve bölme logaritmik.

Recursion: Recurrence Yazmak ve Recursion Tree

Recursive bir fonksiyonun maliyetini döngü sayarak bulamazsın; onun yerine bir recurrence yazarsın. Recurrence, T(n)'yi daha küçük girdilerdeki T cinsinden ifade eden bir denklem. Üç klasik örnek:

public static class Recursion
{
    // T(n) = T(n-1) + T(n-2) + O(1) -> O(phi^n), yaklaşık O(1.618^n)
    public static long NaiveFibonacci(int n, ref long calls)
    {
        calls++;
        return n < 2 ? n : NaiveFibonacci(n - 1, ref calls) + NaiveFibonacci(n - 2, ref calls);
    }

    // T(n) = T(n/2) + O(1) -> O(log n); ulaştığı recursion derinliğini döner
    public static int BinarySearchDepth(int[] sorted, int target, int low, int high, int depth = 1)
    {
        if (low > high) return depth;
        var mid = low + (high - low) / 2;
        if (sorted[mid] == target) return depth;
        return sorted[mid] < target
            ? BinarySearchDepth(sorted, target, mid + 1, high, depth + 1)
            : BinarySearchDepth(sorted, target, low, mid - 1, depth + 1);
    }

    // T(n) = 2T(n/2) + O(n) -> O(n log n)
    public static void MergeSort(int[] items, int[] buffer, int low, int high, ref long comparisons)
    {
        if (high - low < 1) return;
        var mid = low + (high - low) / 2;
        MergeSort(items, buffer, low, mid, ref comparisons);
        MergeSort(items, buffer, mid + 1, high, ref comparisons);

        int left = low, right = mid + 1, k = low;
        while (left <= mid && right <= high)
        {
            comparisons++;
            buffer[k++] = items[left] <= items[right] ? items[left++] : items[right++];
        }
        while (left <= mid) buffer[k++] = items[left++];
        while (right <= high) buffer[k++] = items[right++];
        Array.Copy(buffer, low, items, low, high - low + 1);
    }
}

Gerçek çıktı:

fib(20) =   6,765  calls =      21,891
fib(25) =  75,025  calls =     242,785
fib(30) = 832,040  calls =   2,692,537
n=    1,000: binary search depth = 10  merge sort comparisons =      8,782  n*log2(n) =      9,966
n=1,000,000: binary search depth = 20  merge sort comparisons = 18,849,374  n*log2(n) = 19,931,569

Recurrence'ı çözmenin en sezgisel yolu recursion tree çizmek: kökte ilk çağrı, altında onun yaptığı çağrılar, her düğümün yanına o çağrının recursion dışında yaptığı iş. Toplam maliyet bütün düğümlerin toplamı.

Naive Fibonacci'de her düğüm iki çocuk açıyor ve ağaç n derinliğe iniyor; kabaca 2ⁿ düğüm. Tam sayı biraz daha az: çağrı sayısı 2·F(n+1) − 1, yani fib(30) için 2.692.537. Bunu xUnit testiyle de doğruladım. Her 5 birimlik artışta çağrı sayısı yaklaşık 11 katına çıkıyor (1,618⁵ ≈ 11,1). n'e 5 eklemek işi on bir katına çıkarıyorsa bu exponential bir algoritma. Aynı alt problemleri tekrar tekrar çözdüğü için memoization ile O(n)'e iner; bunu Algoritmalar ve Data Structures serisinin dynamic programming yazısında yapacağız.

Binary search'te her çağrı tek bir çocuk açıyor ve problemi yarıya indiriyor: ağaç bir zincir, derinliği log₂ n. Çıktıda 1.000 için 10, 1.000.000 için 20. Merge sort'ta her seviyede problem ikiye bölünüyor, ağacın log₂ n seviyesi var ve her seviyedeki merge işlemlerinin toplamı n. Toplam n · log₂ n. Ölçülen karşılaştırma sayısı (18,8 milyon) n log₂ n'nin (19,9 milyon) hemen altında; merge sırasında bir taraf erken biterse kalan element'ler karşılaştırılmadan kopyalanıyor.

Master Theorem: Üç Durum, Sezgisel

"Problemi a parçaya böl, her parça n/b büyüklüğünde, bölme ve birleştirme f(n) iş" şeklindeki recurrence'lar için T(n) = a·T(n/b) + f(n) yazılır. Master theorem bunların çoğunu tek bakışta çözer. İspatına girmeden fikri şu: recursion tree'nin yapraklarındaki toplam iş n^(log_b a) kadar. Bunu kökteki iş f(n) ile kıyaslarsın.

Üçüncü durumda CLRS (Cormen, Leiserson, Rivest ve Stein'ın Introduction to Algorithms kitabı) bir de "regularity condition" ister; gerçek hayatta karşılaşacağın f(n)'ler bunu sağlar. Önemli olan sınır: Master theorem yalnızca "n/b'ye böl" şeklindeki recurrence'lar için. Naive Fibonacci gibi "n − 1 ve n − 2'ye in" recurrence'ları bu kalıba girmez; onlar için recursion tree çizmek ya da açılım yapmak gerekir.

Gizli Maliyetler: Tek Satırdaki Döngüler

Tahmin bölümündeki kodda tek bir foreach var ama customers.First(...) içeride listenin başından başlayıp eşleşmeyi bulana kadar ilerleyen bir döngü. Library method'ları, özellikle LINQ (Language Integrated Query) operatörleri, complexity'lerini saklar; onları da sayman gerekiyor. Üç yaygın vakayı aynı demo'da ölçtüm (kod kısaltıldı):

// 1) Lazy bir sorguda döngü içinde Count() ve ElementAt()
var books = CatalogFactory.Create(2_000);
var predicateCalls = 0;
IEnumerable<Book> cheap = books.Where(b => { predicateCalls++; return b.Price < 50m; });
decimal total = 0;
for (var i = 0; i < cheap.Count(); i++)
{
    total += cheap.ElementAt(i).Price;
}

// 2) string += her seferinde bütün string'i kopyalar
var csv = "";
for (var i = 0; i < n; i++) csv += "978-0000000001;";

// 3) OrderBy(...).First() ve MinBy: karşılaştırma sayısını say
_ = prices.OrderBy(p => p, comparer).First();
_ = prices.OrderBy(p => p, comparer).ToList()[0];
_ = prices.MinBy(p => p, comparer);

Gerçek çıktı:

lazy query in a loop : predicate calls = 2,692,550
materialized once    : predicate calls = 2,000
n= 1000: += allocated   15,039,944 bytes   StringBuilder    63,200 bytes
n= 2000: += allocated   60,079,944 bytes   StringBuilder   125,344 bytes
n= 4000: += allocated  240,159,944 bytes   StringBuilder   249,632 bytes
OrderBy().First()      comparisons = 999
OrderBy().ToList()[0]  comparisons = 10,917
MinBy()                comparisons = 999

Birinci vakada cheap bir liste değil, bir sorgu. Deferred execution yüzünden döngü koşulundaki her Count() çağrısı 2.000 kitabın hepsini baştan filtreliyor; ElementAt(i) da filtreyi i'nci eşleşmeye kadar yeniden çalıştırıyor. Sonuç: 2.000 kitaplık bir liste için 2,7 milyon predicate çağrısı, yani O(n²). Sorguyu bir kez ToList() ile materialize edince sayı 2.000'e iniyor. ElementAt'in dokümanı kaynağın IList<T> olması durumunda indexer'ı kullandığını söyler; bir Where sonucu ise IList<T> değil. Deferred execution'ın mekaniği C# LINQ serisindeki "LINQ Deferred Execution: Sorgu Ne Zaman Çalışır? IEnumerable ve IQueryable" yazısında.

İkinci vakada n iki katına çıkınca +='nin allocation'ı dört katına çıkıyor: 15 MB, 60 MB, 240 MB. String immutable olduğu için her += şimdiye kadarki bütün içeriği yeni bir string'e kopyalar; toplam kopyalanan karakter 15 + 30 + … + 15n ≈ 7,5n², yani O(n²). StringBuilder lineer büyüyor. Ayrıntısı C# Temelleri serisindeki "C# String'ler: Interpolation, StringBuilder ve Türkçe I Tuzağı" yazısında.

Üçüncü vaka bir sürpriz. Kâğıt üzerinde OrderBy().First() önce sıralar (O(n log n)), sonra ilkini alır. Ama ölçüm 999 karşılaştırma gösteriyor; bu tam olarak MinBy kadar, yani O(n). Sebep dotnet/runtime kaynak kodunda: OrderedEnumerable'ın TryGetFirst implementasyonu sıralamaz, listeyi bir kez gezip en küçüğü bulur. ToList()[0] yazınca bu kısayol devreye girmez ve gerçek sıralama 10.917 karşılaştırma yapar. Ders şu: complexity bazen dokümanda değil implementasyonda yazar ve sürümden sürüme değişebilir. Niyetini açıkça belirten MinBy'ı kullanmak hem okunabilir hem de bir optimizasyona güvenmemek demek.

Library method'larının complexity'si için ilk bakılacak yer Microsoft Learn'deki Remarks bölümü. List<T>.Contains için "linear search yapar, O(n)" yazar; List<T>.Add için "Count, Capacity'den küçükse O(1), değilse O(n)" yazar. İkincisinin neden yine de O(1) sayıldığı serinin dördüncü yazısının konusu.

Siparişleri Müşteriyle Eşleştirmek: O(n·m)'den O(n+m)'e

Tahmin bölümündeki koda geri dönelim. Dış döngü n sipariş geziyor. İçerideki First ortalama m/2 müşteriye bakıyor. Toplam O(n·m). n ve m ikisi de 10 katına çıkınca beklenen artış 100 kat. Düzeltme, müşterileri bir kez Dictionary'e koymak:

// Index'i bir kez kur (O(m)), sonra her sipariş için bir lookup (O(n)): O(n + m)
public static List<OrderLine> WithDictionary(List<Order> orders, List<Customer> customers)
{
    var byId = customers.ToDictionary(c => c.Id);
    var lines = new List<OrderLine>(orders.Count);
    foreach (var order in orders)
    {
        var customer = byId[order.CustomerId];
        lines.Add(new OrderLine(order.Id, customer.Name, order.Total));
    }
    return lines;
}

İki versiyonun aynı satırları ürettiğini bir xUnit testi doğruluyor (5.000 sipariş, 1.200 müşteri, Assert.Equal(expected, actual)). Ölçüm (Apple M5, .NET 10.0.13; tablo kısaltıldı):

| Method         | N     | Mean          | Ratio | Allocated |
|--------------- |------ |--------------:|------:|----------:|
| Naive          | 1000  |    220.713 us |  1.00 | 140.68 KB |
| WithDictionary | 1000  |      8.286 us |  0.04 |  84.95 KB |
| Naive          | 10000 | 32,968.864 us | 1.000 | 1406.3 KB |
| WithDictionary | 10000 |    151.117 us | 0.005 | 823.28 KB |

Naive versiyon 10 kat veride 149 kat yavaşladı. Teorinin söylediği 100 kat; fazlası büyük ihtimalle bellek erişiminden geliyor: her karşılaştırma bir Customer object'ine pointer takip ediyor ve 10.000 object artık L1 (birinci seviye) cache'e sığmıyor; üstüne her element için bir delegate çağrısı var. Dictionary'li versiyon 18 kat yavaşladı; beklenen 10 katın üstünde, çünkü bu boyutta dictionary'nin iç array'leri LOH'a (Large Object Heap, 85.000 byte üstü nesnelerin tutulduğu heap) düşüyor ve tabloda görünmeyen Gen2 collection'lar başlıyor. Yine de 10.000 kayıtta fark 218 kat. Bu boyutta 33 milisaniye "idare eder" gibi görünebilir; ama sipariş ve müşteri sayısı 100.000'e çıktığında naive versiyon saniyeler, dictionary'li versiyon birkaç milisaniye sürer.

Üretimde Dikkat

Code review'da complexity'yi en kolay yakalayacağın yer, bir döngünün içindeki collection çağrıları. Contains, IndexOf, First, Any, Where(...).Count(), Remove ve Insert(0, ...) bir List<T> üzerinde O(n)'dir; döngünün içinde O(n·m) üretirler. Döngünün içinde bir lookup görüyorsan önce "bu lookup döngüden önce bir HashSet ya da Dictionary'e çevrilebilir mi?" diye sor.

Aynı mantık veritabanı ve network için de geçerli, üstelik daha pahalı. Döngüde her element için bir sorgu atmak (N+1 problemi) O(n) sayıda round-trip demek ve her biri milisaniyeler sürer. Entity Framework Core (EF Core) serisinde gördüğümüz Include ve projection çözümleri, bu yazıdaki dictionary refactor'ının veritabanındaki karşılığı.

Son olarak, bir refactor'ı complexity iddiasıyla yapıyorsan ölçümünü ekle. "O(n·m)'den O(n+m)'e indirdim" cümlesinin yanına yukarıdaki gibi iki boyutta alınmış bir benchmark tablosu koymak hem iddianı kanıtlar hem de ileride birinin değişikliği geri almasını zorlaştırır.

Sık Düşülen Tuzaklar

LINQ'in tek satır görünmesi. orders.Where(o => customers.Any(c => c.Id == o.CustomerId)) tek satır ama iki döngü. Satır sayısı değil, her çağrının içinde ne olduğu önemli.

Bağımlı iç döngüye O(n log n) ya da O(n) demek. j < i ile yazılan üçgen döngü yine Θ(n²).

Her bölmeyi log n sanmak. i /= 2 log n'dir; ama döngünün içinde Array.Copy ile yarıyı kopyalıyorsan her adım O(n) iş yapar ve toplam n + n/2 + n/4 + … = 2n olur, yani O(n). Adım sayısını ve her adımın maliyetini ayrı ayrı say.

Bir IEnumerable'ı birden fazla kez gezmek. Rider'ın "possible multiple enumeration" uyarısı ve .NET analyzer'larındaki CA1851 kuralı bir stil uyarısı değil, gizli bir complexity uyarısı.

Implementasyon detayına güvenmek. OrderBy().First() bugün O(n) ama bu bir garanti değil, bir optimizasyon. Niyetini söyleyen API'yi (Application Programming Interface; MinBy, MaxBy) kullan.

Küçük Bir Deneme

★☆☆ for (var i = 1; i < n; i *= 3) döngüsünün adım sayısını n = 1.000 ve n = 1.000.000 için önce kâğıt üzerinde hesapla, sonra kodla doğrula.

★★☆ Şu fonksiyonun recurrence'ını yaz ve çöz: bir array'in yarısını recursive olarak işleyip ardından bütün array'i bir kez gezen Process(int[] items, int length). İpucu: T(n) = T(n/2) + n. Master theorem'in hangi durumu?

★★★ OrderMatching.Naive'i n = 10.000 sipariş, m = 100 müşteri ve n = 100 sipariş, m = 10.000 müşteri için ölç. İki ölçüm de n·m = 1.000.000 karşılaştırma öngörüyor; süreler neden farklı çıkıyor? Bir de m = 100 için dictionary'nin sabit maliyetinin lineer aramadan daha pahalı olup olmadığına bak.

Bu yazıda yalnızca zamanı saydık. Ama dictionary refactor'ı bedava değildi: m müşteri için ek bir hash tablosu ayırdık. Bir sonraki yazıda bellek tarafına geçiyoruz: space complexity, recursion'ın call stack'te kapladığı yer, kopya üreten API'ler ve 2 GB'lık bir log dosyasını belleğe almadan okumak.