TAOCP算法分析

Question

好吧，我很困惑。TAOCP vol1，第3版，第1.3.2节“混合汇编语言”给出了一个简单的汇编程序来查找数组的最大值。该程序在第145页，连同每条指令应该执行的次数一起给出。在下一页中，它说“.执行子例程的时间长度；它是(5+5n+3A)u .”

但是:当您实际将清单中的计数相加时，最终得到的因子是(4+4n+2A)。这种差异在其他算法中也会出现。例如，在1.3.3节中对程序A的分析中，Knuth写到“通过简单的加法..”。当您实际执行“简单加法”时，您的结果是(5+3A+.)

这里发生什么事情？

下面是混合代码，文本中的计数并排放在括号中。为了便于打字，我把标签名缩短为两个字符。

    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“提示了我:有些指令比其他指令执行时间要长。如果考虑到这一点(书中有一个带有指示时间的表)，所有的内容都会被检查出来。