Asymptotic Notation(渐进表示法、渐进分析)

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!

可能在这个电脑上运行时间慢,是因为这个电脑是 10 年前的电脑!

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.

因此,不能说 A 程序比 B 程序运行时间慢,仅仅根据电脑运行程序的时间。因为不同的电脑配置不一样。

2 Asymptotic Notation(渐进分析)

Computer scientists and mathematicians developed the method of progressive analysis.

计算机科学家和数学家,提出了渐进分析的方法。

2.1 Big O notation (渐进上界 O 符号)

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).

存在正常数 x_0, C, 对所有的大于 x_0x, 均存在 f(x) \leq C \times g(x)。 表示为 f(x)=O(g(x)).

按照定义来讲,O(g(x)) 应该是一个函数的集合,理论上应该写作 f(x) \in O(g(x)). 但是惯例写作 f(x)=O(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(当 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

所以,存在正常数 x_0=4, C=1, 对所有的大于 x_0x, 均存在 f(x) \leq C \times g(x)。因此,g(x)f(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).

存在正常数 x_0, C, 对所有的大于 x_0x, 均存在 f(x) \geq C \times g(x)。 表示为 f(x)=Ω(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(当 C 为 1 的时候):

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

所以,存在正常数 x_0=0, C=1, 对所有的大于 x_0x, 均存在 f(x) \geq C \times g(x)。因此, g(x)f(x) 的渐进下界。

2.3 Big θ notation (渐进紧界 θ 符号)

2.3.1. definition

f(x) = \theta(g(x)) iff(当且仅当if and only if)
(1)f(x)=O(g(x)),
(2)f(x)=\Omega(g(x)),

f(x)=Ω(g(x))f(x)=O(g(x)),则f(x) = \theta(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

Leave a Reply

Your email address will not be published.