Flashcards

4.3

James John English 7 cards

Cards in this deck (7)

1Breadth firstUseful for finding shortest distance path in an unweighted graph
2Depth firstUseful for navigating a maze - It will find a route quickly but maybe not the fastest route
3DjikstrasFinds shortest path on a weighted graph
an extension of a breadth first traversal
pathfinding across a mesh network - GPS
4Linear searchStart with first item. Check it. If its not it, move on. Ends when item is found or entire list is checked.
Suitable for unordered lists
Time complexity O(n)
Slow to search big lists
Algorithmically simple
5Binary SearchList must be ordered either alphabetically or numerically. Find midpoint. Determine whether the wanted item is above or below this point. Discard the half we dont need. Repeat. Ends when item is found or all of list is eliminated.
Time complexity of O(log(n)) - double list only 1 more step
Very fast on large data sets
6Binary search treeO(log(n)) and can be used on unsorted data
Data is entered into a binary tree
data is compared to the root and then placed in the left or right subtree.
This is done recursively until all data is in the tree.
7Time complexityLinear - O(n)
Binary - O(log(n))
Bubble - O(n^2)
Merge - O(nlog(n))