Algoritmalar ve karmaşıklık: açıklamalı alıştırma soruları

1Karmaşıklık neyi ölçer

Algoritma, bir problemi çözen sonlu bir kesin adımlar listesidir; örneğin bir listeyi sıralamak ya da telefon rehberinde bir isim bulmak.

İki algoritma aynı problemi çözebilir ama çok farklı sürelerde. Karmaşıklık, girdi büyüdükçe işin nasıl büyüdüğünü anlatır.

Girdinin boyutuna n denir: sıralanacak öğe sayısı, bir listenin uzunluğu, bir graftaki düğüm sayısı.

1000 sayfalık bir telefon rehberinde isim aradığınızı düşünün. Her sayfayı okumak en fazla 1000 adım sürer. Ortadan açıp her seferinde yarıya bölmek yaklaşık 10 adım sürer.

Zaman karmaşıklığı adımları sayar. Alan karmaşıklığı ekstra belleği sayar. İkisi de n’nin bir fonksiyonu olarak yazılır.

Genellikle en kötü duruma bakılır: n boyutlu tüm girdiler içinde en çok iş. Bazen bunun yerine ortalama durum ya da en iyi durum sorulur.

2Büyük O ve büyüme sınıfları

Büyük O gösterimi yalnızca büyük n için önemli olanı tutar. Sabit çarpanları atar ve yalnızca en hızlı büyüyen terimi tutarsınız.

n = 1000 için n² terimi 3 000 000’dur, 5n ise yalnızca 5000. Küçük terimler toplamı pek değiştirmez.

Bu sınıflar, en yavaştan en hızlı büyümeye doğru tekrar tekrar karşınıza çıkar:

• O(1), sabit: bir dizi öğesini indeksiyle okumak.
• O(log n), logaritmik: her adımda problemi yarıya bölen ikili arama.
• O(n), doğrusal: en büyük değeri bulmak gibi tüm öğeler üzerinde tek geçiş.
• O(n log n): birleştirmeli sıralama (merge sort) gibi iyi sıralama algoritmaları.
• O(n²), ikinci dereceden: öğeler üzerinde iç içe iki döngü, kabarcık sıralaması (bubble sort) gibi.
• O(2ⁿ), üstel: her alt kümeyi denemek. Çabucak kullanılamaz hâle gelir.

Büyük O bir üst sınırdır: iş en fazla bu hızla büyür. Ω (Büyük Omega) bir alt sınırdır ve Θ (Teta) hem üst hem alt olan sıkı bir sınırdır.

Logaritmanın tabanı Büyük O’da önemli değildir, çünkü farklı tabanlı logaritmalar yalnızca sabit bir çarpanla ayrılır.

3Arama, sıralama ve özyineleme

Birkaç algoritma hemen her derste karşınıza çıkar. Karmaşıklıklarını olgu olarak öğrenin.

• Doğrusal arama öğeleri tek tek kontrol eder: O(n). İkili arama sıralı bir dizi gerektirir ve her adımda aralığı yarıya böler: O(log n).
• Kabarcık, ekleme ve seçme sıralaması iç içe döngülerde öğeleri karşılaştırır ve değiştirir: O(n²). Ekleme sıralaması zaten sıralı bir dizide O(n)’dir.
• Birleştirmeli sıralama diziyi yarılara böler, sıralar ve birleştirir: her durumda O(n log n), O(n) ekstra bellekle.
• Hızlı sıralama (quicksort) bir pivot etrafında böler: ortalamada O(n log n), ama en kötü durumda O(n²); örneğin ilk öğenin pivot olduğu sıralı bir dizi.
• Yalnızca öğeleri karşılaştıran hiçbir sıralama en kötü durumda Ω(n log n)’i geçemez. Sayma sıralaması karşılaştırma yapmadığı için daha hızlıdır.

Özyinelemeli bir fonksiyon, doğrudan cevapladığı bir temel duruma ulaşana kadar kendini daha küçük bir girdiyle çağırır. Çalışma süresi bir özyineleme bağıntısı olarak yazılır:

• T(n) = T(n/2) + O(1), ikili arama gibi O(log n) verir.
• T(n) = 2T(n/2) + O(n), birleştirmeli sıralama gibi O(n log n) verir.
• T(n) = T(n − 1) + O(n), O(n²) verir.
• T(n) = 2T(n − 1) + O(1), O(2ⁿ) verir.

Üç tasarım fikrini bilmekte yarar var. Böl ve fethet böler, çözer ve birleştirir. Açgözlü (greedy) her adımda yerel olarak en iyi seçimi yapar. Dinamik programlama örtüşen alt problemlerin cevaplarını saklar, böylece bir kez hesaplanırlar.

4Adım adım yöntem

Bir kod parçasının zaman karmaşıklığını bulmak için:

1. n’nin ne olduğuna karar verin: girdinin boyutu.
2. Her döngünün kaç kez çalıştığını sayın. Her seferinde 1 ekleyen döngü yaklaşık n kez çalışır. İkiye katlayan ya da yarıya bölen döngü yaklaşık log₂ n kez çalışır.
3. İç içe döngüler çarpılır. Art arda gelen döngüler toplanır.
4. Özyinelemeli bir fonksiyon için özyineleme bağıntısını yazın: kaç çağrı, hangi boyutta, artı çağrı başına iş.
5. En hızlı büyüyen terimi tutun ve sabitleri atın.
6. Küçük bir sayıyla kontrol edin, örneğin n = 8 ya da n = 1024.

Bir teori sorusunda önce anlattığı algoritmayı veya fikri adlandırın, sonra karmaşıklığını ve koşullarını (sıralı girdi, negatif olmayan ağırlıklar, örtüşen alt problemler) hatırlayın.

5Çözümlü bir örnek

Her adımı izleyin. Açmadan önce bir sonrakini tahmin etmeye çalışın.

6Sık yapılan hatalar

• Art arda çalışan döngüleri çarpmak. n + n = 2n hâlâ O(n)’dir.
• O(2n) ya da O(n/2) gibi sabitleri tutmak. İkisi de O(n)’dir.
• İkiye katlayan bir döngüyü n tur saymak. Yaklaşık log₂ n kez çalışır.
• İkili aramayı sıralanmamış veriye ya da ortasına tek adımda ulaşılamayan bağlı listeye uygulamak.
• En kötü durum sorulduğunda hızlı sıralamanın ortalama durumunu vermek.
• Büyük O’nun “tam olarak” anlamına geldiğini sanmak. O(n²) bir üst sınırdır; Θ(n²) tam büyümedir.

7Sınav soruları nasıl görünür

• Kolay: anahtar terimler ve olgular. İkili aramanın, birleştirmeli sıralamanın veya dizi erişiminin karmaşıklığı, O, Ω ve Θ’nın anlamı, özyinelemenin ne olduğu.
• Orta: kavramları uygulama. Bir kod parçasının karmaşıklığı, çözülecek bir özyineleme bağıntısı, n ikiye katlanınca sürenin nasıl değiştiği, bir göreve hangi algoritmanın uyduğu.
• Zor: olgular ve analiz. Ana teorem (master theorem), hızlı sıralamanın en kötü durumları, açgözlü ve dinamik programlama karşılaştırması ve P, NP ve NP-tam sınıfları.

P, polinom zamanda çözülebilen problemleri içerir. NP, çözümleri polinom zamanda kontrol edilebilen problemleri içerir. P’deki her problem NP’dedir; P = NP olup olmadığı hâlâ bilinmiyor.