- algorithm: unambiguous set of instructions used to achieve a specific goal
- best case time complexity: O(n)
- cost function: the weight of the current path plus the total weight of the path so far (real distance)
- Euclidean distance: straight line distance
- f(x): the total cost = g(x) + h(x)
- g(x): the real distance cost function
- h(x): the heuristic function
- heuristic: rule of thumb, best guess or estimate that helps the algorithm accurately approximate the shortest path to each node
- heuristic function: approximate the Euclidean distance i.e. the straight line distance from the current node to the goal node
- pass: compares pairs of elements and swaps them if they are out of order
- space complexity: measurement of memory
- time complexity: measurement of time for an algorithm to complete
- total cost f(x): g(x) + h(x)
- worst case time complexity: O(n2)
- divide and conquer: algorithm that reduces the size of the problem into smaller problems that are more easily solvable
- sub lists: the divided smaller lists in merge sort
- pointer: keeps track of which elements are to be compared in merging
- stack frame: represents a single function call on the call stack
- stack: data structure for recursive calls in merge sort
- base case: when sub list contains one element, stopping recursion
- call stack: stack where recursive calls are added
- recursion: technique where function calls itself repeatedly
- slicing: technique to split lists in Python using [start:end]
- optimisation algorithm: algorithm that calculates the shortest path from a starting location to all other locations
- weighted graph: graph where edges carry weighted values representing measurements like time, distance or cost
- node/vertex: a point in the graph
- arc/edge: connection between nodes
- optimisation problem: problem that involves maximising the efficiency of a solution
- priority queue: data structure used to order nodes by distance, prioritizing shortest routes
- visited list: list of nodes that have been removed from the queue and visited
- exhaustive: checking every available option
- dictionary: data structure composed of key and value pairings
- complexity: measure of efficiency of an algorithm
- scalability: how algorithm performance changes with input size
- constant time: O(1), executes same instructions regardless of input data size
- linear time: O(n), instructions grow proportionally to input size
- polynomial time: O(n^k) for k>1, performance proportional to power of input size
- exponential time: O(2^n), time doubles with each additional input value
- logarithmic time: O(logn), very little time increase as input size grows
- best case: most efficient scenario for algorithm performance
- average case: typical performance, neither best nor worst
- worst case: least efficient scenario for algorithm performance
- dominant factor: term contributing most to time complexity as input size increases
- iteration: use of for or while loops for repeating operations
- searching algorithm: a method to find a specific value or element within a data structure.
- linear search: a standard algorithm used to find elements in an unordered list.
- binary search: a more efficient search method than linear search.
- insertion sort: sorts one item at a time by placing it in the correct position of an unsorted list.
- quick sort: an example of a divide and conquer algorithm that reduces the size of the problem into smaller problems that are more easily solvable by an algorithm.