Algorithms Flashcards
ideal algorithm
will run quickly and take up as little space(memory) as possible.
Time complexity
How much time they need to solve a given problem
Space complexity
The amount of resources e.g. memory they require
Permutation
number of ways we can arrange a set of data - factorial e.g. 4! = 4x3x2x1
Constant
y = 3
Linear
y = 3x
Logarithmic (Big O + graph)
y = log(x)
O(logn)
Polynomial
y = x^2
Exponential graph
y = x^3
How to write Big O
Notation always assumes the worst case scenario,
1. remove all terms except the one with the largest factor
2. Remove any constants
e.g. 3n is expressed as O(n), this is a linear complexity that grows by ‘n’ number of times
Constant complexity
O(1)
Always executes in the same time regardless of the size of the data set - most efficient. Time is independent of input
e.g. Determining if a number is odd or even
Logarithmic complexity
O(log n)
Halves the data in each pass. Opposite to exponential and efficient with large data sets - efficient
e.g. Binary search
Linear Logarithmic -
Merge sort = O(n log n)
Linear complexity
O(n)
Performance is proportional to the size of the data set and declines as the data set grows. - medium efficiency
In the worst case scenario it must go through each item once
e.g. Linear search
Polynomial complexity
O(n^2)
Performance is proportional to the square of the size of the data set. - inefficient
A loop inside a loop
e.g. Bubble sort
Exponential complexity
O(2^n)
Doubles with each addition to the data set in each pass, opposite to logarithmic - very inefficient
Intractable
e.g. recursively calculating Fibonacci numbers
Constant Time
Time remains constant even when the number of output increases
Logarithmic Time
Time will grow as the size of the input increases
Linear Time
Time will be linear to the size of the input
Polynomial Time
Time will grow proportionally to the square of the size of the data set
Exponential Time
Time will be as the power of the number of inputs, grows very quick
Factorial Time O(n!)
Time will grow even quicker as data is input, very inefficient
Tractable problems
efficient, have a polynomial or less time solution e.g. O(1). O(n), O(log n), O(n^2)
Intractable problems
inefficient, any problems that can be theoretically solved but take longer than polynomial time e.g. O(n!), O(2^n)
Heuristic algorithms
used to provide approximate but not exact solutions.
Unsolvable problems
can never be solved algorithmically, an example is demonstrated by the Halting problem
Graph Traversal
Is the process of visiting each vertex in a graph. You can use both depth-first and breadth first
Depth First Graph Traversal
a branch is fully explored before backtracking. Uses a stack
Breadth First Graph Traversal
a layer is fully explored before venturing on to the next node. Uses a queue
Pre-Order Tree Traversal
Drawing a dot on the left of the nodes, used for prefix notation and copying a tree
Post-Order Tree Traversal
Drawing a dot on the right of the nodes, used for reverse polish notation
In Order Tree Traversal
Drawing a dot underneath the nodes and follow around the nodes – Used for binary tree search and outputting values in ascending order
How to represent a tree data structure?
- An array that contains values at the nodes
- An array that points to the location of the left child of the node in the values array
- An array that points to the location of the right child of the node in the values array
Reverse Polish Notation
Humans prefer in-fix order notation, this is where operand is either side of the opcode. However RPN creates a postfix equivalent
e.g. infix 3 + 5
Postfix/RPN 35+
Both give the answer 8
Evaluate the postfix equation 963/+ (Use a stack)
963/+
63/= 6/3 = 2
92+
= 11
Operand is pushed onto the stack, whilst opcode causes two items to be popped off the stack with the result of the operation pushed back onto the stack.
RPN uses/benefits
RPN can be executed on a stack, as a result, RPN is ideal for interpreters which are based on a stack e.g. Bytecode and PostScript
RPN is non ambiguous and therefore easier for computers to read
Linear Search Operations?
- Compare every search item against every item in the list one-by-one.
- Starts at the beginning and keeps going until the search item is found
- Returns the position of where it is found
- If the item is not in the list, it will return a suitable message indicating it is not in the list, should not error
Big O for time complexity for Linear Search?
Big O = O(N)
Linear search is slow when compared with other search algorithms
What can Linear Search be conducted on?
any unordered list
How can you determine the maxiumum number of searches a binary list performs?
Divide by 2 until you reach 1 or lower, the number of times divded is the max number of searches#
(or can use log)
What can Binary Search be conducted on?
any ordered list
Binary Search Operations?
- works by looking at the midpoint of the list and determining if the target is higher or lower than the midpoint
- If when calculating the midpoint it is decimal, the decimal is removed e.g. 2.6 → 2
- The list is then halved
Big O time complexity for Binary Search?
O(logN)
Linear Search Advantages and Disadvantages
Advantages;
-Simple and easy to implement
-No sorting required
-Good for short lists
Disadvantages;
-Slow because it searches through the whole list
-Inefficient for long lists
Binary Search Advantages and Disadvantages?
Advantages;
-Much quicker, halving the search zone
Disadvantages;
-Items of the list need to be placed in order
What kind of algorithm is bubble sort?
Sorting
What is the purpose of a Bubble Sort?
The purpose of bubble sort is to order an unordered list, this can be alphabetically or by number.
Bubble Sort: Order of Operations
- Bubble sort steps through a list and compares pairs of adjacent numbers
- The numbers are swapped if they are in the wrong order. e.g. ascending or descending.
- The algorithm repeatedly passes through the list until no more swaps are needed
- Going through the list once is considered 1 pass
Bubble sort advantages and disadvantages
Advantages : Very simple to code and robust
Disadvantages : Slow, inefficient, especially for long lists
What is the maximum number of comparisons a bubble sort can make?
for n items n(n−1)/2
What is a merge sort?
Merge sort is a recursive function that calls itself. It is a divide and conquer algorithm
Merge Sort: Order of Operations
- Divides unsorted lists into sublists, until there is one item in each list
- it then combines pairs of sublists into ordered lists,
- Continues until only one ordered list remains
Merge Sort vs Bubble Sort
Merge sort;
- Much faster than bubble sort especially when the number of elements is large O(n log n)
- More Complex to code and understand
Bubble sort;
- Much slower than merge sort especially when the number of elements is large O(n^2)
- Easy to code and understand
what is Dijkstra
Dijkstra’s shortest path optimisation algorithm finds the shortest path between nodes/vertices in a graph
Dijkstra: Order of operations
- Selects the unvisited node with the shortest path
- Calculates the distance to each unvisited neighbour
- Updates the distance of each unvisited neighbour if smaller
- Once all neighbours have been visited mark node as visited
Uses for Dijkstra’s algorithm?
Applications of DA is heavily used in computer systems that need to calculate shortest paths:
- satellite navigation systems to display shortest or fastest route
- Routers in networks to find shortest path when routing packets within networks
