Farklı veri yapıları ve karmaşıklıkları

Question

Farklı veri yapılarına sahip olan bu wiki link'u biliyorum.

Karmaşık bir tablo biçiminde (başvuru için) karmaşıklıkları (ekleme, silme, güncelleştirme vb.) Alabileceğim bir yer olup olmadığını bilmek istiyorum.

Answer 1

Sorunuzda bağlantı kurduğunuz sayfanın birçok veri yapısı vardır. Her biri belirli veri yapılarını detaylandıran bir sayfa. Hazırlanmış bir formatta karşılaştırma tablolarını istediğinizi biliyorum, ancak mevcut olmadığı için, çeşitli sayfalarda gezinerek kolayca bir araya getirebileceğiniz bir şey olabilir. Örneğin dizideki çeşitli algoritmaların karşılaştırması here ve b-ağacı here için verilir. Bu yüzden hepsini basit bir referans olarak derlemek için biraz iş gerektirebilir. Hmmm ... belki de yapımında bir blog yazısı var.

Answer 2

İşte Wikipedia'da: Ben kaçmak istedim tam olarak ne var Worst-case analysis of data structures

+----------------------+----------+------------+----------+--------------+ 
|      | Insert | Delete | Search | Space Usage | 
+----------------------+----------+------------+----------+--------------+ 
| Unsorted array  | O(1)  | O(1)  | O(n)  | O(n)   | 
| Value-indexed array | O(1)  | O(1)  | O(1)  | O(n)   | 
| Sorted array   | O(n)  | O(n)  | O(log n) | O(n)   | 
| Unsorted linked list | O(1)* | O(1)*  | O(n)  | O(n)   | 
| Sorted linked list | O(n)* | O(1)*  | O(n)  | O(n)   | 
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n)   | 
| Heap     | O(log n) | O(log n)** | O(n)  | O(n)   | 
| Hash table   | O(1)  | O(1)  | O(1)  | O(n)   | 
+----------------------+----------+------------+----------+--------------+ 

* The cost to add or delete an element into a known location in the list 
    (i.e. if you have an iterator to the location) is O(1). 
    If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.