これは、CLRS の数論の章からのものです。
a/b結果qとリマインダ付きのバイナリ「紙と鉛筆」の長除算がビットの操作を行うrことを証明するように求められます。O((1+lgq)lgb)
私の見方ではb、 の各ビットに対して を 1 減算しqます。bしたがって、減算がlgb演算 ( の各ビットに対して 1 つ) を行うと仮定すると、演算bの合計が得O(lgblgq)られますが、これは要求されたものではありません。
最初に行う減算操作の結果が 0 ビットになる可能性があることを考慮すると (たとえば、100b を 11b で割る)、1 をlgq加算してこの減算を補正できます。しかし...減算自体についても同じことが言えます-数値に応じて操作lgbを行うことも、操作を行うこともできます（100bと11bの例では、2番目の減算は100b-11bになり、完了するまでに3回の操作が必要です） lg(b)+1.
したがって、これらのケースを因数分解すると、操作の数は になりますO((1+lgb)(1+lgq))。
問題は、部門がO((1+lgq)lgb)操作を行うことをどのように示すことができるかということです。