[DSA] Overview: Complexity Analysis

dsa data structure algorithm complexity

theQuert 2021-03-22 22:27:53 ‧ 1148 瀏覽

Data Structure
How to manipulate data?
Data structure is a way to manipulate, organize data for different applications.
Like we retrieve data through front-end, getting data from database, and see how to present them in the interactive interface (GUI/CLI).
Complexity (Space-Time Complexity)
During coding interview, you may be asked if there is a better solution?
A better solution, we need to consider Space-Time Complexity.

Space Complexity
A measure of how much auxiliary memory an algorithm takes up, space complexity is a central concept in the field of algorithms and in coding interviews.
In Space Complexity, we care about the memory/storage used. The less memory used, the better space complexity we get.
It's expressed using Big O notation.
Time Complexity
A measure of how fast an algorithm runs, time complexity is a central concept in the field of algorithms and in coding interviews.
In Time Complexity, we care about the Time of the algorithm takes.
The less time it spends, the better Time Complexity we get.
It's expressed using Big O notation

Caution
Each algorithms have different Space-Time Complexity, we cannot both get the best Space Complexity and Time Complexity at the same time.
Thus, when solving different problems, we have to consider Space-Time Complexity before choosing the data structure to tackle.
Time Complexity