Cracking the Coding Interview’dan Notlar: Bölüm 4— Big O

8 min readMay 5, 2020

Önceki bölüm: Bölüm 3— Mülakat Hazırlığı ve Davranışsal Sorular

Big O; algoritmaların etkinliğini tanımlamak için kullandığımız dil ve metriktir. Bu kavramı tam olarak anlamamak, geliştirdiğiniz algoritmaya gerçekten zarar verebilir.

Şu senaryoyu düşünelim: Hard diskte bir dosyanız var. Bu dosyayı ülkenin herhangi bir yerinde yaşayan bir arkadaşınıza göndermeniz ve olabildiğince hızlı bir şekilde ulaştırmanız gerekiyor. Nasıl göndermelisiniz? Çoğu insanın ilk düşüncesi e-posta, FTP veya başka bir elektronik aktarım aracı olabilir. Küçük bir dosyaysa, kesinlikle haklısınız. Havaalanına gitmek, uçağa binmek ve arkadaşınıza teslim etmek 5–10 saat sürer. Ama ya dosya gerçekten çok büyük olsaydı? Fiziksel olarak uçakla teslim etmek daha hızlı olur muydu?
Evet, aslında öyle. Bir terabaytlık bir dosyanın elektronik olarak aktarılması 1 günden fazla sürebilir. Dosyanız o kadar acilse ve maliyet bir sorun değilse, dosyayı uçakla teslim etmek daha hızlı olurdu.
Ya uçuş olmasaydı ve bunun yerine araba ile gitmek zorunda kalsaydınız? O zaman bile, gerçekten büyük bir dosya için kara yolu ile gitmek daha hızlı olurdu.

Zaman Karmaşıklığı (Time Complexity)

Veri aktarımı algoritmasının çalışma zamanını şöyle tanımlayabiliriz:

Elektronik transfer O(s): Burada s, dosyanın boyutudur. Bu, dosyayı aktarma süresinin dosyanın boyutu ile doğrusal olarak arttığı anlamına gelir.
Uçak Transferi O(1): Dosyanın boyutu arttıkça, dosyayı arkadaşınıza ulaştırmak daha fazla zaman almayacaktır. Süre sabittir. Sabit ne kadar büyük olursa olsun ve doğrusal artış ne kadar yavaş olursa olsun, doğrusal bir noktada sabiti aşacaktır.

En yaygın çalışma zamanlarından bazıları O(log n), O(n log n), O(n),
O(n²)’ dir. Bununla birlikte, olası çalışma zamanlarının sabit bir listesi yoktur.
Çalışma zamanınızda birden çok değişken de olabilir. Örneğin, w metre genişliğinde ve h metre yüksekliğinde bir çitin boyanma süresi O(wh) olarak tanımlanabilir.

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

Büyük O: Akademide büyük O, üst eşitlik sınırını tanımlar. Bir dizideki tüm değerleri yazdıran bir algoritma O(n) olarak tanımlanabilir; ancak O(n²), O(n³) veya O(2^n) olarak da tanımlanabilir. Algoritma en azından bunların herhangi biri kadar hızlıdır. Bu, “eşit veya küçüktür” ilişkisine benzer. Bob x yaşındaysa (yaşayan kimsenin 130 yaşını geçmediğini varsayalım), o zaman
x ≤ 130 diyebiliriz. Ancak x ≤ 1,000 veya x ≤ 1,000,000 denklemleri de teknik olarak doğrudur.

Büyük Omega (Ω): Akademide omega, alt eşitlik sınırını tanımlar. Bir dizideki değerlerin yazdırılması O(n), O(log n) ve O(1) ‘dir.
En nihayetinde algoritmanın bunların herhangi birinden daha hızlı olmayacağını biliriz.

Büyük Teta (θ): Akademide teta, hem O hem de omega anlamına gelir.
Yani; bir algoritma hem Ω(n), hem O(n) ise, çalışma süresi θ(n)’dir. Teta çalışma süresine sıkı bir sınır verir.

En İyi Senaryo, En Kötü Senaryo ve Beklenen Senaryo

