邓俊辉<<数据结构>>-公开课-01-B

发表于

功能：
算法:
规范：图灵机复位h的原因。 => 在软件中叫做接口

RAM: Random Access Machine
共同之处：无限的空间。
寄存器：

  • 常数赋值给RAM
  • RAM之间直接赋值 R[i] < R[j]
  • RAM之间间接赋值 R[i] <- R[R[j]]
  • RAM+-
  • 判断0跳转 IF R[i] = 0 GOTO l
  • 判断正跳转 > 0
  • 跳转
  • 停止 STOP

概括:
对计算工具抽象后的简化。
独立于环境和平台，可评判效率。

  • 将执行时间，转化为操作次数。T(n) = 算法为求求解规模为n问题的，所需执行次数

  • 这个次数是清晰的，可度量的。

RAM实例:Floor
向下取整除法, 0 <= c, 0 < d
c%d = max {x | dc <= c}
= max {x | dx < 1+c}

R[0] = c+1, R[1] = d

0, R[0] <- c // int c = c;
1, R[1] <- d // int d = d;
2, R[2] <- 0 // int x = 0;
3, R[3] <- 1 // int a = 1;
4, R[0] <- R[0] + R[2] // c++
6, R[0] <- R[0] - R[1] // c-=d
7, R[2] <- R[2] + R[3] // x++
8, IF R[0] > 0 GOTO 4 // if c > 0 goto 4
9, R[0] <- R[2] - R[3] // else x– and;
9, STOP // return R[0] = x

src: