Zac Anger's Blog

Algorithm & Big-O

14 January, 2016

Algorithms and Problem Solving in One Hour or Less.

Why use algorithms? Because they're a structured set of rules to use for calculations of any type, duh. They let you loop over arrays, etc., in a more functional and portable manner.

Common uses: sorting, searching, solving.

Implementations: recursive, logical (which is exact opposite of recursive), prl/distr/etc


recursive binary search:

function recBin(array, target, left, right){  
  if (left > right){  
  return -1  
  }  
  var middle = Math.floor((right + left) / 2)  
  if (array[middle] === target){  
    return middle  
  } else if (array[middle] > key){  
    return recBin(array, target, left, middle -1)  
  } else {  
    return recBin(array, target,  middle + 1, right)  
  }  
}  
// we can make this a node module  
// then we can be all like  
// var findThat = require('req-bin')  
// findThat([7, 15, 98, 234, 4587, 883489384, 34783473443], 4587)  
module.exports = function(array, target){  
  return recBin(array, target, 0, array.length)  
}  

Finally a valid use for that Wolfram API account. Any big O type of stuff I don't understand by reading it, Wolfram can just straight-up graph that.


Asymptotic notations: languages that let us analyse the time it will take to run an algorithm by identifying its behavior, as the size of the algorithm's input increases.

Let's say algorithm is fn f, input is in, and f(n) is the time it takes to run. So with that algorithm f, input size n, you get the time f(n), yes? This means that we can graph this where Y ix the runtime, and x is the input size; points on the graph are the amount of time for that input size.

Big O in maths and Big O in computer science are a wee bit different. If you read the Wikipedia article on Big O, that's the math version; check the Wikipedia article for Time Complexity instead.

Big O n cubed = a Rubik's Cube. That'd be a triply-nested for loop.

Algorithm that takes an array, iterates over every element in array, and every character of every string in the array: O(n*m)

.sort in JS is (n*m) complexity.

That's linearithmic or (linear logarithmic).

Bucket sorts: we start with an array or whatever, make some buckets. Let's say our array is [1, 4, 3, 7, 7, 9, 6, 2]. Then we make some buckets (let's say ten of them). Just places to put things. Then we go through those buckets, and count how many times those things are in each bucket. So we'd sort our array like this:

1  1    1,  
2  1    2,  
3  1    3,  
4  1    4,  
5         
6  1    6,  
7  2    7, 7,  
8         
9  1    9  
10        

So the output array is [1, 2, 3, 4, 6, 7, 7, 9]. That's chill!

Some samples of sorts! (Of sorts.)

// bubble sort  
var randomArray = function(size){  
  var array = []  
  for(var i = 0; i < size; i++){  
    array.push(parseInt(Math.random() * 100))  
  }  
  return array  
}  
var bubbleSort = function(array){  
  var swapped = true  
  while(swapped){  
    swapped = false  
    for (var i = 0; i < array.length-1; i++){  
      if(array[i] > array[i+1]){  
        swap(i, i+1)  
        swapped = true  
      }  
    }  
  }  
  function swap(a, b){  
    var tmp = array[a]  
    array[a] = array[b]  
    array[b] = tmp  
  }  
}  
// bucket sort  
var bucketSort = function(array){  
  var buckets = []  
  for(var i = 0; i < 100; i++){  
    buckets[i] = 0  
  }  
  for (var i = 0; i < array.length; i++){  
    buckets[number]++  
  }  
  var currentIndex = 0  
  for(var number = 0; number < buckets.length; number++){  
    var count = buckets[number]  
    for (var j = 0; j < count; j ++){  
      array[currentIndex] = number  
      currentIndex++  
    }  
  }  
  return array  
}  
// let's see how they perform...  
var array = randomArray(5000)  
// console.log(array)  
console.time('bubbleSort')  
// console.log('\n#########################################\n')  
bubbleSort(array)  
console.timeEnd('bubbleSort')  
// console.log('\n#########################################\n')  
bucketSort(array)  
// console.log(array)  
// console.log('\n#########################################\n')  
console.time('bucketSort')  
console.timeEnd('bucketSort')  

And some resources for actually kind of understanding any of this stuff (because I only halfway actually do):

Submit a bug report