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

baris

Barış Bideratan

Posted on May 29, 2023

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);
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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.

💖 💪 🙅 🚩
baris
Barış Bideratan

Posted on May 29, 2023

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

10 Best Developer Swags for 2023
webdev 10 Best Developer Swags for 2023

January 8, 2023

BIG O'NOTATION
programming BIG O'NOTATION

March 18, 2022

Converting AND to OR in JavaScript
programming Converting AND to OR in JavaScript

December 21, 2021

Convertendo AND para OR em JavaScript
programming Convertendo AND para OR em JavaScript

December 14, 2021