Counting work and growth

Hazırlık problemi: sırt çantası problemi

The lecture opens with a puzzle in the spirit of Lecture 1. Given a set of integers S = {1, 2, 5, 9, 10} and a target T, find a subset of S that adds up to exactly T. Each number may be used at most once. For T = 22 the answer is {1, 2, 9, 10}. For T = 23 there is no answer.

Ders, Ders 1’in yaklaşımını sürdüren bir bulmacayla açılır. S = {1, 2, 5, 9, 10} tam sayılar kümesi ve bir T hedefi verildiğinde, toplamı tam olarak T olan bir S alt kümesi bulun. Her sayı en fazla bir kez kullanılabilir. T = 22 için yanıt {1, 2, 9, 10}’dur. T = 23 için çözüm yoktur.

Three tempting greedy rules are proposed, and the exercise is to break each one with a counterexample:

Üç çekici açgözlü kural önerilir; alıştırma, her birini bir karşı örnekle çürütmektir:

First fit: walk through S left to right, adding each number if it still fits. Breaks on S = {5, 10, 20} with T = 30: it takes 5 and 10 and then 20 no longer fits, although {10, 20} works.

İlk sığan: S üzerinde soldan sağa ilerleyin; hâlâ sığıyorsa her sayıyı ekleyin. S = {5, 10, 20} ve T = 30 için bozulur: 5 ve 10’u alır, ardından 20 artık sığmaz; oysa {10, 20} çözüm verir.

Best fit (smallest first): add numbers from smallest to largest while they fit. Breaks on S = {1, 3, 4} with T = 7: it takes 1 and 3, then 4 no longer fits, although {3, 4} works.

En iyi sığan (önce en küçük): sayıları sığdıkları sürece küçükten büyüğe ekleyin. S = {1, 3, 4} ve T = 7 için bozulur: 1 ve 3’ü alır, ardından 4 artık sığmaz; oysa {3, 4} çözüm verir.

Largest first: add numbers from largest to smallest while they fit. Breaks on S = {6, 5, 5} with T = 10: it takes 6, and then neither 5 fits, although {5, 5} works.

Önce en büyük: sayıları sığdıkları sürece büyükten küçüğe ekleyin. S = {6, 5, 5} ve T = 10 için bozulur: 6’yı alır ve ardından iki 5’ten hiçbiri sığmaz; oysa {5, 5} çözüm verir.

No simple rule works. This knapsack problem returns in Lecture 21 as one of the officially “hard” problems.

Hiçbir basit kural işe yaramaz. Bu sırt çantası problemi, Ders 21’de resmen “zor” kabul edilen problemlerden biri olarak yeniden karşımıza çıkar.

RAM modeli: zamanı nasıl sayarız?

To talk about speed without picking a particular computer, the course uses the RAM model of computation (Random Access Machine). Its rules are deliberately crude:

Belirli bir bilgisayar seçmeden hızdan söz edebilmek için derste RAM hesaplama modeli (Random Access Machine, Rastgele Erişimli Makine) kullanılır. Kuralları bilerek kabaca tanımlanmıştır:

Every simple operation (+, −, =, an if-test, a function call) costs exactly one step.

Her basit işlem (+, −, =, bir if sınaması, bir fonksiyon çağrısı) tam olarak bir adım tutar.

Every memory access (reading or writing one value) costs exactly one step.

Her bellek erişimi (bir değeri okuma veya yazma) tam olarak bir adım tutar.

Loops and subroutine calls are not single steps. A loop costs the number of iterations times the cost of the body; “sort the list” is not one step, it is however many steps the sorting algorithm needs.

Döngüler ve alt program çağrıları tek bir adım değildir. Bir döngünün maliyeti, yineleme sayısı ile gövdesinin maliyetinin çarpımıdır; “listeyi sırala” tek adım değil, sıralama algoritmasının gerektirdiği kadar adımdır.

The running time of an algorithm is then just the number of steps it performs. Real computers do not work exactly like this (caches, pipelines, and multiplications that cost more than additions all exist), but the model predicts real behaviour well enough. Skiena compares it to the flat-earth model: strictly false, and still useful for finding your way to the shops.

Böylece bir algoritmanın çalışma süresi, gerçekleştirdiği adım sayısından ibaret olur. Gerçek bilgisayarlar tam olarak böyle çalışmaz (önbellekler, boru hatları ve toplamadan daha maliyetli çarpma işlemleri vardır), ancak model gerçek davranışı yeterince iyi öngörür. Skiena bunu düz dünya modeliyle karşılaştırır: kesin anlamda yanlıştır, yine de alışverişe giderken yolunuzu bulmak için işe yarar.

En iyi, en kötü ve ortalama durum

An algorithm does not take the same time on every input of the same size. Sorting 1,000 numbers that are already in order may be faster than sorting 1,000 numbers in random order. So for each input size n we can ask three questions:

Bir algoritma, aynı boyuttaki her girdide aynı sürede çalışmaz. Zaten sıralı 1,000 sayıyı sıralamak, rastgele sıradaki 1,000 sayıyı sıralamaktan daha hızlı olabilir. Bu nedenle her n girdi boyutu için üç soru sorabiliriz:

