algorithms Flashcards
2 things to check when developing an algorithm
time complexity
space complexity
what is time complexity
how much it takes to solve a particular problem
what is time complexity measured in
using big-o notation
what does big o notation show
the effectiveness of an algorithm
show the time taken relative to the number of data elements given as an input
what is the benefit of big O notation
allows to predict the amount of time it takes for an algorithm to finish the given number of elements
define liner search algorithm
an algorithm that looks through every item one at a time until it finds the item its searching for
big o notation for linear search algorithm is
0 (n)
what is binary search algorithm
a divide and conquer algorithm, this means it splits the list into smaller lists until it finds the item its searching for
big o notation for binary search
0 ((log(n)
what is a bubble sort algorithm
Algorithm that passes through the list evaluating pairs of items and ensuring the larger value is above the smaller value
big o notation for bubble sort 0(n^2)
0(n^2)
big o notation for bubble sort 0(n^2)
0(n^2)
what is an algorithm,
a series of steps taken to complete a task
what is space complexity
the space complicity of an algorithm is the amount oof storage the algorithm takes (keep in sotairage is expensive )
big o notation for space complexity
(O(n))
In maths and Physics tutor look at BIG ON NOTAION DEFINITIOSN AND GRAPHS
what does bubble sort do
makes comparisons and swaps between pairs of elements
how does bubble sorting work
he algorithm starts at the first element in an array and compares it to the second. If they are in the wrong order, the algorithm swaps the pair. Otherwise, the algorithm moves on. other wise repeats process
important note in bubble sort
one pass= the whole line being sorted I ascending order even if the first element aren’t correct
e.g the 1st pass may look like this
4,1,6,7,9
2nd pass= bubble sort reorder again from the beginning
e.g 1,4,6,7,9
pseudocode for bubble sort
A = Array of data
for i = 0 to A.length - 1:
noSwap = True forj=0toA.length-(j+2):
if A[j] > A[j+1]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
noSwap = False
if noSwap:
break
return A
is bubble sort a fast algorithm
slow
what is insertion sort
insertion sort places elements into a sorted sequence.
where does insertion sort start
rt starts at the second element in the input, and compares it to the element to its left. If the two elements are in the wrong order, the smaller element is placed in the lowest position.
things to note about insertion sort
if you have gotten to the 6 element of the list and it is smaller than all the first ones (although it has already. been sorted) it automatically goes to its correct position
