Algoritma Karmaşıklığı Big-O
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.
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.
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.
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.
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.
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.
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 .
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.
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.
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.
Erişim Arama, Ekleme ve Silme O(logn)
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.
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.
