Photo by Timo Volz on Unsplash

Veri Yapılarında Algoritma Karmaşıklığı

Bu yazıda farklı veri yapılarındaki işlemlerin algoritma karmaşıklığını analiz edeceğiz.

Bir önceki yazımda Algoritma Karmaşıklığı Big-O konusunu incelemiştik. Algoritmaların karmaşıklığı veri yapıları üzerinde yapılan işlemlere göre farklılıklar gösterir.

  • Access : Veri yapısındaki elemana erişmek
  • Search : Veri yapısında arama yapmak
  • Insertion: Veri yapısına eleman ekleme
  • Deletion: Veri yapısından eleman silme

Aşağıdaki resimde veri yapılarının farklı işlemler için Ortalama ve En Kötü durumda işlemi yapmak için zaman ve bellek karmaşıklığı verilmiştir.

Örneğin

  • Elimizdeki verinin sabit sayıda az elemanı var, ve belirli indeksteki elemanlara sürekli erişim ihtiyacınız var o zaman burada Array kullanmanız mantıklı olur.
  • Sürekli veri yapınız değişiyor ekleme ve çıkarma yapmanız gerekiyor ve üzerine Arama yapmanız gerekiyor bu durumda B-Tree seçmek mantıklı olur

Özetle veri yapısı seçiminiz üzerinde çalıştıracağınız algoritma ve işlemlere göre seçmeniz kodunuzun kalitesini arttıracaktır.

http://bigocheatsheet.com/

Veri yapılarında olan işlemlerin kafanızda daha iyi canlanması için kısaca görseller ile ilgili veri yapısını anlatmaya çalışacağım.

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.

Array

Erişim O(1), Arama, Ekleme ve Silme O(n)

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.

Stack

Erişim ve Arama O(n), Ekleme ve Silme O(1)

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.

Single Linked List
Double Linked List

Erişim ve Arama O(n), Ekleme ve Silme O(1)

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ında 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.

Skip List

Erişim Arama, Ekleme ve Silme O(logn)

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ı anahtardan 2 tane olmaması gerekir. Hash fonksiyonlarıda bu anahtar adreslerinin çakışmamasını garantiler.

Hash Table

Arama, Ekleme ve Silme O(1)

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 .

BST

Erişim Arama, Ekleme ve Silme O(logn)

Cartesian Tree

Max-Heap veya Mean-Heap olacak şekilde ağacın node tutmasıdır. Aşağıdaki görselde Min-Heap Cartesian Ağacı oluşturulmuştur. 1 sağında ve solunda en küçük rakamlar bulunup bunun altındaki düğümlerde de aynı mantık işletilmiştir.

Cartesian Tree

Arama, Ekleme ve Silme O(logn)

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.

B-Tree

Erişim Arama, Ekleme ve Silme O(logn)

Red-Black Tree

Binary Search Tree(BST) düğümlerinin değer dışında renk değeride tutarak dengeli bir ağaç olması amaçlanır.

Red-Black Tree

Erişim Arama, Ekleme ve Silme O(logn)

Splay Tree

Splay Tree

Arama, Ekleme ve Silme O(logn)

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ü örnekte de 2 seviyeli rotation ihtiyacı bulunmaktadır. Balancing +2'dir. Önce sağa rotation, sonrasında da sola rotation işlemi gerçekleştirilir.
AVL Tree

Erişim Arama, Ekleme ve Silme O(logn)

Okumaya Devam Et 😃

Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store