Unit 12 - Algorithms Flashcards
What are the properties of a good algorithm? (4/6)
- has clear steps
- produces a suitable output for every input
- allows for invalid inputs
- will always terminate
- should execute in as few steps as possible
- others should understand and be able to modify (if necessary)
What is time complexity and space complexity?
Time complexity: a measure of the time taken for an algorithm to complete, given as an upper bound to ensure the algorithm’s performance is predictable and scalable
Space complexity: a measure of the amount of memory space an algorithm uses, which accounts for the space needed for the input and the space needed for the algorithm’s code
What is Big-O notation?
A measurement of how the runtime or space requirements of an algorithm grow as the input size grows
How are linear searches performed?
- Start with the first item
- If this item is not the target item, continue moving sequentially through the list until the target is found
- If this item is the target item, then the target has been found and the search terminates
What are the advantages and disadvantages of the linear search?
Adv.
- Easy to program
- Easy to understand
- Easy to trace
- List does not need to be sorted
Disadv.
- Takes n comparisons in the worst case scenario
- Has time complexity of O(n) which is worse than the binary search time complexity
How are binary searches performed?
1) Take a sorted list as an input
2) Check the middle item in the list
3) If this is the target item, the search terminates and the item is returned
4) If this is not the target item, the item and the target are compared
5) If the item is smaller than the target, the item and all items smaller than it are discarded
6) If the item is larger than the target, the item and all items larger than it are discarded
7) This process is repeated until the target or found or if there are no items left (target is not in the list)
What are the advantages and disadvantages of a binary search?
Adv.
- Time complexity O(log n) which is very good
- Suited to large data sets
Disadv.
- Harder to program
- Harder to trace
- List must be sorted
How are bubble sorts performed?
1) Start with the first item in a list
2) Compare this item with the next one
3) If the first item is bigger/smaller (depends on ascending/descending order) than the next item, then swap the items
4) If not, then do not change the items
5) Continue comparing pairs of items until the end of the list, where the largest/smallest (depends on ascending/descending order) will be at the final position
6) After this first pass, continue iterating through the list and comparing items until the list is sorted
What are the advantages and disadvantages of the bubble sort?
Adv.
- Easy to understand and trace
- Easy to program
- Constant space complexity O(1), since all changes are within the same list
- O(n) time complexity in the best case scenario (list is mostly sorted)
Disadv.
- Average time complexity of O(n^2)
How are merge sorts performed?
1) A list is recursively broken down into smaller sublists until each sublist contains only a single item
2) Each sublist is merged together with its adjacent list while being sorted. The items in the sublist are compared and inserted into their sorted position.
3) Sublists are repeatedly merged and sorted until they form a single list with the sorted items
What are the advantages and disadvantages of the merge sort?
Adv.
- Efficient for large arrays
- Time complexity of O(n log n)
Disadv.
- Difficult to program
- Used more memory (because of recursion)
How are insertion sorts performed?
1) A list is logically partitioned into sorted and unsorted parts
2) The list is iterated through and each item is inserted into the sorted list
3) Items are compared with each item in the sorted list, starting from the first until it finds an item greater than it
4) This is repeated until there are no more items in the unsorted part
What are the advantages and disadvantages of the insertion sort?
Adv.
-?
Disadv.
- Time complexity of O(n^2)
How are quick sorts performed?
1) Select the first element in a list as the pivot
2) Go through each item after the pivot and place numbers smaller than the pivot behind it in the order they appear
3) The pivot now becomes fixed in place
What are the advantages and disadvantages of the quick sort?
Adv.
- O(n log n) time complexity
Disadv.
- high memory use (due to recursion)
- time complexity in worst case is O(n^2)
- difficult to program