Data Structures (DS) 基础

(Updated: )
,

Data structures series link: https://www.youtube.com/playlist?list…

Github source code link: https://github.com/williamfiset/algor…

Abstract data types

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

Big-O (时间复杂度)

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.

Big-O Notation (标记)
Constant (恒定的) Time O(1)
Logarithmic (对数的) Time O(log(n))
Linear (直线的) Time O(n)
Linearithmic Time O(nlog(n))
Quadric (平方) Time O(n^2)
Cubic (次方) Time O(n^3)
Exponential (指数) Time O(b^n), b > 1
Factorial (阶乘) Time O(n!)

Big-O Examples

demo1:

1
2
3
4
5
6
7
8
9
i := 0
While i < n Do
  j :=10
  While j < 3*n Do
  	j = j + 1
  j = 0
  While j < 2*n Do
  	j = j + 1
  i = i + 1

f(n) = n * (3n + 2n) = 5n^2

O(f(n)) = O(n^2)

demo2:

1
2
3
4
5
6
7
8
9
i := 0
While i < 3 * n Do
  j :=10
  While j <= 50 Do
  	j = j + 1
  j = 0
  While j < n*n*n Do
  	j = j + 2
  i = i + 1

f(n) = 3n * (40 + n^3/2) = 3n/40 + 3n^4/2

O(f(n)) = O(n^4)

Link

Data-Structure 参考

Data-Structure-And-Algorithm 参考