2.3.1 - Algorithms Flashcards
How can you tell which algorithm is better?
The algorithm that can solve the problem for the lowest cost could then be declared the better algorithm.
In general, the amount of resources (or cost) that an algorithm requires in order to return the expected result is called computational complexity or just complexity.
Why does time cost have an impact on the financial cost of running an algorithm?
Computers consume electricity to run.
A quicker program could solve more of the same problem or run more programs in the same time period.
Why is an algorithm using less memory (space) better?
It can:
Run on cheaper hardware (less RAM)
Have a greater number of different algorithms (programs) running on the same hardware.
What does time complexity indicate?
It indicates the time an algorithm takes to run in relation to the size of the input.
For example, the computational time of an algorithm can increase dramatically when the input data is doubled while for a different algorithm the computational time can remain stable.
What does space complexity indicate?
Space complexity refers to the amount of memory required by an algorithm to solve a problem, depending on the size of the input.
What is the order of growth?
The order of growth is a measure of how an algorithm’s time and space complexity changes when the size of the input changes; typically expressed using Big O notation.
What is bubble sort?
Bubble sort is an algorithm that sorts a collection of data by ‘bubbling’ values to the end of the list over successive passes.
On the first pass, the highest value (or lowest, depending on the sort order) is moved to the top of the list.
On the second pass, the second-highest item bubbles to the next-to-top place, the third-highest on the third pass, and so on, until it has produced a sorted list.
Most efficient bubble sort code?
PROCEDURE bubble_sort(items)
# Initialise variables
num_items = LEN(items)
temp = 0
pass_number = 1
swapped = True
# Continue while swaps have been made and there are more passes to evaluate
WHILE swapped == True AND pass_number <= num_items - 1
swapped = False
FOR index = 0 TO num_items - pass_number
# Check if items are out of order
IF items[index] > items[index + 1] THEN
# Swap items
temp = items[index]
items[index] = items[index + 1]
items[index + 1] = temp
swapped = True
ENDIF
pass = pass + 1
NEXT index
ENDWHILE ENDPROCEDURE
What is the space complexity of bubble sort?
Bubble sort is very efficient in terms of memory requirement, because the sorting is done in the same space as the original data. The only item needing to be copied is the value being swapped, which can be done with one value regardless of how many items are in the original list.
So the space complexity is O(1)
What is the time complexity of bubble sort with nested for loops?
O(n^2) for all cases
What is the time complexity of bubble sort with an outer while loop and/or decreasing inner loop.
O(n) for best case
O(n^2) for all other cases
