Alex_Raj
member
offline  |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
 |
|
|
| Why do I care about algorithm efficiency? |
With computer power being doubled every 18 months as Moore's Law states, why do I care about algorithm efficiency as long as the algorithm is accurate?
Waaa, well let's look at the following real testing benchmark run on Intel Core-i7 2.8GHz
Table 1. Typical Algorithm Performance Benchmark (in second)
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
Size of problem | BinarySearch | LinearSearch | QuickSort | MergeSort | HeapSort | InsertSort | BubbleSort | Hanoi Tower
(n) | O(logn) | O(n) | O(nlogn) | O(nlogn) | O(nlogn) | O(n^2) | O(n^2) | O(2^n)
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
10 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.001 / 0.5 hour*
20 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.076 / 12 days*
32 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 175.171 / 136 years*
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
1,000 | ~0 | 0.000 | 0.000 | 0.001 | 0.001 | 0.007 | 0.008 |
10,000 | ~0 | 0.000 | 0.015 | 0.003 | 0.008 | 0.022 | 0.166 |
100,000 | ~0 | 0.000 | 0.023 | 0.034 | 0.024 | 1.505 | 16.119 |
1,000,000 | ~0 | 0.001 | 0.151 | 0.202 | 0.214 | 151.941 | 1,598.389 |
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
10,000,000 | 0.000 | 0.005 | 1.543 | 2.012 | 3.123 |17,736.500 | |
100,000,000 | 0.000 | 0.042 | 17.382 | 22.152 | 46.136 | | |
1,000,000,000 | 0.000 | 0.372 | | | | | |
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
* Note: If it were done by human with moving speed of 1 disk per second.
Observations:
For simple (O(n)) tasks like searching one item from a list, you may not care about which algorithm to choose with a powerful computer.
For decent (O(n^2)) tasks like sorting a list, you got to be very careful about which algorithm to choose if your size of problem (n) is greater than 1 million. As you can see from Table 1, QuickSort takes 0.151 second to finish your job whereas BubbleSort can easily bring your computer to its knees.
For complex (O(2^n)) tasks like moving Hanoi Tower, you really have to ask yourself the same question again: Why do I care about algorithm efficiency? The algorithm provided here took a 2.8GHz computer 175 seconds just to move 32 disks!
|
|
|
|
|
|
Email To Friend | 
Set Alert To This Topic
New Topic | 
Post Reply 
posted on: 12/19/2013 01:19:16 AM
Edit
Quote
Report
Profile
Reply