Each of these is a function of n: put in a size, get out a step count. Skiena’s lottery analogy: the best case of a lottery ticket is winning millions, the average case is losing a little, the worst case is losing the whole ticket price. Which number would you use to decide whether to buy?

Bunların her biri n’nin bir fonksiyonudur: bir boyut girer, bir adım sayısı elde edersiniz. Skiena’nın piyango benzetmesi: bir piyango biletinin en iyi durumu milyonlar kazanmaktır; ortalama durumu biraz kaybetmek, en kötü durumu ise bilet bedelinin tamamını kaybetmektir. Satın almaya karar verirken hangi sayıyı kullanırdınız?

This course uses worst-case complexity unless told otherwise. It is usually easy to work out, it is a guarantee, and in practice it usually tracks the average case anyway. The main exception is randomised algorithms (Lecture 8), whose benefit only shows up in an average-case analysis.

Bu derste aksi belirtilmedikçe en kötü durum karmaşıklığı kullanılır. Genellikle hesaplaması kolaydır, bir garanti sağlar ve uygulamada çoğunlukla ortalama durumu da izler. Başlıca istisna, yararı ancak ortalama durum analizinde ortaya çıkan rastgeleleştirilmiş algoritmalardır (Ders 8).

Kesin adım sayıları neden yanlış bir hedeftir?

Counting the exact number of steps gives ugly functions like 3n² − 100n + 6, and the exact constants depend on details we said we would ignore (which computer, which language, which compiler). What we really want is the shape of the function for large n: does it grow like n, like n², like 2ⁿ?

Adımların tam sayısını hesaplamak, 3n² − 100n + 6 gibi kullanışsız fonksiyonlar verir; kesin sabitler ise göz ardı edeceğimizi söylediğimiz ayrıntılara bağlıdır (hangi bilgisayar, hangi dil, hangi derleyici). Asıl istediğimiz, büyük n için fonksiyonun biçimidir: n gibi mi, n² gibi mi, 2ⁿ gibi mi büyür?

So instead of exact functions we work with upper bounds and lower bounds that are simple functions, ignoring constant factors and ignoring small values of n. That is what asymptotic notation does.

Bu yüzden kesin fonksiyonlar yerine, basit fonksiyonlarla ifade edilen üst sınırlar ve alt sınırlarla çalışır; sabit çarpanları ve küçük n değerlerini göz ardı ederiz. Asimptotik gösterimin yaptığı budur.

Büyük-O, Büyük-Omega, Büyük-Theta

Let f(n) be the true running time and g(n) a simple function like n² that we compare it with. Three symbols:

f(n) gerçek çalışma süresi, g(n) ise onu karşılaştırdığımız n² gibi basit bir fonksiyon olsun. Üç simge vardır:

f(n) = O(g(n)) (“f is Big-O of g”): some constant multiple of g(n) is an upper bound on f(n). Roughly, “f grows no faster than g”.

f(n) = O(g(n)) (“f, g’nin Büyük-O’sudur”): g(n)’nin sabit bir katı, f(n) için üst sınırdır. Kabaca, “f, g’den daha hızlı büyümez”.

f(n) = Ω(g(n)) (“Big-Omega”): some constant multiple of g(n) is a lower bound on f(n). Roughly, “f grows at least as fast as g”.

f(n) = Ω(g(n)) (“Büyük-Omega”): g(n)’nin sabit bir katı, f(n) için alt sınırdır. Kabaca, “f en az g kadar hızlı büyür”.

f(n) = Θ(g(n)) (“Big-Theta”): both at once. f(n) is squeezed between two constant multiples of g(n). Roughly, “f grows exactly like g”.

f(n) = Θ(g(n)) (“Büyük-Theta”): ikisi aynı anda geçerlidir. f(n), g(n)’nin iki sabit katı arasında sıkışır. Kabaca, “f tam olarak g gibi büyür”.

The formal versions, which all say “beyond some starting size n₀, the inequality always holds”:

Biçimsel tanımların tümü, “belirli bir n₀ başlangıç boyutundan sonra eşitsizlik her zaman geçerlidir” der:

f(n) = O(g(n)) if there are positive constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀.

Her n ≥ n₀ için f(n) ≤ c · g(n) olacak biçimde pozitif c ve n₀ sabitleri varsa f(n) = O(g(n))’dir.

f(n) = Ω(g(n)) if there are positive constants c and n₀ such that f(n) ≥ c · g(n) for every n ≥ n₀.

Her n ≥ n₀ için f(n) ≥ c · g(n) olacak biçimde pozitif c ve n₀ sabitleri varsa f(n) = Ω(g(n))’dir.

f(n) = Θ(g(n)) if there are positive constants c₁, c₂ and n₀ such that c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for every n ≥ n₀.

Her n ≥ n₀ için c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) olacak biçimde pozitif c₁, c₂ ve n₀ sabitleri varsa f(n) = Θ(g(n))’dir.

Two details matter. The constant c is any fixed number: you are allowed to multiply g by 1,000,000 if that is what it takes. And n₀ says we only care about large inputs: a function may be bigger for n = 3 and still be “below” for the values that matter.

