这是来自 CLRS 的数论章节。
我们被要求证明a/b带有结果q和提示的二进制“纸和铅笔”长除法r对O((1+lgq)lgb)位进行操作。
我看到它的方式是我们b对q. 因此，假设减法b执行lgb操作（对于 中的每个位一个b），那么我们总共有O(lgblgq)操作，这不是所要求的。
如果您考虑到您执行的第一个减法运算可能会导致 0 位（例如，将 100b 除以 11b），那么，好的，您可以加 1lgq来补偿这个减法。但是......减法本身也可以这样说 - 它可以进行lgb运算，也可以lg(b)+1根据数字进行运算（在 100b 和 11b 示例中，第二次减法将是 100b-11b 需要 3 次运算才能完成） .
所以如果我们考虑这些情况，那么操作的数量应该是O((1+lgb)(1+lgq)).
所以问题是，你怎么能证明这个部门有O((1+lgq)lgb)行动呢？