| Previous | Next |
|---|
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
When an object has no references to it, then the JVM can do garbage collection on it. For example.
String s1 = new String("old"); s1 = new String("new"); The string object having the content old no longer has any references to it; therefore, it can be garbage collected.Garbage collection frees memory only. If you have objects that are using other system resources, then
Object.finalize()can be overridden to reclain (i.e. garbage collect) those resources.Syntax.
protected void finalize() throws Throwable The finalize() method implemented in the Object class does nothing.It is important to note the following with respect to finalizers.
- they are not equivalent to C++ destructors
- no guarantee they will be called (they were worthless in jdk1.0)
- no guarantee as to when they will be called
- to force finalizers to run:
System.gc(); System.runFinalization(); //gc() must be msg'd 1stSystem.runFinalizersOnExit();to force finalizers to run when the program exits
A tree is a "nonlinear" structure that consists of nodes and branches.
Arrays, stacks, queues, and linked-lists define collections of objects that are sequentially accessed. These are linear lists: they have first and last elements, and each interior element has a unique successor.
In a nonlinear structure, an element may have multiple successors.
Tree structures are used to represent a "hierarchy" of information. A commonly used hierarchy is an operating system's file system. [websites]
A tree structure consists of a set of nodes that originate from a unique starting node called the root.
Some nodes may be considered a parent node which implies they have zero or more children nodes to which they are connected.
The children of a node and children of those children are called descendants, and parents and grandparents of a node are its ancestors.
A node that doesn't have any children is called a leaf.
Each node in a tree is the root of a subtree, which is defined by the node and all descendants of the node.
grandfather
|
+----------+-----------+
| | |
father uncle aunt
|
+-----+-----+
| |
brother sister
grandfather is the root node. grandfather is the parent
node to father, uncle and aunt. father, uncle, aunt, brother
and sister are all descendants of grandfather. father and
grandfather are ancestors of brother and sister. brother and
sister are children of father. brother are sister are leaf
nodes. brother and sister are siblings. father is the root
of the subtree that contains the father, brother, sister nodes.
A single-inheritance class hierarchy can be represented by a tree.
Component
|
+------------------+------------+------------+
| | | |
Container Button Canvas TextComponent
| |
+---------+----------+ +----+----+
| | | | |
Panel ScrollPane Window TextArea Textfield
|
+-----+----+
| |
Dialog Frame
|
FileDialog
Movement from a parent node to its child and other descendants is done along a path.
The level of a node is the length of the path from the root to the node.
The depth of a tree is the maximum level of any node in the tree.
A level 0
/ | \
B C D level 1
\ \
E F level 2
/ \
G H level 3
The depth of this tree is 3 (the longest path from the root
to a node). The path length for node E is 2. The path
length for node D is 1. The path for node H is: A->B->E->H.
Definition:
A general tree is a set of nodes that is either empty, or has a designated node called the root from which descend zero or more subtrees. Each node is not an ancestor of itself, and each subtree itself satisfies the definition of a treee.
Note that a tree is defined in a recursive fashion; consequently, most tree-processing algorithms are recursive.
| Previous | Next |
|---|