algorithm - 償却複雑度

Question

私のアルゴリズムのクラスでは、償却された複雑性について説明しました。残念ながら体育大会で不在のため参加できませんでした。教授に連絡してこれを説明しようとして失敗した後、ここで質問することになりました。Amortized Complexity とは何ですか? どうすれば見つけられますか? やるべき仕事を任されたが、どうしたらいいのかわからない。非常に役立つか、他の説明への参照を提供する1つの質問で私を助けることができれば.

問題は次のとおりです。

次のアルゴリズムを検討し、オーバーフローがないと仮定して、n ビットの配列として表される 2 進数に 1 を加算します。

increment is
    local
        i: INTEGER;
    do
        from i:=n until a.item(i) = 0 loop
            a.put(0,i);
            i:=i - 1
        end;
        a.put(1,i)
    end

このアルゴリズムは、最悪の場合、明らかに O(n) です。その償却複雑度が O(1) であることを示します。

最悪のケースが O(n) である理由はわかりますが、償却後の複雑さが O(1) である理由はわかりません。または、そのことについては、償却された複雑さでさえあります。