Before we start writing code, we should first understand how to solve problems using well defined steps and procedures. Let me give you an example.
Sort a list of numbers so that they are in a growing sequence. List : 27,2,1,63,8,26,3,2,8,1,3,3,4
Let's write some steps for a classic bubble sort.
Take the first pair. 27 and 2
If the second one is higher, leave it.
If it is lower, switch them.
Do this until they are sorted.
If you reach the end of list, go again, do another pass.
Now, most of the work is done. It's enough to solve the problem. To make it automatic, we need to write pieces of code for each of the steps. The tools you need to know will be covered later in the course, for now just look at how simple a Python program could be.
In [1]:
def bubble_sort(alist):
for pass_number in range(len(alist)-1,0,-1):
for i in range(pass_number):
left, right = alist[i], alist[i+1]
if left > right:
left, right = right, left
alist[i], alist[i+1] = left, right
print(alist)
In [2]:
bubble_sort([27,2,1,63,8,26,3,2,8,1,3,3,4])
Now, imagine that you need to explain this to the computer.
From where? We need a thing with all pieces. IKEA instructions tell you to do things in a sequence, so let's try a list. We need a list with all pieces.
How do we know which one? It seems like, for each piece, we need to know this. We need to connect this information. To keep things simple, let's keep this information in a list. So for example:
In [3]:
# Chair leg, screwdriver
# Chair seat, hammer
# Chair leg, screwdriver
In [4]:
# Chair leg, screwdriver, 30mm screw
# Char seat, hammer, wooden peg
# Char leg, screwdriver, 30mm screw
# ...
But what if we no longer have any screws? We should stop the program. It also means, somewhere else in program, we should keep count of screws, and each time one is used, decrease the count by 1.
Now, everyone knows this is the hardest part. We need to tell the computer to do something with many elements. "Doing stuff" in programming is performed by instructions, or a sequence of instructions (called a procedure, function, method).
Lets say we define how to use a screw and screwdriver:
In [5]:
def screw_together( furniture_piece, supplies, tool):
connected_furniture = tool.screw(furniture_piece, supplies)
return connected_furniture
Now our list looks like this:
In [6]:
# list_of_actions =
# Chair leg, screwdriver, 30mm screw, screw_together( Chair leg, 30mm screw, screwdriver)
# ...
We managed to at least model the behavior. We know the minimum amount of information an algorithm needs to work its way to the end.
One additional thing is, actually it's really hard to write this down. And a single row of our action list has some duplicated information. Maybe we can write it easier:
In [7]:
# screw_together( Chair leg, 30mm screw, screwdriver)
# hammer_together( Chair seat, wooden peg, hammer)
# screw_together( Chair leg, 30mm screw, screwdriver)
# ...
In [8]:
for action in list_of_actions:
action()
Simple enough. But in the real world, it's better to hold such information in methods and classes. We will go back to this example when we learn more.
This picture presents popular complexities - indicating how much computation is needed for a given input size n of a function.
The steeper upwards the function, the more computationally demanding a calculation is.
Examples:
O(1) - constant time - finding an element of dictionary (hash table) O(log n) - logarithmic - finding an item in a sorted array with binary search O(n log n) - linearithmic - sorting with "heapsort" algorithm, or a fast fourier transform O(n) - linear time - finding an item in an unsorted list O(n^2) - quadratic time - bubble sort algorithm
This value describes how much memory a normal physical computer would need to solve a given computational problem.
Lets say we have a function that accepts a number. Then, it will create a new variable in a loop, as many times as the number. This is a linear space complexity function.