Week 11: Sorting and Efficiency
Efficiency in general,
describes the extent to which time, effort or cost is well used for the
intended task or purpose. – definition from Wikipedia
When we talk about efficiency in Computer Science and
programming, we see how much time is needed for a result of the code to be
executed; that is usually calculated by how may “lines of code” are ran during
the execution.
Ex) Which algorithm is better? - Algorithm A takes n^2– 37
time units or Algorithm B takes n+45 time units, when n presents the input
number(or size). OF COURSE algorithm B!
These matter much more when n gets larger, and usually there
is not much difference when n is small. Which means efficiency only matters
when n is a large number.
Big-O Notation
- the time complexity(efficiency) of
an algorithm is commonly expressed using big O notation, which suppresses
multiplicative constants and lower order terms (of course since this deals with
“efficiency”, we need to think n as a BIG number, as we discussed from the
above)
Relationships
between orders (for the basic Big-O’s)
O(1) < O(log n)
O(log n) < O(n)
O(n) < O(n log n)
O(n log n) < O(n^2)
O(n^2) < O(n^3)
O(n^x) < O(x^n), for
all x and n
Than now, let’s look
at sorting…
Many common sorts
consists of nested loops (n^2)
Ex) Selection sort,
Insertion sort, Bubble sort
Or you can sort
recursively by dividing set into two pieces and sorting each piece recursively.
Ex) Merge sort,
Quick sort
As we progress in learning in CS, we will be dealing with
much more complicated algorithm; without thinking about efficiency, the program
that is created will be less helpful and less appealing to the user. What we
can see from the above is that there are several approaches to find best
algorithm to sort, which means that there is no fixed answer for a problem(usually
in real life situation as they are much more complex than just a plain sorting
problem). Now our job as a programmer is to come up with new and better
algorithm and compare with others to develop with what we already have to make
the existing code efficient.
