Most of computer science students won’t forget the pain of learning data structure and algorithm. If you work at Google or NASA, then you may use it everyday. Why data structure and algorithm is so important and how to refactor your code? think about this,

For example, write a function to display all Fibonacci numbers for given number.
function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n – 1) + fib1(n – 2)

If you write code like above, then the bigO would grow up to 2^n. In short, our naive recursive algorithm is correct but hopelessly ineffcient. Can we do better?

function fib2(n)
if n = 0 return 0
create an array f[0 : : : n]
f[0] = 0, f[1] = 1
for i = 2 : : : n:
f[i] = f[i – 1] + f[i – 2]
return f[n]

The bigO would be linear in n.

Do you see the big different? remeber whenever we have an algorithm, there are three questions we always ask about it:

1. Is it correct?
2. How much time does it take, as a function of n?
3. And can we do better?
Ref:
Algorithms from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Data Structures and Algorithms

Wiki: Algprithm

Sort algorithm

Graph algorithms

Advertisements