Bir algoritmanın çalışma süresini 3 şekilde tanımlayabiliriz:

En İyi Senaryo (Best Case): Tüm elemanlar eşitse, quick sort algoritması ortalama olarak dizide bir kez dolaşır. Bu O(n)’dir. (Bu durum quick sort algoritmasının implementasyonuna da bağlıdır.)

En Kötü Senaryo (Worst Case): Ya gerçekten şanssız olursak ve pivot sürekli dizideki en büyük elemansa? (Aslında, bu kolayca olabilir. Pivot, alt dizideki ilk öğe olarak seçilirse ve dizi ters sırada sıralanırsa, en kötü senaryoyu yaşarız.) Bu durumda, özyineleme (recursion) diziyi ikiye bölemez ve her iki yarıda tekrar eder. Sadece alt diziyi bir eleman küçültür. Bu da çalışma süresini O(n²)’ye çıkarır.

Beklenen Senaryo (Expected Case): Genellikle, en iyi ya da en kötü senaryolar yaşanmaz. Tabii, bazen pivot çok düşük veya çok yüksek olacak, ancak bu sürekli olmayacaktır. Burada çalışma zamanını O(n log n) olarak bekleyebiliriz.

Peki, en iyi/en kötü/beklenen senaryo ile büyük O/teta/omega arasındaki ilişki nedir? Aslında aralarında belirli bir ilişki yoktur. Ancak her iki tarafın da “daha yüksek”, “daha düşük” ve “tam olarak doğru” gibi kavramları olduğundan, adayların bu kavramları karıştırması çok kolaydır.

En iyi, en kötü ve beklenen senaryolar belirli girdiler veya durumlar için büyük O (veya büyük teta) süresini tanımlar.

Büyük O, büyük omega ve büyük teta ise, çalışma süresi için üst, alt ve sıkı sınırları tanımlar.

Alan Karmaşıklığı (Space Complexity)

Bir algoritmada önemli olan tek şey süre değildir. Bir algoritmanın ayrıca gerektirdiği bellek veya alan miktarını da dikkate almamız gerekir.

Alan karmaşıklığı, zaman karmaşıklığına paralel bir kavramdır. N boyutunda bir dizi oluşturmanız gerekirse, bu O(n) bellek gerektirir. Eğer 2 boyutlu n*n bir diziye ihtiyacımız olursa, bu O(n²) bellek gerektirir.

int sum(int n) {    
    if (n <= 0) {        
        return 0;    
    }    
    return n + sum(n - 1);
}

Her bir çağrı, yığına (stack) bir seviye ekler. Bu çağrıların her biri çağrı yığınına eklenip, asıl bellekte yer tutar.

sum(4)  
    sum(3)    
        sum(2)      
            sum(l)        
                sum(0)

Ancak, toplamda n çağrı olması, bellekte O(n) alan kapladığı anlamına gelmez. Aşağıdaki fonksiyona bir göz atalım:

pairSum metoduna yaklaşık O(n) kadar çağrı yapılacaktır. Ancak, bu çağrılar çağrı yığınında eşzamanlı olarak mevcut değildir. Bu nedenle yalnızca O(1) alana ihtiyacınız vardır.

Sabitleri Çıkarın

O(n)’in belirli girdiler için O(1)’den daha hızlı çalışması mümkündür. Büyük O sadece artış oranını tanımlar.
Bu nedenle çalışma süresi tanımlarında sabitleri kullanmayız. O(2n) olarak tanımlanabilecek bir algoritma aslında O(n)’dir.
Birçok insan iç içe iki döngü içeren algoritmalara O(2n) demekte ısrarcıdır.. Daha net olduklarını düşünürler, ancak değildir.

Aşağıdaki iki koda bir bakalım:

int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int x : array) {    if (x < min) min = x;    if (x > max) max = x;}

int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int x : array) {    if (x < min) min = x;}for (int x : array) {    if (x > max) max = x;}

Hangisi daha hızlıdır? Birincisinde tek döngü, diğerinde iki döngü vardır. Ancak ilki döngü başına bir değil iki satır kod içerir.

