Karteikarten
Computer Science Paper 2 - Algorithms
Karten in diesem Stapel (14)
- 1Big O Notation is......a method of analysing algorithms. It determines how the run-time and memory requirements of algorithms scales as the size of it's input does.
- 2O(1)Constant time. Algorithm will always take the same time or memory to complete.
- 3O(logn)Logarithmic time. Inverse of exponential. Works by discarding input deemed as irrelevant.
- 4O(n)Linear time. Algorithm scales directly with input size.
- 5O(nc)Polynomial. Scales depending on a mathematical function power-of function to the set. Quadratic time is most common example.
- 6O(cn)Exponential. Type of power-of scaling but n is used as the power. Much worse than polynomial.
- 7O(n!)Factorial.
- 8A Linear Search is......a simple search that looks for a certain item and returns the index of the item within an array or list. It can be used on unsorted lists, checking one by one and returning -1 if not found. Inefficient for larger lists.
- 9A Binary Search is......a search that uses the divide and conquer methodology to search SORTED lists. Finds mid point of data set, then determines if it is higher than or less than - discarding half the data from there. Uses three pointers (low, mid, high) and is much faster for larger lists than linear search, but needs to be sorted.
- 10A Bubble Sort is......a method of sorting lists in which items are compared in size to the item on their right, swapping if needed. A variable stores whether there are any swaps in a pass, and the sort ends when none are made. It is slow, and rarely used as it's only advantage is it's ease of implementation.
- 11An Insertion Sort is......a method of sorting lists in which the array is looped through from left to right. For each index, it loops back to compare the values, shunting indexes to the right until the correct place is found. One loop through is enough to sort the data set, and it is faster than bubble sorts.
- 12A Merge Sort is......a method of sorting lists that uses recursion and a divide and conquer approach. The array is divided in half until each subset is exactly one in length. Then, a merge algorithm is used to recombine each subset, sorting them as it goes. Merge Sorts are significantly faster at sorting through large arrays than Insertion Sorts or Bubble Sorts, though the space complexity is higher.
- 13A Quick Sort is......a divide and conquer and recursive algorithm. A pivot point is decided upon, with all elements less than the pivot being put into a partition, and the others into a another. Each partition is quick sorted recursively until partitions are exactly size one. Time and space complexity are good.
- 14Steps of Djikstra's Algorithm? (Hint: There are 4)
Informationen
- Beschreibung
- Karteikarten am Computer Science Paper 2 - Algorithms, erstellt von Haydn Warne am 13/02/2018.
- Erstellt von
- Haydn Warne
- Aufrufe
- 0
- Bewertung