algorithm - スライディング ウィンドウ最小アルゴリズム

Question

これは宿題の問題です。A[] を整数の配列とし、整数 K -- ウィンドウ サイズ。A の上をスライドするウィンドウに表示される最小値の配列 M を生成します。この問題の解決策を記載した記事を見つけましたが、 O(n) の複雑さがある理由がわかりませんでした。誰か説明してくれませんか？

Answer 1

これは人々を捕まえる傾向があります。O(N^2)追加に時間がかかり、要素があるため、時間O(N)がO(N)かかると考えるでしょう。ただし、各要素は一度しか追加できず、一度しか削除できないことに注意してください。したがって、O(N)全体として、配列全体をスライドする必要がありAます。

O(1)これにより、スライディング ウィンドウを 1 要素分移動するたびに、償却効率が得られます。つまり、スライディング ウィンドウを 1 要素分移動するのにかかる平均時間は ですO(1)。