アルゴリズムの時間複雑さを決定する

Question

私はAがすべての反復でkの値によって減分されている問題に取り組んでいます。 Kは繰り返しごとに倍増します。例えば、

A = 30→29→27→23→15→0 デルタ= 1→2→4→8→16

このアルゴリズムの時間の複雑さをどのように評価できますか？私は、デルタの倍増のためにO（logN）に関連しなければならないが、直感的に/数学的にどのように結論に到達するかはわからないと思う。

Answer 1

Nの合計サイズがデクリメントは、2^Nである1 - （誘導によってこれを証明する）、それは数場合デクリメントが0

Answer 2

に到達するCEIL（LOG2（A + 1））を取るAからなりますnで総減少分ステップするので、それは、non-positive値を取得するために、正確にn措置をとるだろう、2^nと2^(n-1)の間にある、すなわち、2^(n-1) <= A < 2^nは（n上で使用する誘導が証明する）1+2+..+2^(n-1)=2^n-1です。したがって、時間複雑度= n = lg 2^n = 1 + lg 2^(n-1) <= 1 + lg(A)、lgはlogbase 2です。