- 2021-03-09 21:15
*views 3*- Algorithm and data structure
- algorith
- Linked list
- # data structure
- queue
- data structure
- Binary tree

<> Basic data structure

1. Time complexity

Data structure search by index search by keyword insert delete

array (Array)O(1)O(n)O(n)O(n)

queue (queue)O(n)O(n)O(1)O(1)

Linked list (Linked list)O(n)O(n)O(1)O(1)

Binary tree (Binary Search Tree) Average O(log(n))O(log(n))O(log(n))

Binary tree (Binary Search Tree) worst O(n)O(n)O(n))

2. Spatial complexity

Data structure array queue list Binary Tree

Spatial complexity O(1)O(1)O(1)O(1)

<> Advanced data structure

What problems can be solved by the time complexity of data structure operation

heap (Heap)O(log(n)): push, pop; O(1):top Global dynamic search for maximum and minimum height

Hashtable (Hash table)O(1）: insert, find, delete Does the query element exist ,key-value Query question level

trie (Trip)O(1): insert, find, delete It's similar to hashing , Does the query element exist ,key-value Query questions

And check the collection (UnionFind)O(1): union, find Dynamically merge sets and determine whether two elements are in the same set

Balanced sort binary tree (Balanced BST)O(log(n)): insert, find, delete, max, min, lower, upper

Add, delete, check and modify dynamically, and support finding global maximum and minimum ; It can be used to find the minimum value larger than a certain number and the maximum value smaller than a certain number （ As close as possible ） Low high

Jump table (Skip List)O(log(n)): insert, find, delete, max, min, lower, upper and Balanced

BST The problem is the same , And can always maintain an ordered list low high

Tree array (Binary Indexed Tree)O(log(n)): insert, delete, range, sum At the same time of addition, deletion and modification , Solving the problem of interval summation

Segment tree (Segment Tree)O(log(n)): insert, find, delete, range max, range min, range

sum, lower, upper; O(1):global max, global min At the same time of addition, deletion and modification , Solving interval evaluation problem , max, min, sum

And so on can completely replace the low middle

2. Spatial complexity

Data structure heap hash table prefix tree and lookup set balanced sort binary tree jump table tree array segment tree

Spatial complexity O(1)O(1)O(1)O(1)O(1)O(1)O(log(n))O(1)

Technology

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

The problem of string left rotation Interview essential ： Data structure time complexity and usage Remove outliers , use python to write matlab Of hampel(X) function BN layer pytorch realization Linux C Three methods of redirecting standard input and output to file [ Thesis reading ]HRNetV1,HRNetV2,HRNetV2p2021 World ranking of Computer Science Major ! This year's ranking reshuffle What certificates can big data test ? use Python and Pygame Implementation of code rain 2020 The 11th National Blue Bridge Cup B group C/C++