1. Algorithms and Analyzing Algorithm.
The quote above from Donald Knuth said an algorithm is something difficult to believe and Yes it is.But why do we need it in our life and especially in programming ?Informally, an algorithm is any well-defined computational procedure that takes some values or set of values, as input and produces some value, or set of values as output.An algorithm is thus a sequence of computational steps that transform the input into the output.
If you need to solve any problem, the first thing you need is an algorithm.It is a tool used to achieve your output from the input.
It can be seen from any activities in daily routine.
For example.
Input: YouSo the algorithm for this problem is.
Ouput: You go to school in time at 8am.
Step 1: Wake up.
Step 2: Brush your teeth
Step 3: Put on your clothes
Step 4: Get on the bus
Step 5: Let your body lie in school in time at 8am.
Did you see it? it's quite easy to understand what the algorithm means. Then why do we need to know what is Analyzing algorithm is?
Let's glance briefly at this solution for the example above.
Step 1: Wake up.
Step 2: Get your body on the bus.
Step 3: Put your ass in school in time at 8am.
It seems weird and naughty, isn't it? Some morning you just wake up without brushing your teeth, you are still lazy and smelly, your class can be contaminated by your smell but it is not the problem. You get the result you want from the output.
Because the Input provides You
and the
Output only want You to go to school in time at 8am.
Congrats, You nailed it.
The first solution needs 5 steps to get the required result when the second only needs 3.
If I am shameless;
The second must be the optimal solution.
To conclude, the algorithm is the process of steps you need to do to achieve the result you want and analyzing the algorithm to help you know the efficiency and chose the best solution in the suitable case.It's too easy...?
Okay, take your seat and careful
we are moving to the less easy way.
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify problem according to how their running time or space requirements grow as the input size grows.
Order of growth.
The key point in analyzing the running time of a program is this: for a great many programs, the running time satisfies the relationship where is a constant and function is known as the order of growth of the running time. For typical programs, f(n) is a function such as $log_2n$ , $nlog_2n$ , $n$ , $n^2$ ,$n^3$ , $n!$ .The reason for not using $log_{2}(n)$ or $log_{3}(n)$ or even $log_{7}(n)$ for T(n) can be explained like this
while we got $log_{a}{c}$ = $log_{a}{b}$ . $log_{b}{c}$
from the properties of logarithms in A Quick Math Review.
Let T(n) = $log_2(n)$ = $log_2(10)$ . $log_{10}(2)$ and $log_2(10)$ is a constant as c,
Then we can conclude that $T(n)\approx\ c\lg{n}\approx\lg{n}$
Scientists trying to make it formal and easy to understand as much as possible.
Order of growth classifications.
For a concrete example, we will make a competition for two computers.
Computer A is faster and can execute 10 billion = $10^{10}$ instructions per second.
while Computer B is slower and can only execute 10 million = $10^7$ instructions per second.
Input: 10 million numbers
Output: 10 million sorted numbers.
If the numbers are eight-byte integers, then the input occupies 80 megabytes, which fits in the memory of even an inexpensive laptop computer many times over.
Computer A must use Insertion sort T(n) = O( $n^{2}$) to sort.
Computer B must use Merge sort T(n) = O( $n$$log{n}$) to sort.
Computer A is 1000 times faster than computer B in raw computing power.
This is the result
Running time on computer A:
$\frac{2(10^{7})^{2} .instructions}{10^{10}.instructions/second} \approx$ 20 000 seconds ( more than 5,5 hours ).
Running time on computer B:
$\frac{50(10^{7})\lg{10} .instructions}{10^{7}.instructions/second} \approx$ 1163 seconds ( less than 20 minutes ).
Computer hardware is something but the algorithm is much more important and it plays an important role in developing our information technology in the 21th century.
Thanks for visiting my blog, there are areas of mathematics that concern themselves directly to programming so next post will be about Math review.
You may come here to learn not to laugh sorry bout that btw haha
0 nhận xét:
Post a Comment