C++ 数据结构(一)绪论(2)计算模型
in C/C++ with 0 comment, Views is 77

C++ 数据结构(一)绪论(2)计算模型

in C/C++ with 0 comment, Views is 77

上一篇:《C++ 数据结构(一)绪论(1)计算》

算法分析的两个主要方面

考察

$ T_A (P) $ = 算法 A 求解问题实例 P 的计算成本

意义不大,可能出现的问题实例太多

如何归纳概括?

观察

问题实例的规模,往往是决定计算成本的主要因素

特定算法 + 不同实例

令 $ T_A (n) $ = 算法 A 求解某一问题规模为 n 的实例,所需的计算成本

讨论特定算法 A(及其对应的问题)时,简记作 T(n)

然而,这一定义仍有问题...

观察

同一问题等规模的不同实例,计算成本不尽相同,甚至有实质差别

例如:在平面上的 n 个点中,找到所成三角形面积最小的三个点

1.png

以蛮力算法为例,最坏情况下需枚举所有 $ C_n^3 $ 种组合,但运气好的话一次即可

既然如此,又该如何定义 T(n) 呢?

稳妥起见,取 T(n) = max{T(P) | |P| = n}

亦即,在同规模同为 n 的所有实例中,只关注最坏(成本最高)者

特定问题 + 不同算法

同一问题通常有多种算法,如何评判其优劣?

实验统计

实验统计是最直接的方法,但不足以准确反映算法的真正效率

为给出 客观 的评判,需要抽象出一个 理想 的平台或模型

图灵机(TM)模型

2.png

例子

功能:将二进制非负整数加一

全 '1' 的后缀翻转为全 '0'
原最低位的 '0' 或 '#' 翻转为 '1'

(<, 1, 0, L, <) // 左行, 1 -> 0
(<, 0, 1, R, >) // 掉头, 0 -> 1
(<, #, 1, R, >) // ?
(>, 0, 0, R, >) // 右行
(>, #, #, L, h) // 复位

3.png

Random Access Machine (RAM) 模型

寄存器顺序编号,总数没有限制

R[0], R[1], R[2], R[3], ...

每一基本操作仅需常熟时间

R[i] <- c
R[i] <- R[j]
IF R[i] = 0 GOTO 1

与 TM 模型一样,RAM 模型也是一般计算工具的简化与抽象,使我们可以独立于具体的平台,对算法的效率做出可信的比较与评判

在这些模型中,算法的运行时间 -> 算法需要执行的基本操作次数

T(n) = 算法为求解规模为 n 的问题,所需执行的基本操作次数

例子

功能:向下取整的除法,0 <= c, 0 < d

4.png

反复地从 R[0] = 1 + c 中减去 R[1] = d
统计在下溢之前,所做减法地次数 x

0 R[3] <- 1           // increment
1 R[0] <- R[0] + R[3] // c++
2 R[0] <- R[0] - R[1] // c -= d
3 R[2] <- R[2] + R[3] // x++
IF R[0] > 0 GOTO 2    // if c > 0 goto 2
R[0] <- R[2] - R[3]   // else x-- and
STOP                  // return R[0] = x = (c/d) 向下取整

5.png

下一篇:《C++ 数据结构(一)绪论(3)复杂度》

Responses
选择表情