Algorithms Flashcards
What is linear search?
In linear search, the idea of the algorithm is to iterate across the array from left to right, searching for a specified element.
In pseudocode:
*Repeat, starting at the first element:
* If the first element is what you’re looking for (the target), stop.
*Otherwise, move to the next element.
What is big O notation
Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm. Big O Notation in Data Structure describes the upper bound of an algorithm’s runtime
It helps programmers calculate the scalability of an algorithm or count how many steps it must execute to give output based on data the program works on
What is the runtime complexity of linear search?
Runtime Complexity for Linear Search = O(n)
It’s, as the name says, linear
one extra ‘item’ adds one extra ‘unit of time’
What is binary search?
the idea of the algorithm is to divide and conquer, reducing the search area by half each time, trying to find a target number.
What is needed to do binary search?
In order to leverage the power of binary search, our array must first be sorted, else we cannot make assumptions about the array’s contents.
What is the pseudocode of Binary search
Repeat until the (sub)array is of size 0:
*Calculate the middle point of the current (sub)array.
*If the target is at the middle, stop.
*Otherwise, if the target is less than what’s at the middle, repeat,
changing the end point to be just to the left of the middle.
*Otherwise, if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle.
What is the runtime complexity of binary search?
Runtime Complexity for binary = O(log n)
this means: for every item added the number of operations grows very slowly.
log(n) is 2^N = value (N = the power is needed to reach that value
Name 3 ways to sort an array
Selection sort, Bubble sort, Merge sort
What is Bubble sort?
In bubble sort, the idea of the algorithm is to move higher valued elements generally towards the right and lower value elements generally towards the left.
What is de pseudocode of Bubble Sort
*Set swap counter to a non-zero value
*Repeat until the swap counter is 0:
* Reset swap counter to 0
* Look at each adjacent pair
* If two adjacent elements are not in order, swap them and
add one to the swap counter
Worst case scenario when using bubble sort?
The array is in reverse order; we have to “bubble” each of the n-elements all the way across the array, and since we can only fully bubble one element into position per pass, we must do this n times.
Best case scenario when using bubble sort?
The array is already perfectly sorted, and we make no swaps on the first pass.
What is the runtime complexity of bubble sort?
Runtime Complexity for bubble sort = O(N²)
Best case is O(n) = when array is already sorted
What is selection sort?
In selection sort, the idea of the algorithm is to find the smallest unsorted element and add it to the end of the sorted list.
What is de Pseudocode of selection sort
*Repeat until no unsorted elements remain:
*Search the unsorted part of the data to find the smallest value
*Swap the smallest found value with the first element of the unsorted part
What is the runtime complexity of selection sort?
Runtime Complexity for selection sort = O(N²)
Runtime for best- and worse case are exactly same because you need to check every item for each item
What is merge sort?
In merge sort, the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order.
What is merge sort in Pseudocode?
*Sort the left half of the array (assuming n> 1)
*Sort the right half of the array (assuming n> 1)
*Merge the two halves together
What is the runtime complexity of merge sort?
Runtime Complexity for selection sort =O(n log n)
Worst-case scenario: We have to split n elements up and then recombine them, effectively doubling the sorted subarrays as we build them up. (combining sorted 1-element arrays into 2-element arrays, combining sorted 2-element arrays into 4-element arrays…)
What is recursion?
*We might describe an implementation of an algorithm as being particularly “elegant” if it solves a problem in a way that is both interesting and easy to visualize.
*The technique of recursionis a very common way to implement such an “elegant” solution.
*The definition of a recursive function is one that, as part of its execution, invokes itself.
