Level 43
Level 44

2.3.1 - Algorithms


39 words 0 ignored

Ready to learn       Ready to review

Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

All None

Ignore?
time complexity
how much time an algorithm needs to solve a particular problem, so that it can be compared to other algorithms
permutation
the number of ways of arranging the objects in a set of objects
constant time
O(1) describes an algorithm that takes the same amount of time to execute regardless of the size of the input data set
linear time
O(n) describes an algorithm whose performance will grow in direct proportion to the size of the data set
polynomial time
O(n^2) describes an algorithm whose performance is directly proportional to the square of the size of the data set
exponential time
O(2^n) describes an algorithm where the time to execute will double with every additional item in the data set
logarithmic time
O(log n) describes an algorithm where the time to execute it will grow very slowly as the size of the data set increases
O(n!)
Big-O notation for an algorithm that grows in exponential time, but even faster than O(2^n), e.g. for finding permutations
space complexity
the measure of the maximum amount of memory that is needed at any one time in an algorithm
linear search
a search algorithm that goes through every data item individually to find the required item, needed for lists that aren't ordered
O(n)
time complexity of a linear search
binary search
a search algorithm that repeatedly divides a list in half until the required item is found or the list is of size one, however the list must be sorted
divide and conquer
binary search is an example of the ... strategy, which is the strategy of halving the amount of work to do with every iteration
O(log n)
time complexity of a binary search (and a binary tree search)
binary tree search
a recursive search algorithm where half of a tree or subtree is eliminated each time its root is examined
bubble sort
a basic sorting algorithm that repeatedly compares pairs of adjacent items and swaps them into the correct order
flag
to optimise the bubble sort, a ... can be set and tested on each pass as to whether any swaps were made, as this can indicate if the list is sorted or not
insertion sort
a sorting algorithm that takes a data item and places it in the correct position and repeats this until there are no unsorted items left
O(n^2)
time complexity of bubble and insertion sorts
sorted
the time complexity of an insertion sort is close to O(n) if the list is almost ...
O(1)
space complexity of bubble and insertion sorts
merge sort
a sorting algorithm that uses a divide and conquer approach by repeatedly sorting sublists and merging them until a single sorted list is formed
O(n)
space complexity of merge sort
one element
in the merge sort algorithm, the list is divided into n sublists, where each sublist contains ...
quick sort
a sorting algorithm that uses a divide and conquer approach by repeatedly using pivots and moving lesser values into one partition and greater values into another until the list is sorted
O(n log n)
time complexity of merge sort and quick sort
O(n^2)
time complexity of quick sort in the worst case scenario
O(log n)
space complexity of quick sort
stack
quick sort uses recursion, meaning it requires memory space for the ... for each recursion
depth-first traversal
the method of traversing a graph by going as far down one route as possible before backtracking and taking the next route
return addresses
a recursive depth-first traversal automatically implements a stack to hold local variables, parameters and ... each time the subroutine is called
breadth-first traversal
the method of traversing a graph by firstly visiting all the neighbours of a node and then all the neighbours of the first node visited and all the neighbours of the second node and so on
queue
a breadth-first traversal is iterative and uses a ... to keep track of nodes that still need to be visited
scheduling jobs
a depth-first search could be used to solve problems like mazes, where it can be represented as a graph, or for ... where certain tasks must be completed before others
web crawlers
a breadth-first search can be used to find the shortest path, for ... and in facebook to represent friends
Dijkstra’s shortest path algorithm
an algorithm with one cost function - the real cost value from the source to a given node and works by finding the shortest path to every node
A* algorithm
a general path-finding algorithm which has two cost functions - the real cost value and the approximate cost from the node to the goal node
goal node
Unlike Dijkstra's algorithm, where the shortest path to every node is found, the A* algorithm has a focus of reaching the ...
GPS navigation systems
Shortest path algorithms are needed for ... and computer networks (such as the internet)