Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms/data compression - Coggle Diagram
Algorithms/data compression
Linear search
Sequential search until either data is found or not found
Data does not need to be in order
Drawbacks: slow
Binary Search
Takes midpoint and disregards data on one side
midpoint=low+(high-low)/2 if decimal round
Does this until data is found or not found
Data must be sorted first
Bubble sort
Looks at each adjacent pair of numbers if rightmost is less than then swap
Does more than one pass
When no more exchanges data has been sorted
Insertion sort
Makes separate sub list and compares with elements to data in the sorted sub list
Data Compression
Means reducing file size of a file
Lossy
loses data and data removed cannot be put back
Lossless
replaces data with common values
Data can be put back
Run Length encoding
Finds runs of data repeated binary patterns
Then replaces them with a single instance of a pattern and how many times the pattern is repeated
Well suited for image files but not on detailed photos where each individual pixel is a different colour
Dictionary-based compression
allocates code for each unique word ,creates dictionary
e.g store hashing as 00000
Huffman econding
Creates dictionary of letters used and most used letters have shorter code
Compression ratio=uncompressed size/compressed size
Space saved=uncompressed size/compressed size
Big O notation and time complexity
An estimate of well an algorithm scales and is an estimate of efficiency e.g will it work as well at 10 items as at 10,000 items.Have to assume worst place scenario.
O(1)-Constant time
Algorithm always takes the same time to complete each time it runs regardless of size of data set .Think of reading a page in a book with 4 pages and reading a page in a book with 4000 pages both take same time..
O(N)-Linear time-the length of tine taken to complete an algorithm is directly proportional to the size of the data set (N) e.g reading a longer book takes longer than reading a shorter book
If have tow data sets being processed indecently of each other O(n+x)
O(n")-Qaudric time-An algorithm with a loop within a loop
Cubic time-A loop within a loop within a loop
Qaudratic time is faster than cubic time idea is each time mainloop goes nested loops run mutiple times
O(log n) Logarithmic time -Only applies to divide and conquer scenarios e.g binary search. Means that running time grows in proportion to the logarithm of the input size.