Algorithms Flashcards
What does Dijksta’s Algorithm do?
This method takes a lot of computing time but it will always calculate the fastest route
You first visit the starting Node,
You update the cost for each surrounding node,
You mark the current node as visited,
You visit the next smallest node
You keep doing this until you have reached your final destination
What is the A * Star Version do?
This method is more efficient, however it is not guaranteed to find the fastest route.
You take the halustic cost, which is the estimated cost and add it to the real cost to get the final cost, if the current cost you have for the final path is smaller than other predicted costs then you do not need to bother visiting them.
What is an Array?
Arrays hold multiple elements of data/ data types. So you cannot have a string and an integer in the same array. Data can be added and removed to the array, but the size cannot change. A 2d array is a list within a list.
How does a Stack work?
it Works on first in last out, like a stack of books.
How does a Queue work?
it Works on first in first out, like a queue of people.
What is Binary Search?
It’s a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
What is Linear Search?
it’s a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched
What is Bubble Sort?
It repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list.
What is Insertion Sort?
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
What does Big-O do?
It measures efficiency of program by looking at space and time.
What does O(1) mean?
Constant Time
The program will execute in exactly the same amount of time regardless of the size of the data set
What does O(n) mean?
Linear Time
The value grows directly in proportion to the size of the data set in linear time, in most cases this will be a list.
What do O(n log n) and O(log n) mean?
Logarithmic Time
Execution time grows very slowly as the data set increases. Doubling the size of the data set has little effect on the time to complete
The base is taken to be 2 (changes in the base have little effect for Big O over very large data sets)
Divide and conquer algorithms where the list is halved on each permutation are O(log n)
Works the same as binary sort, overall decreasing time to search for an item depending on the size of the list / data set
What does O(n^2) mean?
n Squared
It is Polynomial time
Grows directly in proportion to the square of the size of the data set. For example where a loop is nested in a loop.
Deeper nested loops may be O(n^3)etc… Increasing time dramatically
What does O(2^n) mean?
2 to the power of n
It is Exponential Time
Execution time doubles with each item added to the data set. Execution time will very large very quickly
For practical purposes an algorithm within this time complexity would not be considered useful.
