Algorithms Flashcards
What is an algorithm?
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.
How is Algorithm efficiency typically measured?
Algorithm efficiency is typically measured by the algorithm’s computational complexity.
What is Computational complexity?
Computational complexity is the amount of resources used by the algorithm.
What is runtime complexity?
An algorithm’s runtime complexity is a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.
What is an algorithm’s worst case?
An algorithm’s worst case is the scenario where the algorithm does the maximum possible number of operations.
What is an algorithm’s best case?
An algorithm’s best case is the scenario where the algorithm does the minimum possible number of operations.
Describe what a Linear search algorithm does.
Linear search is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.
What is algorithm runtime?
An algorithm’s runtime is the time the algorithm takes to execute.
What is Big O notation?
Big O notation is a mathematical way of describing how a function (running time, or runtime, of an algorithm) behaves in relation to the input size.
What is the worst-case runtime?
The worst-case runtime of an algorithm is the runtime complexity for an input that results in the longest execution.
What is the selection sort algorithm?
Selection sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
What is the Insertion sort algorithm?
Insertion sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.
What is the Quicksort algorithm?
Quicksort is a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts.
What is the Merge sort algorithm?
Merge sort is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list.
What is Shell sort algorithm?
Shell sort is a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm.
What is radix sort algorithm?
The radix sort algorithm sorts a list of integers by grouping elements based on the element’s digits, starting with the least significant digit and ending with the most significant.
What is a heuristic?
Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.
What is a self-adjusting heuristic algorithm?
A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used.
What is a greedy algorithm?
A greedy algorithm is an algorithm that, when presented with a list of options, chooses the option that is optimal at that point in time.
