Current Size:
Chakra BreakPoints
base0px
sm480px
md768px
lg992px
xl1280px
2xl1536px
Current Height:Width
widthpx
heightpx

Subjects

Algorithms

Date Created: 2021/03/15

Last Update: 2023/08/04

#algorithms #notes

What is an algorithms

A set of steps, instructions or actions to solve rigorously understood(defined) problem.

  • the steps of an algorithm needs to be in a specific order
  • steps need to be distinct
  • produce a result
  • should complete(complete in a finite amount of time)

General Generic Definitions

  • algorithms must have a clear problem statement
    • problem must be rigorously defined
    • clear input
    • clear output
  • specific set up instruction in a specific order
  • each step is unique(distinct)
    • each step is atomic and cannot be broken down into subtasks
  • algorithm must produce a result
  • the algorithm must complete

What is a "good" algorithms

there is no single way

  • correctness
  • efficiency

Correctness

  • clear input
  • clear output
  • will end

Efficiency

Algorithm efficiency is defined by two metrics time and space complexity

We analyze the worst case because it can never perform worst than the worst case

Time complexity : home long it takes to complete a job : in computer science, this is defined as run time

Space complexity : the amount of computer memory an algorithm takes

  • binary search
  • efficiency if the set is sequential and ordered
  • linear search
  • linear search maintains it's complexity regardless if the set is ordered

Correctness

  • input: ordered list of values
  • output: position of the target value

Efficiency

Common Search Algorithms

  • linear/sequential/simple search
  • binary search
  • bubble sort
  • heap sort
  • quick sort
  • insertion sort
  • selection sort
  • merge sort
  • pancake sort
  • permutation sort
  • cocktail sort
  • combo sort
  • counting sort
  • gnome sort
  • bead sort
  • radix sort
  • shell sort
  • sleep sort
  • strand sort

Value of Algorithms

  • compressing data
  • sorting
  • generating random numbers

Measuring Performance Between Algorithms

Big O Notation

Why we need Big O notation What is Big O notation time complexity and space complexity

For a given programming problem how do we know which solution is best?

Big O notation gives us a numeric performance benchmark for

function addUpTo(n){
let total = 0;
for (let i = 0; i <=0; i++ ){
total += i;
}
return total;
}
function addUpTo(n){
return n * (n + 1 ) /2
}

Methods for measuring performance

function addUpTo(n){
let total = 0;
for (let i = 0; i <=0; i++ ){
total += i;
}
return total;
}
let t1 = performance.now()
addUpTo(1000000)
let t2 = performance.now()
console.log(`Run time: ${(t2-t1)/ 1000} seconds`)

Manually timing is difficult to performance benchmark. Different machines and what processes are running will have performance results. For high-performance algorithms, the time difference may be so small that our timing measurements do not measure it.

Methods for Measuring Performance

Counting time

Counting the number of simple operations the computer has to perform

Big O : Formally talk about how the runtime of an algorithm grows as the input grows. : Big O notation is a way to formalize fuzzy counting. : We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases

Big O notions

linear time: O(n) Constant Time: O(1) Quadratic time: O(n^2) $O(n^2)$ Cubic Time: O(n^3) or $O(n^3)$

  • $f(n)$ could be linear $(f(n) = n)$
  • $f(n)$ could be quadratic $(f(n) = n^2)$
  • $f(n)$ could be constant $(f(n) = 1)$
  • $f(n)$ could be something entirely different

Common Algorithms

Robin Karp Algorithm

Reference

Courses

  • Algorithm Patterns in JavaScript

Tools

More Notes

All Notes
HomeProjects

Links

Home Articles Notes Projects About Style Guide Site Credits

Contact

 [email protected]

Location

🌎 Earth