Search data structure: Difference between revisions

Revision as of 18:43, 7 October 2015

Revision as of 18:55, 7 October 2015

Line 27:

====Asymptotic amortized worst-case analysis====

In this table, the [[asymptotic analysis|asymptotic]] [[big-O notation|notation ''O''(''f''(''n''))]] means "not exceeding some fixed multiple of ''f''(''n'') in the worst case."

{| class="wikitable"

Line 42:

|-

| Unsorted [[Array data structure|array]]

| [[Constant time|''O''(1)]]<br>^{(see&nbsp;note)}

| O(''1O''(1)<br><sup>(see&nbsp;note)

| N/A

| ''O''(1)

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

|-

| [[Sorted array]]

| ''O''(''n'')

| ''O''(''n'')

| N/A

| ''O''(1)

| ''O''(log&nbsp;''n'')

| ''O''(1)

| ''O''(1)

| ''O''(''n'')

|-

| Unsorted [[linked list]]

| ''O''(1)

| ''O''(1)<ref name="listdelete">{{cite book |title=Introduction to Algorithms |publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|quote=LIST-DELETE runs in ''O''(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.}}</ref>

| N/A

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

|-

| Sorted linked list

| ''O''(''n'')

| ''O''(1)<ref name="listdelete" />

| N/A

| ''O''(''n'')

| ''O''(''n'')

| ''O''(1)

| ''O''(1)

| ''O''(''n'')

|-

| [[Self-balancing binary tree]]

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| N/A

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| ''O''(''n'')

|-

| [[Heap (data structure)|Heap]]

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| ''O''(log&nbsp;''n'')

| N/A

| ''O''(''n'')

| ''O''(1)

| ''O''(''n'')

| ''O''(''n'')

|-

| [[Hash table]]

| ''O''(1)

| ''O''(1)

| ''O''(''n'')

| N/A

| ''O''(1)

| ''O''(''n'')

| ''O''(''n'')

| ''O''(''n'')

|-

| [[Trie]]

| ''O''(''m'')

| ''O''(''m'')

| N/A

| ''O''(''n'')

| ''O''(''m'')

| ''O''(''m'')

| ''O''(''m'')

| ''O''(''n'')

|}

''Note'': Insert on an unsorted array is sometimes quoted as being ''O''(''n'') due to the assumption that the element to be inserted must be inserted at one particular ___location of the array, which would require shifting all the subsequent elements by one position. However, in a classic array, the array is used to store arbitrary unsorted elements, and hence the exact position of any given element is of no consequence, and insert is carried out by increasing the array size by 1 and storing the element at the end of the array, which is a O(''1O''(1) operation.<ref name="games">{{cite book|isbn=9781584506638|title=Data Structures and Algorithms for Game Developers|author=Allen Sherrod|publisher=Cengage Learning|year=2007|quote=The insertion of an item into an unordered array does not depend on anything other than placing the new item at the end of the list. This gives the insertion into an unordered array of ''O''(1).}}</ref><ref>{{cite book |title=[[Introduction to Algorithms]]|publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest}}</ref> Likewise, the deletion operation is sometimes quoted as being ''O''(''n'') due to the assumption that subsequent elements must be shifted, but in a classic unsorted array the order is unimportant (though elements are implicitly ordered by insert-time), so deletion can be carried out by swapping the element to be deleted with the last element in the array and then decrementing the array size by 1, which is a O(''1O''(1) operation.<ref>{{cite web|url=http://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array#9358634|title=Algorithm - the time complexity of deletion in a unsorted array|quote=Finding the element with a given value is linear. Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element.}}</ref>

This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.