| Previous | Next |
|---|
Compile-time is the time that is required to compile a program. Run-time is the time that it takes for a program to execute.
Clients (e.g. end-users) are particularly interested in a program's run-time. If a program is slow, then users may not use a program.
The amount of time a program takes to execute depends on a variety of factors: the underlying hardware and platform that the program is running on, system load at the time a program is executing, the amount of data the program needs to process, the number of instructions the program needs to execute, and so forth.
In many cases, the only way to "fix" a slow program is to throw more hardware at it and given today's cost of computing this is often an economically viable solution. If you cannot provide more hardware for the program, then the following can be tried:
Of the items mentioned above, "tweaking" the algorithms used in a program can be beneficial. General rule: look at the algorithms first, then examine the code.
The run-time efficiency of a program has two main ingredients: space and time.
Space efficiency is a measure of the amount of memory a program requires.
Time efficiency is a measure of how long a program takes to execute.
In general, there is a trade-off between space and time. If your algorithm uses more space, then typically it will execute faster and vice versa.
The relationship between N (where N is
a variable representing the number of inputs on which your algorithm
must operate) and the running time of an algorithm as N
becomes large is called the computational complexity of that
algorithm.
Computational complexity is denoted using BigO notation.
The letter O stands for the word order as it is
used in the phrase on the order of. It signifies
approximation.
Given two functions f and g, the function g is said to dominate function f if there is some positive constant c such that:
c * g(x) >= f(x), for all possible values of x
Asymptotic dominance is a variation of dominance such that:
c * g(x) >= f(x), for all x >= x'
In other words, function g asymptotically dominates function f for all "large" values of x. Big-O notation is represented using asymptotic dominance.
5N versus N2
-------------------------
N=1: 5 versus 1
N=2: 10 versus 4
N=3: 15 versus 9
N=4: 20 versus 16
N=5: 25 versus 25
N=6: 30 versus 36
N=7: 35 versus 49
In this example, x' is equal to 6 and the constant is 1.
The following are some examples of how dominance is used to determine BigO values:
O(N3) + O(N2) => O(N3)
As N gets large, N cubed grows at a faster rate than
does N squared. For large values of N, N cubed dominates.
O(10 * N) + O(1000 * N) + O(1) => O(N)
Constant values are ignored. The significance of the
constant values are minimized for large values of N.
O(N log N) + O(log N) + O(N2) => O(N2)
N squared dominates N log N which in turn dominates log N.
Let's review:
O(N) may have different
running times for the same number of inputs
BigO-notation is used for three distinct purposes.
| O(1) | constant time (most efficient) |
| O(N) | linear time (polynomial time) |
| O(N log N) | "linearithmic" time (polynomial time) |
| O(N2) | quadratic time (polynomial time) |
| O(N3) | cubic time (polynomial time) |
| O(log N) | logarithmic time |
| O(2N) | exponential time (impractical for large values of N) |
The following table presents growth rates for some of the common functions (i.e running times):
N log N N N log N N**2 N**3 2**N
=========================================================================
1 0 1 0 1 1 2
2 1 2 2 4 8 4
4 2 4 8 16 64 16
8 3 8 24 64 512 256
16 4 16 64 256 4096 65536
32 5 32 160 1024 32768 4.29497e+09
64 6 64 384 4096 262144 1.84467e+19
128 7 128 896 16384 2097152 3.40282e+38
Note: the aforementioned table was generated using the BigOvalues.cpp program.
Typically, constant factors are ignored in BigO analysis (although in reality constants do matter).
To compare the speed of different algorithms, computer scientists use bigO notation. The bigO notation doesn't exactly predict performance times. Instead, what the bigO notation tells us is that given two algorithms with the same order, then both will slow down at roughly the same rate as the number of items being sorted gets larger.
Search algorithms also have bigO values. Linear search
is O(n), binary search is O(log n).
Once again, these differences are most important for large data sets.
If you have 1 million items in an array, a linear search will require
about 1 million tests, but a binary search will only require 20 tests
(because 2 to the 20 power is about 1 million -- the 'log' in bigO
notation is always log-base-2 -- when you have a logarithmic algorithm,
the analysis need not be concerned with the base of the logarithm, since
this can change the total running time only by a constant factor (and
constant factors are ignored).
for (i = SOME_CONSTANT; i <= ANOTHER_CONSTANT; i++) // O(1)
// loop body requiring constant time
for (i = SOME_CONSTANT; i <= N; i++) // O(N)
// loop body requiring constant time
for (i = SOME_CONSTANT; i <= N; i++) // O(N*N)
for (j = ANOTHER_CONSTANT; j <= N; j++)
// loop body requiring constant time
for (i = SOME_CONSTANT; i <= N; i++) // O(N*M)
// loop body requiring time O(M), where M is a variable
The following is example of how one can go about determining the approximate running time of an algorithm.
// the following logic initializes a 'n' element array
index = 0; // assignment is 1 step
while (index < n) { // EXPR index < n is 1 step
array[index] = -1; // assignment is 1 step
index++; // increment is 1 step
}
Si + Sc*(n+1) + Sb*n
n = 0: 1 + 1*1 + 2*0 = 2
n = 1; 1 * 1*2 + 2*1 = 5
n = 2; 1 * 1*3 + 2*2 = 8
n = 3: 1 + 1*4 + 2*3 = 11
n = 6: 1 + 1*7 + 2*6 = 20
n = 9: 1 + 1*10 + 2*9 = 29
n = 300: 1 + 1*301 + 300*2 = 902
Si => # of initialization steps
Sc => # of steps in the condition EXPR
sb => # of steps in the loop body
Conclusion: linear -- O(n)
for (k = 1; k <= n / 2; k++) {
...
for (j = 1; j <= n * n; j++) {
...
}
}
Since these loops are nested, the number of times statements
within the innermost loop are executed is the product of the
number of repetitions of the two individual loops. Hence the
efficiency is n3, or
O(N3) in BigO terms,
with a constant of proportionality equal to 1/2.
for (k = 1; k <= n * 10; k++) {
...
}
for (j = 1; j <= n * n * n; j++) {
...
}
Since one loop follows the other, the number of operations
executed by both loops is the sum of the individual loop
efficencies. Hence the efficiency is 10n + n3,
or O(N3) in BigO terms.
Assume we have array A with length N
and we want to find the minimum element in the array.
Pass 1: compare the n-1 elements A[1]...A[n-1]
with A[0] and, if necessary, exchange elements
so that A[0] always has the smallest value
Pass 2: compare the n-2 elements A[2]...A[n-1]
with A[1] and, if necessary, exchange elements
so that A[1] less than all elements to the right
Pass i: compare the n-i elements A[i]...A[n-1]
with A[i-1] and, if necessary, exchange elements
The total number of comparisons is given by the
arithmetic series f(n) from 1 to n-1:
f(n) = (n-1) + (n-2) + ... + 3 + 2 + 1 = n * (n-1) / 2
The number of comparisons depends on n2.
Append an item: O(1). Insert an item at the front of the array: O(N).
Bubble, selection, insertion, and exchange are all O(N2).
Shell sort can give much better performance than O(N2) in the worst case.
Quick sort in the worst case can be O(N2), but on average it is O(N log N).
Merge sort is an O(N log N) sort.
The order of a function is defined as follows:
Given two non-negative functions f and g,
the order of f is g if and only if g
asymptotially dominates f. Using BigO notation,
this can said as: f = O(g) (f is of
order g).
Some rules to help calculate and compare BigO estimates:
Let f and g be functions, and C a constant:
O(C * f) = O(f)
O(f * g) = O(f) * O(g)
O(f / g) = O(f) / O(g)
O(f) > O(g), if and only if f dominates g
O(f + g) = Max[O(f), O(g)]
A logarithm of base b for the value y
is the power to which you must raise b to get y.
Normally, this is written as: logby = x.
logby = x <=> bx = y <=> blogby = y
where <=> means "is equivalent to"
Logarithms have the following properties:
For any positive values of m, n, and r, and any positive integers
a and b:
log nm = log n + log m
log n/m = log n - log m
log nr = r log n
logan = logb n / logba
| Previous | Next |
|---|