TAOCP中的算法分析

Question

好吧，我被难住了。 TAOCP vol1，第 3 版，第 1.3.2 节“MIX 汇编语言”给出了一个简单的汇编程序，用于查找数组的最大值。该程序在第 145 页上给出，连同每条指令被假定执行的次数。在下一页上它说“[...] 执行子程序的时间长度；它是 (5+5n+3A)u [...]”

但是:当您实际对列表中给出的计数求和时，您最终得到 (4+4n+2A) 的因数。这种差异也出现在其他算法中。例如，在1.3.3节程序A的分析中，Knuth写道“通过简单加法[..] (7+5A+...)”。当你实际执行“简单加法”时，你最终得到 (5+3A+...)

这是怎么回事？

---

这里是 MIX 代码，括号中的文本中的计数并排显示。我已将标签名称缩短为两个字符以便于输入

    X EQU 1000
      ORIG 3000
MA    STJ EX      [1]
IN    ENT3 0,1    [1]
      JMP CH      [1]
LO    CMPA X,3    [n-1]
      JGE *+3     [n-1]
CH    ENT2 0,3    [A+1]
      LDA X,3     [A+1]
      DEC3 1      [n]
      J3P LO      [n]
EX    JMP *       [1]

Answer 1

好的，我想出了这个。括号中因素后的“u”提示我:某些指令的执行时间比其他指令长。考虑到这一点后(书中有一张包含指令时间的表格)，一切都会检查出来。