İki ayrıntı önemlidir. c sabiti herhangi bir sabit sayı olabilir: gerekiyorsa g’yi 1,000,000 ile çarpabilirsiniz. n₀ ise yalnızca büyük girdileri önemsediğimizi söyler: bir fonksiyon n = 3 için daha büyük olsa da önemli olan değerlerde yine “aşağıda” kalabilir.

One warning about the equals sign: “f(n) = O(n²)” does not mean the two sides are equal. Read it as “f(n) is in the set of functions bounded above by a multiple of n²”.

Eşittir işareti hakkında bir uyarı: “f(n) = O(n²)”, iki tarafın birbirine eşit olduğu anlamına gelmez. Bunu “f(n), n²’nin bir katıyla üstten sınırlanan fonksiyonlar kümesindedir” diye okuyun.

f(n) = 3n² − 100n + 6 ile çözümlü örnekler

Upper bounds:

Üst sınırlar:

f(n) = O(n²), because 3n² > 3n² − 100n + 6 for every n ≥ 1, so c = 3 works.

f(n) = O(n²); çünkü her n ≥ 1 için 3n² > 3n² − 100n + 6’dır; dolayısıyla c = 3 işe yarar.

f(n) = O(n³) as well, because 0.01n³ eventually exceeds f(n). Big-O is a ceiling, and a higher ceiling is still a ceiling. It is true but not tight.

f(n) aynı zamanda O(n³)’tür; çünkü 0.01n³ sonunda f(n)’yi aşar. Büyük-O bir tavandır; daha yüksek bir tavan da hâlâ tavandır. Bu ifade doğrudur, ancak sıkı değildir.

f(n) is not O(n), because whatever constant c you choose, 3n² eventually beats c · n (as soon as n > c).

f(n), O(n) değildir; çünkü hangi c sabitini seçerseniz seçin, 3n² sonunda c · n’yi geçer (n > c olur olmaz).

Lower bounds:

Alt sınırlar:

f(n) = Ω(n²), because 2.99n² < 3n² − 100n + 6 once n is large enough.

f(n) = Ω(n²); çünkü n yeterince büyük olduğunda 2.99n² < 3n² − 100n + 6 olur.

f(n) = Ω(n) as well, because even 10¹⁰ · n is eventually smaller than f(n).

f(n) aynı zamanda Ω(n)’dir; çünkü 10¹⁰ · n bile sonunda f(n)’den küçük kalır.

f(n) is not Ω(n³), because f(n) eventually falls below n³/10, or any positive multiple of n³.

f(n), Ω(n³) değildir; çünkü f(n) sonunda n³/10’un veya n³’ün herhangi bir pozitif katının altına düşer.

Tight bound:

Sıkı sınır:

f(n) = Θ(n²), because it is both O(n²) and Ω(n²).

f(n) = Θ(n²); çünkü hem O(n²) hem de Ω(n²)’dir.

f(n) is not Θ(n³) (only the O part holds) and not Θ(n) (only the Ω part holds).

f(n), Θ(n³) değildir (yalnızca O kısmı geçerlidir) ve Θ(n) de değildir (yalnızca Ω kısmı geçerlidir).

The practical habit: to find the Big-Theta of a polynomial, keep the term with the highest power and drop its constant. 3n² − 100n + 6 is Θ(n²); 5n³ + 20n log n is Θ(n³).

Pratik alışkanlık şudur: bir polinomun Büyük-Theta’sını bulmak için en yüksek kuvvetli terimi tutun ve sabit katsayısını atın. 3n² − 100n + 6, Θ(n²)’dir; 5n³ + 20n log n, Θ(n³)’tür.

Büyük-O sınırlarını toplama ve çıkarma

Suppose f(n) = O(n²) and g(n) = O(n²).

f(n) = O(n²) ve g(n) = O(n²) olduğunu varsayalım.

Their sum f(n) + g(n) is O(n²): add the two constants and you have a constant that works.

Toplamları f(n) + g(n), O(n²)’dir: iki sabiti topladığınızda işe yarayan bir sabit elde edersiniz.

Their difference f(n) − |g(n)| is also O(n²): subtracting something non-negative from an O(n²) function cannot make it grow faster. (It does not become smaller in the Big-O sense either, because the constants do not have to cancel.)

Farkları f(n) − |g(n)| de O(n²)’dir: O(n²) olan bir fonksiyondan negatif olmayan bir nicelik çıkarmak, onun daha hızlı büyümesine yol açamaz. (Büyük-O anlamında daha küçük de olmaz; çünkü sabitlerin birbirini götürmesi gerekmez.)

We know nothing about lower bounds of the sum or difference, because Big-O told us nothing about lower bounds of f and g in the first place.

Toplamın veya farkın alt sınırları hakkında hiçbir şey bilmiyoruz; çünkü Büyük-O, başlangıçta da f ve g’nin alt sınırları hakkında bir şey söylemiyordu.

The general rule of thumb for sums: the bigger term wins. O(n²) + O(n) = O(n²).

Toplamlar için genel pratik kural: büyük terim kazanır. O(n²) + O(n) = O(n²).