Program analysis and logarithms

Hazırlık: fonksiyon çiftlerini karşılaştırma

For each pair, decide whether f = O(g), f = Ω(g), f = Θ(g), or none:

Her çift için f = O(g), f = Ω(g), f = Θ(g) ilişkilerinden hangisinin geçerli olduğuna veya hiçbirinin geçerli olmadığına karar verin:

In every case the rule is the same: find the fastest-growing term on each side and compare those.

Her durumda kural aynıdır: her iki tarafta en hızlı büyüyen terimi bulun ve bunları karşılaştırın.

Büyük-O sınırlarını çarpma

Multiplying by a constant changes nothing. O(c · f(n)) is the same as O(f(n)); the constant is absorbed into the hidden constant of the Big-O. So O(3n²) = O(n²) and O(n/2) = O(n).

Bir sabitle çarpmak hiçbir şeyi değiştirmez. O(c · f(n)) ile O(f(n)) aynıdır; sabit, Büyük-O’nun gizli sabitinin içine alınır. Dolayısıyla O(3n²) = O(n²) ve O(n/2) = O(n).

Multiplying by a growing function matters. If one piece of a program costs O(f(n)) and it is repeated O(g(n)) times, the total is O(f(n) · g(n)). This is the single most used rule in program analysis: a loop that runs n times around a loop that runs n times costs n × n = O(n²). Three nested loops of n each cost O(n³).

Büyüyen bir fonksiyonla çarpmak önemlidir. Programın bir parçası O(f(n)) maliyetliyse ve O(g(n)) kez tekrarlanıyorsa toplam maliyet O(f(n) · g(n)) olur. Program analizinde en çok kullanılan tek kural budur: n kez çalışan bir döngünün içinde n kez çalışan bir döngü varsa maliyet n × n = O(n²)’dir. Her biri n kez çalışan iç içe üç döngü O(n³) tutar.

Örnek 1: seçmeli sıralama (selection sort)

Selection sort sorts a list by repeatedly finding the smallest remaining item and moving it to the front:

Seçmeli sıralama, kalan elemanların en küçüğünü tekrar tekrar bulup başa taşıyarak bir listeyi sıralar:

selection_sort(s, n):
    for i from 0 to n−1:
        min = i
        for j from i+1 to n−1:
            if s[j] < s[min]:
                min = j
        swap s[i] and s[min]

selection_sort(s, n):
    for i from 0 to n−1:
        min = i
        for j from i+1 to n−1:
            if s[j] < s[min]:
                min = j
        s[i] ile s[min] yer değiştir

In words: position 0 gets the smallest of all n items; position 1 gets the smallest of the remaining n−1; and so on.

Sözel olarak: 0. konuma n elemanın en küçüğü, 1. konuma kalan n−1 elemanın en küçüğü yerleştirilir; bu böyle sürer.

Rough analysis. The outer loop runs n times. For each outer step, the inner loop runs at most n times. So the total is at most n × n = O(n²).

Kaba analiz. Dış döngü n kez çalışır. Her dış adım için iç döngü en fazla n kez çalışır. Dolayısıyla toplam en fazla n × n = O(n²)’dir.

Is that tight? Yes. For the first n/2 outer steps, the inner loop scans at least n/2 items, so at least (n/2) × (n/2) = n²/4 steps happen. That is a lower bound of Ω(n²), so selection sort is Θ(n²).

Bu sınır sıkı mı? Evet. İlk n/2 dış adımda iç döngü en az n/2 elemanı tarar; dolayısıyla en az (n/2) × (n/2) = n²/4 adım gerçekleşir. Bu, Ω(n²) alt sınırını verir; yani seçmeli sıralama Θ(n²)’dir.

Exact count. The inner if runs (n−1) + (n−2) + … + 2 + 1 times, which is the sum from Lecture 1:

Kesin sayı. İçteki if, (n−1) + (n−2) + … + 2 + 1 kez çalışır. Bu, Ders 1’deki toplamdır:

That is about n²/2, confirming Θ(n²). Note that selection sort does the same work whatever the input looks like: its best, worst and average cases are all Θ(n²).

Bu değer yaklaşık n²/2’dir ve Θ(n²)’yi doğrular. Seçmeli sıralamanın, girdi nasıl görünürse görünsün aynı işi yaptığına dikkat edin: en iyi, en kötü ve ortalama durumlarının tümü Θ(n²)’dir.

Örnek 2: eklemeli sıralama (insertion sort)

Insertion sort is how most people sort a hand of cards: take the next item and slide it leftwards until it sits in the right place among the items already sorted.

Eklemeli sıralama, çoğu insanın elindeki oyun kartlarını sıralama biçimidir: sıradaki elemanı alın ve önceden sıralanmış elemanlar arasında doğru yerine oturana kadar sola kaydırın.

insertion_sort(s, n):
    for i from 1 to n−1:
        j = i
        while j > 0 and s[j] < s[j−1]:
            swap s[j] and s[j−1]
            j = j − 1

insertion_sort(s, n):
    for i from 1 to n−1:
        j = i
        while j > 0 and s[j] < s[j−1]:
            s[j] ile s[j−1] yer değiştir
            j = j − 1

The slide walks through sorting the letters of INSERTIONSORT one letter at a time; the sorted prefix grows by one letter per outer step.

Slayt, INSERTIONSORT sözcüğünün harflerini birer birer sıralamayı gösterir; sıralı önek her dış adımda bir harf büyür.

The inner loop is a while, not a for, so its number of iterations depends on the data, which makes the analysis less mechanical. But it can never run more than i times (it stops at the left end), so the outer loop makes n calls to something costing at most n steps: O(n²).

İç döngü bir for değil, while döngüsüdür; dolayısıyla yineleme sayısı verilere bağlıdır ve analiz daha az mekanik hâle gelir. Ancak hiçbir zaman i’den fazla çalışamaz (sol uçta durur). Bu yüzden dış döngü, en fazla n adım maliyetli bir işleme n çağrı yapar: O(n²).

Is that tight? The reverse-sorted input (10, 9, 8, …, 1) forces every new item to slide all the way to the front, giving 1 + 2 + … + (n−1) ≈ n²/2 swaps. So the worst case is Θ(n²). Unlike selection sort, insertion sort’s best case is different: on an already sorted list the while loop never runs and the whole thing takes Θ(n).

Bu sınır sıkı mı? Ters sıralı girdi (10, 9, 8, …, 1), her yeni elemanı en başa kadar kaymaya zorlar; bu da 1 + 2 + … + (n−1) ≈ n²/2 yer değiştirme verir. Dolayısıyla en kötü durum Θ(n²)’dir. Seçmeli sıralamadan farklı olarak eklemeli sıralamanın en iyi durumu değişiktir: zaten sıralı bir listede while döngüsü hiç çalışmaz ve tüm işlem Θ(n) sürer.

Asimptotik baskınlık: büyüme hızı neden sabitleri geride bırakır?

Skiena’s picture: a rocket burns all its fuel quickly, reaches a high speed, then coasts at a constant speed. A solar sail accelerates very slowly but never stops accelerating. However fast the rocket, the sail eventually overtakes it. A function that grows faster dominates one that grows slower, no matter how the constants are set.

Skiena’nın benzetmesi: bir roket tüm yakıtını hızla tüketir, yüksek bir hıza ulaşır ve ardından sabit hızla yol alır. Bir güneş yelkeni çok yavaş ivmelenir ama ivmelenmeyi hiç bırakmaz. Roket ne kadar hızlı olursa olsun, yelken sonunda onu geçer. Daha hızlı büyüyen bir fonksiyon, sabitler nasıl seçilmiş olursa olsun, daha yavaş büyüyen fonksiyona baskındır.

The following table (from the slides) shows how long each growth rate takes if one step is one nanosecond:

Aşağıdaki tablo (slaytlardan alınmıştır), bir adımın bir nanosaniye sürdüğü varsayımıyla her büyüme hızının gerektirdiği süreyi gösterir:

The conclusions to memorise:

Akılda tutulacak sonuçlar:

Exponential algorithms (2ⁿ, n!) become hopeless almost immediately, somewhere between n = 20 and n = 50.

Üstel algoritmalar (2ⁿ, n!) n = 20 ile n = 50 arasında bir yerde, neredeyse hemen uygulanamaz hâle gelir.

Quadratic algorithms (n²) become hopeless at or before n = 1,000,000.

Karesel algoritmalar (n²), n = 1,000,000’da veya daha önce uygulanamaz hâle gelir.

n log n algorithms are fine up to about a billion items.

n log n algoritmaları, yaklaşık bir milyar elemana kadar uygundur.

Logarithmic algorithms (log n) never break a sweat.

Logaritmik algoritmalar (log n) hiç zorlanmaz.

Hangi fonksiyonun baskın olduğuna karar verme

Formally, f(n) dominates g(n) if g(n)/f(n) goes to 0 as n grows. This is written g(n) = o(f(n)) with a little o, meaning “grows strictly slower than”. (Big-O allows equality of growth; little-o does not.)

Biçimsel olarak, n büyürken g(n)/f(n) sıfıra gidiyorsa f(n), g(n)’ye baskındır. Bu, küçük o ile g(n) = o(f(n)) biçiminde yazılır ve “kesin olarak daha yavaş büyür” anlamına gelir. (Büyük-O büyüme eşitliğine izin verir; küçük-o vermez.)

Two useful facts: nᵃ dominates nᵇ whenever a > b, because nᵇ/nᵃ = n^(b−a) shrinks to 0. And adding lower-order terms changes nothing: nᵃ + (something smaller than nᵃ) does not dominate nᵃ, because the ratio tends to 1, not 0.

İki yararlı bilgi: a > b olduğunda nᵃ, nᵇ’ye baskındır; çünkü nᵇ/nᵃ = n^(b−a) sıfıra küçülür. Ayrıca düşük dereceli terimler eklemek hiçbir şeyi değiştirmez: nᵃ + (nᵃ’ten küçük bir ifade), nᵃ’e baskın değildir; çünkü oran 0’a değil 1’e yaklaşır.

The basic ranking, which you must know cold (≫ means “dominates”):

Çok iyi bilmeniz gereken temel sıralama (≫, “baskındır” demektir):

A fuller ranking, with functions that appear in more advanced analysis (cⁿ is any exponential, n^(1+ε) is any power just above 1, α(n) is the almost-constant inverse Ackermann function from Lecture 13):

Daha ileri analizlerde karşılaşılan fonksiyonları içeren daha kapsamlı bir sıralama (cⁿ herhangi bir üstel fonksiyon, n^(1+ε) üssü 1’in biraz üzerinde olan herhangi bir kuvvet, α(n) ise Ders 13’teki neredeyse sabit ters Ackermann fonksiyonudur):

Logaritmalar

A logarithm is the inverse of an exponential: saying bˣ = y is the same as saying x = log_b y. In this course the base is almost always 2, written lg n.

Logaritma, üstel fonksiyonun tersidir: bˣ = y demek, x = log_b y demekle aynıdır. Bu derste taban neredeyse her zaman 2’dir ve lg n biçiminde yazılır.

The intuition to keep: lg n counts how many times you can halve n before reaching 1, or equivalently how many times you can double 1 before reaching n. lg 8 = 3 (8 → 4 → 2 → 1), lg 1,000,000 ≈ 20.

Akılda tutulacak sezgi: lg n, n’yi 1’e ulaşana kadar kaç kez ikiye bölebileceğinizi; eşdeğer olarak, 1’i n’ye ulaşana kadar kaç kez iki katına çıkarabileceğinizi sayar. lg 8 = 3 (8 → 4 → 2 → 1), lg 1,000,000 ≈ 20.