Talimatların (instruction) sayısını saymak istediğinizde; assembly seviyesine inmeniz, çarpmanın toplamadan daha fazla talimat gerektirdiği, derleyicinin bir şeyleri nasıl optimize ettiği gibi detayların olduğu hesaba girmeniz gerekecektir.

Bu hesap çok karmaşıktır, bu yüzden bu yola hiç girmemek gerekir. Büyük O, bize çalışma süresinin nasıl ölçeklendiğini ifade etmemizi sağlar. Kabul etmemiz gereken sadece O(n)’in daima O(n²)’ den daha iyi olduğu anlamına gelmediğidir.

Baskın Olmayan Terimleri Çıkarın

O(n²+ n) gibi bir ifade hakkında ne yorum yapardınız? Burada ikinci n tam olarak bir sabit değil. Ancak bu çok da önemli değildir.

Sabitleri çıkardığımızı zaten söylemiştik. Bu yüzden O(n²+n²), O(n²) olacaktır. İkinci n² ifadesini umursamıyorsak, neden n ifadesini önemseyelim ki?

Baskın olmayan terimleri çıkardığımızda ifadeler şunlara dönüşür:

O(n²+n²) -> 0(n²)
O(n+log n) -> O(n)
O(5*2^n + 1000n¹⁰⁰) -> O(2^n)

Çok Kısımlı Algoritmalar: Toplama ve Çarpma

İki adımlı bir algoritmanız olduğunu varsayalım. Çalışma sürelerini ne zaman çarparsınız ve ne zaman birbirine eklersiniz?
Bu durum adayların genelde kafasını karıştırır.

Çalışma sürelerini topla O(a+b):

for (int a : arrA) {    print(a);}for (int b : arrB) {    print(b);}

Çalışma sürelerini çarp O(a*b):

for (int a : arrA) {    for (int b: arrB) {        print(a + "," + b);    }}

İlk örnekte önce a kadar iş, ardından b kadar iş yaparız. Bu nedenle toplam iş O(a+b)’dir.

İkinci örnekte ise her bir a elemanı için b kadar iş yaparız. Bu nedenle toplam iş O(a*b)’dir.

Amortize Edilmiş Süre

ArrayList ya da dinamik olarak yeniden boyutlandırılabilen bir dizi, size boyut konusunda esneklik sunan bir dizinin avantajlarını sağlar. Elemanları ekledikçe genişleyen bir ArrayList ile hiç bir zaman boyut sorunu yaşamazsınız. Bir ArrayList’in implementasyonu bir dizi ile olur. Dizi kapasitesine ulaştığında, ArrayList sınıfı iki katı kapasiteye sahip yeni bir dizi oluşturur ve tüm öğeleri yeni diziye kopyalar.

Eklemenin maliyetini nasıl tanımlarsınız?

Dizi dolu olabilir. Dizi n tane eleman içeriyorsa, o halde yeni bir eleman eklemek O(n) zaman alacaktır. 2n boyutunda yeni bir dizi oluşturmanız ve ardından n tane elemanı kopyalamanız gerekir. Bu ekleme (insert) işlemi O(n) zaman alacaktır.

Ancak, bunun çok sık gerçekleşmediğini de biliyoruz. Ekleme işlemleri çoğunlukla O(1) zaman alır.

Her ikisini de dikkate alan bir kavrama ihtiyacımız var. Amortize edilmiş süre budur. En kötü senaryo bir kez yaşanır ve uzunca bir süre tekrar yaşanmayacaktır. Bu maliyete “amortize edilmiş” süre denir.

Elemanları ekledikçe, dizinin boyutunu 2'nin katları olarak artırırız. X tane eleman, dizinin boyutunu 1, 2, 4, 8, 16, …, x kopya şeklinde artırır.

Peki 1 + 2 + 4 + 8 + 16 + … + x işleminin toplamı nedir?

Bu toplamı soldan sağa okursak, 1 ile başlayıp x’e gelene kadar çift şekilde artmaya devam eder. Sağdan sola okursak, x ile başlayıp azalarak 1 olana kadar devam eder.

O halde x + x/2 + x/4 + x/8 + … + 1 işlemin toplamı kabaca 2x’tir.

