Week 02 → Day 006 → Monday → August 14, 2017
Index
Code Challenge #5 removeDuplicates.js
Code Challenge #4 callBackPractice.js Review
Lecture ⋰ Linear Time O(n) Complexity ⋰ Constant Time O(1) Complexity ⋰ Quadratic Time O(n²) Complexity ⋰ Linked Lists ⋰ Stacks ⋰ Queues ⋰ Hash Tables ⋰ Hash Function Examples ⋰ Hash Table Insertion ⋰ Hash Table Collisions
Resources
10 Common Data Structures Explained with Videos + Exercises – https://medium.freecodecamp.org/10-common-data-structures-explained-with-videos-exercises-aaff6c06fb2b
Data Structure Visualizations – https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Computer Science Animated Slides – http://www.csanimated.com/browse.php
A Beginners Guide to Big O Notation – https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
Big O Cheat Sheet – http://bigocheatsheet.com/
Time Complexities
Linear Time O(n) Complexity
O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of theforloop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
bool ContainsValue(IList<string> elements, string value)
{
foreach (var element in elements)
{
if (element == value) return true;
}
return false;
}
const search = (array, element) => {
for (let i = 0; i < array.length; i++) {
if (array[i] === element) {
return array[i];
}
}
return null;
}
Constant Time O(1) Complexity
O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
const capitalizeFirstLetter = (string) => {
return string[0].toUpperCase() + string.split(1);
};
Other examples of 0(1) Complexity:
- myArray[0]
- myObject[key]
Quadratic Time O(n²) Complexity
O(N²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴) etc.
const containsDuplicates = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
// Don't compare with self
if (i === j) continue;
if (array[i] === array[j]) return true;
}
}
return false;
};
O(²N)
O(²N) denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(²N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(²N) function is the recursive calculation of Fibonacci numbers:
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
Data Structures
Linked Lists
A linked list is a linear collection of data elements, called nodes, each of which points to the next. Each node in a linked list contains two key pieces of information: the element itself, and a reference to the next node.
const node = {
element: value,
next: next
}
Linked list time complexity
╔═══════════╦═════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬═════════╬════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════╩════════════╝
Doubly Linked List
There are also doubly linked lists where each node has a pointer to both the next item and the previous item in the list.
const node = {
element: value,
next: next
previous: previous
}
Stacks
A stack is a basic data structure where you can only insert or delete items at the top of the stack. It is kind of similar to a stack of books. If you want to look at a book in the middle of the stack you must take all of the books above it off first.
The stack is considered LIFO (Last In First Out) — meaning the last item you put in the stack is the first item that comes out of the stack:
There are three main operations that can be performed on stacks: inserting an item into a stack (called ‘push’), deleting an item from the stack (called ‘pop’), and displaying the contents of the stack (sometimes called ‘pip’).
Stack time complexity
╔═══════════╦═════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬═════════╬════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════╩════════════╝
Queues
You can think of a queue as a line of people at a grocery store. The first one in the line is the first one to be served. Just like a queue.
A queue is considered FIFO (First In First Out) to demonstrate the way it accesses data. This means that once a new element is added, all elements that were added before have to be removed before the new element can be removed.
A queue has just two main operations: enqueue and dequeue. Enqueue means to insert an item into the back of the queue and dequeue means removing the front item.
Queue time complexity
╔═══════════╦═════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬═════════╬════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════╩════════════╝
Hash Tables
A hash table is a map data structure that contains key / value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
The hash function usually takes a string as input and it outputs an numerical value. The hash function should always give the same output number for the same input. When two inputs hash to the same numerical output, this is called a collision. The goal is to have few collisions.
So when you input a key / value pair into a hash table, the key is run through the hash function and turned into a number. This numerical value is then used as the actual key that the value is stored by. When you try to access the same key again, the hashing function will process the key and return the same numerical result. The number will then be used to look up the associated value. This provides very efficient O(1) lookup time on average.
Hash table time complexity
╔═══════════╦═════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬═════════╬════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(1) ║ O(n) ║
║ Insert ║ O(1) ║ O(n) ║
║ Delete ║ O(1) ║ O(n) ║
╚═══════════╩═════════╩════════════╝
Hash Function Examples
The hash function usually takes a string as input and it outputs an numerical value. The hash function should always give the same output number for the same input.
var hash = (string, max) => {
var hash = 0;
for (var i = 0; i < string.length; i++) {
hash += string.charCodeAt(i);
}
return hash % max;
};
Hash Table Insertion
Hash Table Collisions
When two inputs hash to the same numerical output, this is called a collision. The goal is to have few collisions.