Algoritma verimliliği

Algoritma verimliliğini ifade etmek için kullanılan matematiksel ifade büyük O dur.
Bu konuyu iyi kavrarsak kuracağımız her mantık, yazacağımız her kod kendini bize doğrudan verimlilik açısından açmış olacak.
Bu matematiksel terimle yapılan hız hesaplaması işlemciden bağımsız olduğu için bakan herkesin aklında aynı şeyi ifade eder.

Bir algoritmanın çözüm süresi genellikle giren eleman büyüklüğü ile ilişkilidir. Biz buna N diyoruz. N büyüdükçe algoritmanın çalışma hızının değişimini ifade etmek için aşağıda gibi bazı ifadeler kullanılır.

O(1)
O(log n)
O(N)
O(N log N)
O(N^2)

Şimdi konuya gerçek hayattan bir örnekle devam edelim!


Olay;

Genişbant interneti olan bir vatandaş 300MB'lık bir dosyayı 120 KM uzaklıktaki bir yere göndermek için internet ve ayağına usb bellek bağladığı bir güvercin kullanıyor. Güvercin hedefe ulaştığında internetten gönderilen dosyanın henüz %24'ü tamamlanmış.

Bizi ilgilendiren kısmı şu, biz gönderdiğimiz dosyanın boyutunu internetten ve güvercinin ayağındaki USB bellekte artırdığımızda ne olacak?

USB de yapılan dosya boyut artırımı hız olarak hiç bir etkide bulunmayacaktır! -USB sonsuz değil abartmayalım lütfen :) -
Ancak internette gönderilen dosyada yapılan artırım dosya boyutu kadar fark yapacaktır.

İşte USB de yapılan artırım etkisi olmadığı için O(1) olarak ifade edilir. İnternette yapılan artırım ise boyuta bağlı olarak hız değişeceği için O(N) olarak ifade edilir.

Bu hesaplamalarda N ile birlikte başka değişkenler ve sabitler olabilir. Ancak en büyük değer dışındaki bütün değerler atılır. Çünkü N büyüdükçe diğer değişkenlerin büyüme hız ihmal edilebilecek kadar küçük kalmaktadır.

Biraz kod örnekleri ile baştan başlayalım;

$n = 10;
$tour = 0;
for ($i = 0; $i < $n; $i++) {
    echo $i . PHP_EOL;
    $tour++;
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//10

Bu algoritma O(N) sürede çalışacaktır. Tur sayısı N ile eşittir.

$n = 10;
$array = [];
$tour = 0;
for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $n; $j++) {
        $array[$i][$j] = $i+$j;
        $tour++;
    }
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//100

$n = 5;
$tour = 0;
for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $n; $j++) {
        $tour++;
    }
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//25

$n = range(0, 10);
$count = count($n);
//N*(N-1)/2
echo $count*($count-1)/2 . PHP_EOL;

$tour = 0;
for ($i = 0; $i < $count; $i++) {
    $j = 0;
    while ($n[$i] != $n[$j]) {
        $j = $j + 1;
        $tour++;
    }
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//55

Bu üç algoritma O(N^2) sürede çalışacaktır. Tur sayısı n sayısının karesi olacaktır. Daha önce bahsettiğimiz sabitlerin ve küçük kısımların atılması kuralı gereği O(N*(N-1)/2) yerine direk O(N^2) diyoruz.

$a = range(0, 5);
$b = range(0, 3);

$tour = 0;
for ($i = 0; $i < count($a)-1; $i++) {
    for ($j = 0; $j < count($b)-1; $j++) {
        $tour++;
    }
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//15

Bu algoritma O(a*b) sürede çalışacaktır.

$n = 10;
$tour = 0;
while ($n >= 1) {
    echo $n . PHP_EOL;
    $n = $n / 2;
    $tour++;
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//4

$n = 20;
$tour = 0;
while ($n >= 1) {
    echo $n . PHP_EOL;
    $n = $n / 2;
    $tour++;
}

echo sprintf('Tur Sayısı: %s', $tour) . PHP_EOL;
//5

Bu algoritma O(log(N)) sürede çalışacaktır.
İşlem sayısı her defasında kendini ikiye bölerek ilerliyor, katlayarak ilerlemenin tersi.
İkinci örnekte N iki katına çıkmasına rağmen tur sayısı yalnızca 1 artmıştır.
20 log 10 = 1.3, 30 log 10 = 1.47, 40 log 10 = 1.60 şeklinde ilerliyor.
N = 20 ve N = 30 arasında yalnızca 5 tur atılırken N = 40 olduğunda 6. tura geçiliyor. Tur sayısı, sayı oranına göre çok küçük bir miktarda artış meydana getiriyor.

Burada şunu sorabilirsiniz log tabanı kaç? Aslında bunun hiç bir önemi yok. Taban yazılmadığı zaman 10 kabul ediliyor. Ama bu iki veya 10 olabilir. Kurallar gereği bunlara takılmıyoruz.

Kendini çağıran fonksiyonlarda durum nasıl dersiniz? Adı üstünde kendini çağıran. Bu da kendi sayısı kadar olacaktır.

Recursive için Faktöriyel güzel bir örnek olacaktır.
Formül olarak N! = N * (N-1) * (N-2) * (N-3) ... şeklinde gidiyor.

function factorial($n, &$tour = 0) {
    $tour++;
    if ($n <= 1) {
        return 1;
    } else {
        return $n * factorial($n-1, $tour);
    }
}

$result = factorial(5, $tour);

echo sprintf('Sonuç: %s Tur Sayısı: %s', $result, $tour) . PHP_EOL;
//Tur Sayısı: 5

Bu algoritma O(N) sürede çalışacaktır. Tur sayısı N ile eşittir.

Bu kadar sözden sonra izlemenizi tavsiye edeceğim iki video var;

1. Faktöriyel
2. Big O Notations

Kaynaklar;
Güvercin ve İnternet
Büyük O gösterimi
Big O Notation (İngilizce ve daha detaylı olan)
What is the big O notation and how do I calculate it?