What is an Alogirthm?
- How to systematically perform a task
- Sequence of steps (Varying degrees of detail)
Algorithms can be used to/for:
- Compute numerical functions
- Reorganize data
- Optimization
How to optimise an algorithm? An example
Computing the gcd of two numbers (m,n)
The most obvious solution is to find all factors of the two numbers, see which ones are common and return the greatest one:
def gcd(m,n):
fm=[]
for i in range (1, m+1):
if(m%i)==0:
fm.append(i)
fn=[]
for j in range (1, n+1):
if(n%j)==0:
fn.append(j)
cf=[]
for f in fm:
if f in fn:
cf.append(f)
return (cf[-1])
Optimization 1: Both the factors can be found in the same loop
fm=[]
fn=[]
for i in range (1, max(m,n)+1): #assuming m>n
if(m%i)==0:
fm.append(i)
elif (n%i==0):
fn.append(i)
Optimization 2: We can reduce the loop to min (m,n) as the fcd cannot be greater than that. Also a common list can be used to save only the common divisors
fm=[]
fn=[]
for i in range (1, min(m,n)+1): #assuming m>n
if(m%i)==0 and (n%i==0):
cf.append(i)
Optimization 3: The list can be replaced by a single number and since we want gcd, instead of searching from lowest to highest, we should search from highest to lowest.
i= min(m,n)
while (m%i!=0 and n%i!=0):
i=i-1
return i
For further optimisation, you can read up on Euclids Algorithm
If you are stuck at any point or have any doubts, drop a message here