Big-O Notasyonu Nedir?

Big-O, bir algoritmanın veri boyutu (n) büyüdükçe nasıl davrandığını, işlem sayısının veya sürenin nasıl değiştiğini gösterir.

Amaç, algoritmayı değerlendirmek için üst sınırı belirtmektir.

Sadece dominant (baskın) terimler dikkate alınır. Küçük sabitler ya da düşük dereceli terimler önemsenmez.

Sık Kullanılan Big-O Kavramları

O(1): Sabit Zaman

• Tanım: Veri boyutu ne olursa olsun, algoritmanın çalışma süresi değişmez.
• Örnek:
  • Bir dizinin ilk elemanını almak. Örneğin: $array[0]
  • Hesaplama: Hep sabit süre, örneğin 1 adımda tamamlanır.

<?php
echo $array[0]; // Veri boyutu ne olursa olsun sabittir.

O(n): Doğrusal Zaman

• Tanım: Veri boyutu nn kadar büyürse, işlem süresi de nn kadar büyür.
• Örnek:
  • Bir diziyi tamamen taramak (Lineer Arama).
  • Eğer dizide 10 eleman varsa 10 adım, 100 eleman varsa 100 adım yapılır.

<?php
foreach ($array as $value) {
    if ($value == $target) {
        echo "Bulundu!";
        break;
    }
}

O(log n): Logaritmik Zaman

• Tanım: Veri boyutu büyüse bile işlem süresi çok yavaş artar. Veri boyutu iki katına çıksa bile işlem süresi yalnızca bir adım artar.
• Örnek:
  • İkili Arama: Ortadaki eleman kontrol edilir, sonra kalan yarıda arama devam eder.
  • 16 elemanlı bir dizi için maksimum log⁡₂(16) = 4 adım gerekir.

function binarySearch($array, $target) {
    $low = 0;
    $high = count($array) - 1;

    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($array[$mid] == $target) {
            return $mid; // Bulundu
        } elseif ($array[$mid] < $target) {
            $low = $mid + 1; // Sağ yarıya geç
        } else {
            $high = $mid - 1; // Sol yarıya geç
        }
    }
    return -1; // Bulunamadı
}

4. O(n²): Kare Zaman

• Tanım: Veri boyutu n kadar büyürse, işlem süresi n² kadar büyür.
• Örnek:
  • Bir dizi içindeki tüm eleman çiftlerini karşılaştırmak (örneğin, iki döngü).
  • 10 elemanlı bir dizi için 100 işlem yapılır.

<?php
for ($i = 0; $i < count($array); $i++) {
    for ($j = 0; $j < count($array); $j++) {
        echo $array[$i] . " ile " . $array[$j] . " karşılaştırılıyor.\n";
    }
}

Özet Tablo

Share on Facebook

Tweet