Data structures series link: https://www.youtube.com/playlist?list…
Github source code link: https://github.com/williamfiset/algor…
Data Structures (DS) is a way of organizing data so that it can be used effectively.
Why Data Structures?
They are essential (基本要素) ingredients (因素) in creating fast and powerful algorithms.
They help to manage and organize data.
They make code cleaner and easier to understand.
Abstract (理论) Data Type (ADT)
An abstract data type (ADT) is an abstraction of a data structure which provides only the interface to which a data structure must adhere (遵守) to.
The interface does not give any specific (具体的) details about how something should be implemented (工具) or in what programming language.
|Abstraction (ADT)||Implementation (实施) (DS)|
|List||Dynamic Array or Linked List|
|queue (队列)||Linked List based Queue or Array based Queue or Stack based Queue|
|Map||Tree Map or Hash Map / Hash Table|
|Vehicle (工具\交通工具)||Golf Cart or Bicycle or Smart Car|
Complexity Analysis: time and space in my program.
Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify (量化) performance as the input size becomes arbitrarily (武断地) large.
|Constant (恒定的) Time||O(1)|
|Logarithmic (对数的) Time||O(log(n))|
|Linear (直线的) Time||O(n)|
|Quadric (平方) Time||O(n^2)|
|Cubic (次方) Time||O(n^3)|
|Exponential (指数) Time||O(b^n), b > 1|
|Factorial (阶乘) Time||O(n!)|
i := 0
f(n) = n * (3n + 2n) = 5n^2
O(f(n)) = O(n^2)
i := 0
f(n) = 3n * (40 + n^3/2) = 3n/40 + 3n^4/2
O(f(n)) = O(n^4)