FHTW Berlin
Fachbereich 4
Internationale Medieninformatik
PROG2: Programmierung II
Sommersemester 2003
|
|
FHTW Berlin |
Complexity
Instead of saying
"the run time T(N) of an algorithm depending on the size of the problem N is, for all N:
T(N) £ c1 · N + c2
with two constants c1 and c2"
we say:
"T(N) is of order N"
or
"T(N) is O(N)". ("Big Oh" of N)
In mathematics we say
When we say that an algorithm is of order O(f), that means that it needs f units of time (in this example microseconds or millionths of a second) for computing one input, then the algorithm will need this much time for calculating N inputs:
| O(f) | N | ||||
|
|
10 |
100 |
1000 |
10000 |
100000 |
|
| |||||
|
O(1) |
1.0 x 10 -6 s |
1.0 x 10 -6 s |
1.0 x 10 -6 s |
1.0 x 10 -6 s |
1.0 x 10 -6 s |
|
O(log N) |
1.0 x 10 -6 s |
2.0 x 10 -6 s |
3.0 x 10 -6 s |
4.0 x 10 -6 s |
5.0 x 10 -6 s |
|
O(N) |
1.0 x 10 -5 s |
1.0 x 10 -4 s |
1.0 x 10 -3 s |
1.0 x 10 -2 s |
1.0 x 10 -1 s |
|
O(N log N) |
1.0 x 10 -5 s |
2.0 x 10 -4 s |
3.0 x 10 -3 s |
4.0 x 10 -2 s |
5.0 x 10 -1 s |
|
O(N2) |
1.0 x 10 -4 s |
1.0 x 10 -2 s |
1.0 second |
1.7 minutes |
2.8 hours |
|
O(N3) |
1.0 x 10 -3 s |
1.0 second |
17 minutes |
11.6 days |
31.7 years |
|
O(2N) |
1.0 x 10 -3 s |
1.0 x 10 14 century |
1.0 x 10284 century |
finite, but very long |
finite, but very, very long |
| Last change: 01.04.03 - 09:26 |