Veri Yapılarında Algoritma Karmaşıklığı Big-O

Yazdığınız algoritmanın veri büyüklüğüne göre ne kadar zaman alacağı, karmaşıklığının nasıl arttığı çok önemlidir. Yazdığınız algoritma kaynak kullandığı için, bu kaynaklarda para anlamına geldiği için yazdığınız algoritmanın complexity(karmaşıklığı) çok önemlidir.

http://bigocheatsheet.com/ adresinde temel algoritma karmaşıklığı anlatılmıştır.

  • Data Structure Operations
  • Heap Operations

Uygulama geliştirme sırasında algoritma veya veri yapısı seçerken karmaşıklık değerlerine bakarak bir seçim gerçekleştirmeyiz ama kullandığımız yöntemin maliyetini bilmemiz işi maliyetlendirmek açısından çok önemlidir.

Array

Array, belli uzunluğu olan bellek alanıdır. Değerler arka arkaya olan bellek alanları içerisinde saklanır. Bu değerlere erişim indeks numarası ile gerçekleştirilir.

Stack

Yığıt, verilerin üst üstesi konularak oluşturulan veri yapısıdır. En son eklediğimiz veri, yığıtın en üstüne eklenir . Veriye erişmek içinde yığıtın üstündeki verileri tek tek kaldırarak erişilebilir.

Single Linked List / Double Linked List

Single Linked List’de nesneler birbirine tek bir link ile bağlanır ve sadece önündeki nesneyi bilir. Double Linked List de ise nesneler hem ön hem de arkalarındaki nesneleri bilir.

Skip List

SkipList sıralı Single Linked List’in genişletilmiş halidir. Çünkü arama işlemi O(n) sürerken bu sistem arası daha uzak elemanlar arasıda bağlantılar kurarsak arama süresini O(n) yerine 1 node atlayarak koyduğumuzda O(n/2) , 2 node atlayarak ekstra bağ kurarsak O(n/3) gibi bir sürede erişim sağlamanıza olanak sağlar.

Hash Table

Arama ve erişim hızının çok hızlı O(1) olmasını sağlayan veri yapısıdır. Veriler anahtar’a göre hashlanerek tutulur. Aynı anahtar’dan 2 tane olmaması gerekir. Hash fonksiyonlarıda bu anahtar adreslerinin çakışmamasını garantiler.

Binary Search Tree

2 li arama ağaçları. Her ağacın sol kısmına kendisinden küçük sağ kısmına kendisinden büyük rakam gelecek şekilde dizilim gerçekleşir. Bu sayede erişim ve arama işlemleri her adımda %50 eleyerek hızlı bir şekilde gerçekleşmesini sağlar .

Cartesian Tree

B-Tree (B=Boing)

B-Tree’de ağacın çocuklarının birden fazla olması sağlanarak. Node sayısı, ağacın yüksekliğinin belli bir boyutu geçmesi engellenir. Bu sayede arama erişim daha kısa bir sürede gerçekleşebilir. Bunu daha çok AVL dışında bellekte halledemediğimiz büyük ağaçlarda kullanılır.

Red-Black Tree

Binary Search Tree’nin node’larının değer dışında renk’ değiride tutması ile dengeli ağaçlardır.

Splay Tree

AVL Tree (Self Balancing Tree)

Binary ağaçtan geliştirilen bu ağaç türünde amaç sağ ve sol çocuk yükseklik farklarının [-1, 0, 1] aralığında kalmasını sağlamaktır. Bu sayede balancing tree’ler oluşturulabilir. Aşağıdaki resimleri incelerseniz

  • 1nci örnekte Balancing -2 gelmiştir ve Right rotation gerçekleştirerek balancing 0 düşürülmüştür.
  • 2nci örnekte balancing +2 dir ve Left rotation gerçekleştirilerek balancing 0 dönüştürülmüştür.
  • 3ncü örnekte 2 seviyeli bir rotation ihtiyaç vardır. Balancing -2 iken Sola döndürme gerçekleştirilir sonrasında da sağa dönüş gerçekleştirilerek Balancing tree oluşumu sağlanır.
  • 4ncü örnektede 2 seviyeli rotation ihtiyacı bulunmaktadır. Balancing +2'dir. Önce sağa rotation, sonrasında da sola rotation işlemi gerçekleştirilir.