Subject: Example
Author: Alex_Raj
In response to: How to tell a algorithm is efficient?
Posted on: 12/14/2013 10:13:18 PM
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;
}
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
>
> On 12/14/2013 03:27:46 AM Alex_Raj wrote:
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)
References:
