The concept of progressive time complexity ：
If there is a function f（n）, Properly n Approaching infinity ,T（n）/ f（n） The limit value of is a constant not equal to zero , said f（n） yes T（n） Functions of the same order of magnitude of . Write it down as T（n）= O（f（n））, call O（f（n）） Is the incremental time complexity of the algorithm , Time complexity . Progressive time complexity in uppercase O To express , So it's also called big O notation .
Time complexity derivation principle ：
- If the run time is constant , With constant 1 Express .
- Only the highest order term in the time function .
- If the highest order term exists , Then the coefficient before the highest order term is omitted .
- add(E e) Method inserts... Directly at the end of the array , The time complexity is O(1)
- add(int index, E element) Method to specify index insertion , There will be data movement , The time complexity is O(n)
- get(int index) According to the index of the array , Time complexity O(1)
- remove(int index) After deleting , There will be movement of data , Time complexity O(n)
- add(E e) The tail interpolation , The time complexity is O(1)
- add(int index, E element) Insert... At the specified location , Need to loop to get the insertion position , Time complexity O(n)
- get(int index) Get the specified location node , Order traversal list , The time complexity is O(n)
- remove() Delete header node , Time complexity O(1)
- add(E e) The bottom is HashMap Of put(K key, V value) Method ,JDK1.8 Red black tree introduced , When hash The length of the list of nodes in the table reaches the treeling threshold 8 when , It will turn into a red black tree , The insertion time complexity is O(logn).
As long as the red and black trees are introduced , Insert 、 Delete 、 When looking for , The time complexity becomes O(logn).
The bottom layer is TreeMap, Use red black tree to achieve , The time complexity of insert delete search is O(logn).
LinkedHashSet Inherited from LinkedHashSet, At the bottom LinkedHashMap, and LinkedHashMap Inherited from HashMap, So time complexity analysis and HashMap identical .
Three common implementation classes HashMap,TreeMap,LinkedHashMap, Red and black trees have been introduced into the ground floor , The time complexity is also related to the red and black trees , Insert 、 Delete 、 Search for O(logn).
A set of pictures understand “ Time complexity ”
JAVA Set time complexity
Red and black trees ( One ) And The principle and algorithm are introduced in detail