Search data structure: Difference between revisions

Revision as of 14:35, 16 March 2011

Revision as of 21:31, 28 June 2011

Line 50:

| O(''n'')

|-

| [[Sorted array]]

| O(''n'')

| O(''n'')

Line 80:

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

| O(log ''n'')

| O(log ''n'')^†**

| O(''n'')

| O(1)

Line 91:

| O(''n'')

| O(''n'')

|}

|}<small>&nbsp;† The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>

<small>&nbsp;* 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.</small>

|}<small>&nbsp;†** The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>

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.