Preface
Im just kinda taking notes and taking the slides from a yt vid so i can maybe remember stuff / copy stuff for later
also to partially increase my typing speed without looking at my keyboard and idk maybe get better at typing given i dont use the standerd asdf jkl; hand position
rather i do shift+awr jop' layout and use alot of range for my index fingers and spread them out its not optimal but this is realy all i need coz im a gamer lmfao
also [] is my ring finger and all numbers are my ring fingers wish i had an ergo keyboard lol
https://www.youtube.com/watch?v=RBSGKlAvoiM&ab_channel=freeCodeCamp.org
Example pagepage, and literal first 6 minutes of the video
Why Data Structures?
- They are essential Ingredients in creeating fast and powerfull algorithms.
- they help to manage and organize data.
- they make code cleaner and easier to understand. (even if it lowers efficiency)
Abstract Data Types VS. Data Structures
Abstract data type
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 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.
Examples
| Abstraction (ADT) |
Implementation (DS) |
| List |
Dinamic Array Linked List |
| Queue |
Linked List based Queue Array based Queue Stack based Queue |
| Map |
Tree Map Hash Map / Hash Table |
| Vehicle |
Golf Cart Bicycle Smart Car |
Complexity Analysis
As programmers, we often find ourselves asking the same two questions over and over again:
- How much time does this algorithm need to finish?
- if it takes the length of the universe to complete its useless
- How much space does this algorithm need for its computation?
- likewise if it takes the entire bit size of internet its also useless
Big-O Notation
yes it's the letter O not the number 0
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.
Ex, looking for the number 7 in a list, and it occurring last. this scenario would include all values in that list, if allocating space per number, you'd allocate the entire list.
n - The size of the input
Complexities ordered in from smallest to largest
| Constant Time: |
O(1) |
| Logarithmic Time: |
O(log(n)) |
| Linear Time: |
O(n) |
| Linearithmic Time: |
O((n)log(n)) |
| Quadratic Time: |
O(n^2) |
| Cubic Time: |
O(n^3) |
| Exponential time: |
O(b^n), b >1 |
| Factorial Time: |
O(n!) |
Big-O Properties
| O(n + c) | = |
O(n) |
| O(cn |
= |
O(n), c > 0 |
*c = constant, n = number
if your constant is large, like 2 billion its likely to have substantial run-time penalties
let f be a function that describes the running time of a particular algorithm for an input of size n:
f(n) = 7log(n)^3 + 15(n)^3 + 15n^2 + 8
this is Quadratic because theres ^3 then ^2 then ^1 or a regular value at the end
O(f(n)) = O(n3)
The folloing run in constant time: O(1)
| a := 1 |
i := 0 |
| b := 2 | While i < 11 do |
| c := a + 5*b |
i = i + 1 |
:= is used to explicitly signal the initialization or assignment of a new value to a variable. and is usually used for pseudo code
The Following runs in Linear time: O(n)
|
|
| f(n) = n O(f(n)) = O(n) |
f(n) = n/3 0(f(n)) = O(n) |