Logarithms show up wherever something is repeatedly halved or doubled:

Bir şeyin tekrar tekrar yarıya indirildiği veya iki katına çıkarıldığı her yerde logaritmalar ortaya çıkar:

Binary search. Looking up a name in a sorted phone book, you open it in the middle and throw away the half that cannot contain the name. Each comparison halves the remaining candidates, so about 20 comparisons find any name in a million-name book. In general it takes ⌈lg n⌉ comparisons.

İkili arama. Sıralı bir telefon rehberinde ad ararken ortasını açar ve adı içeremeyecek yarıyı elersiniz. Her karşılaştırma kalan adayları yarıya indirir; bu yüzden bir milyon ad içeren rehberde herhangi bir adı yaklaşık 20 karşılaştırma bulur. Genel olarak ⌈lg n⌉ karşılaştırma gerekir.

Trees. A binary tree doubles its number of possible leaves at each level. To have room for n leaves you need ⌈lg n⌉ levels. This is why balanced search trees (Lecture 5) have height O(log n).

Ağaçlar. Bir ikili ağaç, her düzeyde olası yaprak sayısını iki katına çıkarır. n yaprağa yer açmak için ⌈lg n⌉ düzey gerekir. Dengeli arama ağaçlarının (Ders 5) yüksekliğinin O(log n) olmasının nedeni budur.

Bits. Each extra bit doubles the number of patterns, so representing the numbers 0 to 2ⁱ − 1 takes exactly i bits, and representing 0 to n − 1 takes ⌈lg n⌉ bits.

Bitler. Her ek bit, örüntü sayısını iki katına çıkarır; dolayısıyla 0’dan 2ⁱ − 1’e kadar sayıları temsil etmek tam olarak i bit, 0’dan n − 1’e kadar sayıları temsil etmek ise ⌈lg n⌉ bit gerektirir.

Multiplication. log(xy) = log(x) + log(y). This turned multiplication into addition in the days of slide rules, and it is still handy in analysis, for example to see that log(n!) is about n log n.

Çarpma. log(xy) = log(x) + log(y). Bu özellik, hesap cetvelleri döneminde çarpmayı toplamaya dönüştürürdü; bugün de analizde, örneğin log(n!)’in yaklaşık n log n olduğunu görmek için kullanışlıdır.

The base does not matter asymptotically. Changing base only multiplies by a constant: log₂ n = (1/log₁₀₀ 2) × log₁₀₀ n ≈ 6.643 × log₁₀₀ n. Since 6.643 is a constant, O(log₂ n) = O(log₁₀₀ n) = O(log n), and we usually drop the base.

Taban, asimptotik açıdan önemli değildir. Taban değiştirmek yalnızca bir sabitle çarpar: log₂ n = (1/log₁₀₀ 2) × log₁₀₀ n ≈ 6.643 × log₁₀₀ n. 6.643 sabit olduğundan O(log₂ n) = O(log₁₀₀ n) = O(log n)’dir; bu yüzden tabanı genellikle yazmayız.

A last, real-world logarithm: US federal sentencing guidelines increase the punishment level by one step roughly each time the amount stolen doubles ($2,000 → +1, $5,000 → +2, $10,000 → +3, …, $80,000,000 → +18). Punishment grows logarithmically in the money, which perversely means one enormous crime is “cheaper” per dollar than many small ones. Logarithms make big things feel small.

Gerçek dünyadan son bir logaritma örneği: ABD federal ceza belirleme yönergeleri, çalınan miktar yaklaşık her iki katına çıktığında ceza düzeyini bir basamak artırır ($2,000 → +1, $5,000 → +2, $10,000 → +3, …, $80,000,000 → +18). Ceza, para miktarıyla logaritmik büyür; bunun tuhaf sonucu, çok büyük tek bir suçun dolar başına çok sayıda küçük suçtan “daha ucuz” olmasıdır. Logaritmalar büyük şeyleri küçük hissettirir.