1 How to measure the running speed of an algorithm?

How to measure the running speed of an algorithm? What exactly does it mean for an algorithm to be fast or efficient well?

Of course, we cannot simply measure the “running time” of the algorithm, because the different computers have different configuration.

Maybe it runs slowly on this computer because this computer is 10 years old!

So you can’t say program A is slower than program B, just based on how long the computer is running the program. Because different computers are configured differently.

2 Asymptotic Notation

Computer scientists and mathematicians developed the method of progressive analysis.

2.1 Big O notation

2.1.1 definition

A function f(x) runs on the order of G(x) if there exists some x value x_0 and some constant C for which f(x) is less than or equal to that constant times G(x) for all x greater than x_0. Then we say that f(x)=O(g(x)).

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \leq C \times g(x).

for example:

2.1.2 example

for another example:
f(x) = 4x^2 + 16x + 2,
g(x) = x^4,
then, we have:
f(x) = O(g(x)),
that means: 4x^2 + 16x + 2 \leq C \times x^4.

when C=1:

x 4x^2 + 16x + 2 < x^4 T or F
0 2 < 0 F
1 22 < 1 F
2 50 < 16 F
3 86 < 81 F
4 130 < 256 T
f(x) < g(x) T

So, there is normal for x_0=4, C=1, for all x greater than x_0, there are f(x) \leq C \times g(x). So, f(x)=O(g(x)).

2.2 Big Ω notation

2.2.1 definition

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \geq C \times g(x).

2.2.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = Ω(g(x)),
that means: 4x^2 + 16x + 2 \geq C \times x^2,

when C=1:

x 4x^2 + 16x + 2 > x^2 T or F
f(x) > g(x) T

So, there is normal for x_0=0, C=1, for all x greater than x_0, there are f(x) \geq C \times g(x). So, f(x)=Ω(g(x)).

2.3 Big θ notation

2.3.1. definition

f(x) = \theta(g(x)) iff
(1)f(x)=O(g(x)),
(2)f(x)=\Omega(g(x)),

2.3.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = \theta(g(x)),
than means:f(x) = O(g(x)) and f(x) = \Omega(g(x)).

prove f(x) = O(g(x))

when C=5, x>=20:
4x^2 + 16x + 2 \leq 5 \times x^2
so,f(x) = O(g(x))

prove f(x) = Ω(g(x))

when C=1, x>=0:
4x^2 + 16x + 2 \geq x^2
so,f(x) = Ω(g(x))

you can see this pic:

so,f(x) = θ(g(x)).

0
Posted in 计算机基础知识

Leave a Comment:

电子邮件地址不会被公开。