Algoritma karmaşıklığı

Yazdığımız algoritmaların büyük verilerde bellekte ne kadar alan harcadığı, ne kadar zamanda işi yapacağı çok önemlidir. Buna algoritma karmaşıklığı denir. Algoritma karmaşıklığı bilgisayar biliminde Big O gösterimi ile ifade edilir. Algoritmanın analizini yaparken her bir satır kaç kere çalışır sorusunu sormamız gerekir.

O(1) ile ifade edilen fonksiyonların büyüme sayısı 1’ dir. Bunun kod karşılığı döngü içermeyen tek seferde çalışan yazılımlardır. Örneğin if, switch gibi ifadeler tek karar yapılarıdır bir kere çalışır.

O(n) değeri olan algoritmalar genelde döngülerdir. Bir döngü n defa dönüyorsa karmaşıklığı O(n) dir. Bu karmaşıklığın bir diğer adı lineer karmaşıklıktır.

O(ne) ifadesi iç içe olan döngülerin karmaşıklığıdır. n içteki döngünün dönme sayısı e ise dıştaki döngünün dönme sayısıdır. O(n2) karmaşıklığının diğer adı quadratic karmaşıklıktır.

O(logn) karmaşıklığına logaritmik karmaşıklık denir. Bir eleman dizisi küçük parçalara bölünerek işleniyorsa algoritma logaritmik karmaşıklığa sahiptir.

Resim 1- Big O karmaşıklığı

.Net Koleksiyonlarındaki Operasyonların Karmaşıklığı

List

· List veri yapısı elemanlara rastgele veya inde index’li erişimlerde tercih edilir.

· Çok yönlüdürler. Genelde verileri genel amaçlarla gruplandırmak için kullanılmaktadırlar.

· Sort() metodu hızlı sıralama algoritmasını uygulamıştır. Bu algoritmanın O(nLogn) karmaşıklığı vardır. Eğer mevcut elemanları sıralayıp, sadece sona yeni eleman eklemek istiyorsanız SortedList yerine bu metodu kullanmak daha iyidir. Çünkü SortedList’e eleman eklemenin O(logn) karmaşıklığı varken, List’e eleman eklemenin O(1) maliyeti vardır.

· Insert() ve Remove() metodlarına çok fazla yüklenmekten kaçının. Dizi kaydırıldığı için O(n) maliyeti olacaktır. Dizide kaydırma olmadığı için en sondan eleman çıkarmanın maliyeti O(1) olacaktır.

· Eleman eklemenin normal şartlarda maliyeti O(1)’dir. İç dizinin boyutu limite ulaştığında, boyutu iki katı olacak şekilde yeni bi dizi yaratılır ve elemanlar kopyalanır. Eğer başlangıçta ne kadar eleman olacağını biliyorsanız, o kapasitede List yaratırsanız, ilk eklemede zaman ve bellek’ten tasarruf sağlarsınız.

Dictionary

· Bu veri yapıları erişim için çok mükemmeldir, fakat elemanların sıralı olmasını garanti etmez.

· Elemanı hızlı getirebilmek, hash’leme algoritmasının kalitesine bağlıdır, basit olmalı ve zaman bağımlı değişebilir olmaması gerekir.

· Veriye eşim O(1) ‘e yakındır.

SortedList, Sorted Dictionary

· Bu veri yapıları arka planda arama ağacını kullanır. Ağaçlar hızlı ekleme, çıkarma ve arama için idealdir.

· Arama yapmanın maliyeti O(log n) ‘dir.

· İki veri yapısı bellek kullanımı ve ekleme ve çıkarma maliyeti açısından farklılaşır.

· SortedList SortedDictionary’den daha az bellek kullanır.

· SortedList Keys ve Values property’lerinden dönen kolleksiyonlarda indeksli getirmeyi daha efektif yapar.

· SortedDictionary sıralanmamış veri üzerinde daha hızlı ekleme ve çıkarma yapar. Bu işlemin SortedDictionary’de maliyet O (log n) iken SortedList’te O(n)’dir.

· Eğer sıralanmış diziden oluşturuluyorsa SortedList SortedDictionary’den daha hızlıdır.

Hepsinin karşılaştırmalı maliyetlerini aşağıdaki tabloda gösterebiliriz:

Alan-Zaman Ödünleşimi ve Etkinlik

Optimal bellek kullanımı ve çalışma süresi performansı arasında genellikle bir ödünleşim vardır. Genelde bir algoritma için, alan verimliliği ve zaman verimliliği iki zıt uçta uzanır ve aralarındaki her nokta belirli bir zaman ve alan verimliliğine sahiptir. Böylece, ne kadar fazla zaman verimliliğine sahip olursanız, sahip olduğunuz alan verimliliği o kadar az olur ve bunun tersi de geçerlidir. Örneğin, Mergesort algoritması son derece hızlıdır ancak işlemleri yapmak için çok yer gerektirir. Diğer tarafta, Bubble Sort son derece yavaştır, ancak minimum alan gerektirir.

Doğru Koleksiyonun Seçilmesi

Tüm durumlarda en iyi olabilecek bir koleksiyon yoktur. Tamamen ihtiyaçlara göre seçimler değişir. Doğru seçim yaparken şimdiye kadar bahsettiğimiz zaman karmaşıklıklarını ve alan kullanımını dikkate alıp nelerden ödün verebileceğinizi bilmeniz gerekir.