Bu yüzden x tane ekleme işlemi O(2x) süre alır. Her bir ekleme işlemi için amortize edilmiş süre O(1)’dir.

Log N Çalışma Süreleri

O(log n) ifadesini çoğunlukla görürüz, peki nereden gelir bu?

Binary search algoritmasına bir göz atalım. N boyutlu sıralı bir dizide x değerini aradığımız bir örnek olsun. X’i ilk olarak ortadaki elemanla kıyaslarız.
Eğer x bu elemana eşitse döneriz, küçükse sol taraftan, büyükse sağ taraftan aramaya devam ederiz.

search 9 within {1, 5, 8, 9, 11, 13, 15, 19, 21}    compare 9 to 11 -> smaller.    search 9 within {1, 5, 8, 9, 11}        compare 9 to 8 -> bigger        search 9 within {9, 11}            compare 9 to 9            return

N tane eleman üzerinden aramayı başlatırız. Bir adım sonra n/2 elemana, bir adım daha sonra n/4 elemana düşeriz. Listede sadece bir tane eleman kaldığında ya da x’i bulduğumuzda aramamız biter.

N = 16N 8 /* 2'ye bölünür */N 4 /* 2'ye bölünür */N 2 /* 2'ye bölünür */N 1 /* 2'ye bölünür */

Bu duruma tersten baktığımızda durum şu şekildedir:

N = 1N 2  /* 2 ile çarpılır */N 4  /* 2 ile çarpılır */N 8  /* 2 ile çarpılır */N 16 /* 2 ile çarpılır */

2^k = n ifadesindeki k nedir? Bu tam olarak log’un ne olduğunu açıklar.

2⁴ = 16 -> log2 16 = 4log2 n = k -> 2^k = n

Dizi elemanlarının zamanla yarıya indiğini gördüğünüz bir problemde, çalışma zamanı muhtemelen O(log n) olacaktır. Bu nedenle dengeli bir binary search tree üzerinde arama yapmak O(log n) kadar süre alır. Her bir kıyasla, sağa ya da sola gideriz. Düğümlerin (node) yarısı sağda, yarısı soldadır. Böylece problem alanını her seferinde yarıya indiririz.

Özyinelemeli (Recursive) Çalışma Süreleri

Bu kodun çalışma süresi nedir?

int f(int n) {    if (n <= 1) {    return 1;    } 
    return f(n - 1) + f(n - 1);}

Fonksiyonu f(4) ile çağırdığımızı varsayalım. Bu f(3)’ü iki kez çağırır. Her bir f(3) çağrısı, f(1)’e ulaşana kadar f(2)’yi çağırır.

Bu ağacın derinliği n’dir. Her bir düğümün (yani her bir fonksiyon çağrısının) iki çocuğu vardır. Bu nedenle her seviyede, üst seviyenin iki katı kadar çağrı olacaktır. Her bir seviyede düğüm sayıları şu şekildedir:

0. seviyede düğüm sayısı 1, yani 2⁰’dır.
1. seviyede düğüm sayısı 2, yani 2¹’dir.
2. seviyede düğüm sayısı 4, yani 2²’dir.
3. seviyede düğüm sayısı 8, yani 2³’tür.
4. seviyede düğüm sayısı 16, yani 2⁴’tür.

Bu nedenle 2⁰ + 2¹ + 2² + 2³ + 2⁴ + … + 2^n tane düğüm olacaktır.

Elinizde özyinelemeli bir fonksiyon olduğunda, çalışma süresi genelde O(dallar^derinlik) şeklindedir. Burada dal sayısı, fonksiyonumuzdaki her bir çocuk çağrı sayısına denk gelir. Bu da bize O(2^n) ifadesini verir.

Bu algoritmanın alan karmaşıklığı O(n)’dir. Ağaçta toplam O(2^n) düğüm olmasına rağmen, sadece O(n) tanesi belli bir zamanda yaşar. Bu nedenle sadece O(n) müsait bellek bizim için yeterli olacaktır.

Sonraki bölüm: Bölüm 5— Teknik Mülakat

<:-)