Veri Yapıları ve Algoritmalar: O(1) ve O(n)

O(1) ve O(n), algoritmanın zaman karmaşıklığını ifade eden Big-O gösterimleridir.

O(1) "Sabit zaman karmaşıklığı" anlamına gelir. Bir algoritmanın zaman karmaşıklığı O(1) ise, girdi boyutundan bağımsız olarak, işlemlerin sabit bir sürede tamamlandığı anlamına gelir. Yani, algoritma her zaman aynı sürede çalışır. Örneğin, bir diziye erişmek veya bir değişkeni güncellemek gibi işlemler O(1) karmaşıklığa sahiptir. Bu tür algoritmalar en verimli olanlardır, çünkü girdi boyutu arttıkça performansları etkilenmez.

O(n) "Lineer zaman karmaşıklığı" anlamına gelir. Bir algoritmanın zaman karmaşıklığı O(n) ise, algoritmanın çalışma süresi, girdi boyutu n ile doğru orantılı olarak artar. Yani, her bir girdi elemanı için işlemler yapılır ve girdi boyutu arttıkça çalışma süresi de artar. Örneğin, bir dizinin tüm elemanlarını kontrol etmek veya bir döngü içinde n adım atmak gibi işlemler O(n) karmaşıklığa sahiptir. Bu tür algoritmaların performansı, girdi boyutu arttıkça lineer olarak kötüleşir.

Bu iki karmaşıklık sınıfı arasındaki fark, algoritmanın performansının girdi boyutuna nasıl bağlı olduğunu gösterir. O(1) karmaşıklığa sahip algoritmalar, sabit performans sunarken, O(n) karmaşıklığa sahip algoritmaların performansı girdi boyutuyla doğru orantılı olarak değişir. O(1) karmaşıklığa sahip algoritmalar genellikle tercih edilen ve daha verimli olanlardır, ancak bazı problemler için O(n) karmaşıklık gereklidir ve bu durumda daha optimize edilmiş algoritmalar kullanılabilir.

Gelin O(1) ve O(n) zaman karmaşıklığına sahip basit bir örnek yapalım.

O(1) Zaman Karmaşıklığı Örneği:

function printFirstElement(arr) {
  if (arr.length > 0) {
    console.log(arr[0]);
  }
}

const array = [1, 2, 3, 4, 5];
printFirstElement(array);

Bu örnekte, printFirstElement fonksiyonu bir dizinin ilk elemanını ekrana basar. Fonksiyonun çalışma süresi, dizinin boyutu ne olursa olsun sabittir (birinci elemanı basmak için her zaman bir adım gerekmektedir). Bu nedenle, zaman karmaşıklığı O(1) olarak kabul edilir.

O(n) Zaman Karmaşıklığı Örneği:

function printAllElements(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

const array = [1, 2, 3, 4, 5];
printAllElements(array);

Bu örnekte, printAllElements fonksiyonu bir dizinin tüm elemanlarını ekrana basar. Fonksiyon, döngü içinde dizinin her bir elemanını tek tek basar. Döngünün çalışma süresi, dizi boyutuna bağlı olarak doğru orantılı olarak artar. Bu nedenle, zaman karmaşıklığı O(n) olarak kabul edilir.

İki örnek arasındaki fark, printFirstElement fonksiyonunun her durumda sabit bir işlem süresine sahip olmasına karşılık, printAllElements fonksiyonunun dizi boyutuyla doğru orantılı olarak çalışma süresinin artmasıdır.