| Author |
Topic: How to tell one algorithm is better than another. |
|
Alex_Raj
member
offline  |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
 |
|
|
| How to tell one algorithm is better than another. |
That's simple. Here is the rules:
Rule #1: It is accurate, of course
Rlue #2: It is more efficient.
|
|
|
|
|
|
|
Alex_Raj
member
offline  |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| How to tell a algorithm is efficient? |
An algorithm is considered efficient if its resource consumption is at or below some acceptable level. There are many ways in which the resources used by an algorithm can be measured: the two most common measures are:
Speed, and
Memory usage
Other measures could include:
Disk usage
Power consumption
Total cost of ownership.
Many of these measures depend on:
The size (N) of the input to the algorithm
The way in which the data is arranged, which results in so called "worst case scenario", "best case scenario" and "average case scenario".
For example, QuickSort algorithm is measured as:
Worst case performance O(N^2)
Best case performance O(NlogN)
Average case performance O(NlogN)
Worst case space complexity O(N)
|
|
|
|
|
|
|
Alex_Raj
member
offline |
| |
| posts: |
99 |
| joined: |
05/16/2006 |
| from: |
San Jose, CA |
|
|
|
|
|
| Example |
Let's look at a very simple example:
Algorithm A: Count the number of data input
public static int count(int[] a){
return a.length;
}
Algorithm B: Count the number of data input
public static int count(int[] a){
int count = 0;
for(int i=0; i<a.length; i++){
count++;
}
return count;
}
As we can see, the execution time of algorithm B is proportional to the size of array: the more the size, the more the time consumed; whereas the execution time of algorithm A is irrelevant to the size of array and remains constant. Therefore, we can conclude:
Algorithm A = O(1)
Algorithm B = O(n)
Algorithm A is more efficient than B, and thus algorithm A is better than B
|
|
|
|
|
|
|
|
Email To Friend | 
Set Alert To This Topic
New Topic | 
Post Reply 
posted on: 12/14/2013 02:46:22 AM
Edit
Quote
Report
Profile
Reply