スライディングウィンドウとは？
すらいでぃんぐうぃんどう
データの連続した部分列を一定サイズの「窓」でずらしながら処理するアルゴリズムの手法です。
スライディングウィンドウ（Sliding Window）とは、配列や文字列などの線形データ構造に対して、一定サイズまたは可変サイズの「窓（ウィンドウ）」を端から端へとスライドさせながら部分列を処理するアルゴリズム的手法です。
素朴に全部分列を列挙すると計算量がO(n²)以上になるような問題でも、ウィンドウを1ステップずつ移動させる際に「追加された要素」と「取り除かれた要素」だけを差分更新することで、全体としてO(n)やO(n log n)程度の計算量に抑えられます。この効率性が最大の利点です。
代表的な適用例としては、固定サイズウィンドウでは「配列の中で連続するk個の要素の合計・最大値を求める」問題があります。可変サイズウィンドウでは「合計がSになる最短の部分配列を求める」や「重複しない最長の部分文字列を求める」といった問題に使われます。ネットワークのフロー制御（TCPのスライディングウィンドウプロトコル）にも同名の概念が採用されており、送信済みだが未確認のパケットを管理する仕組みとして機能します。
競技プログラミングや実用的なシステム設計の両面でよく登場する重要な考え方であり、動的計画法や二分探索と組み合わせて使われることもあります。
使い方・例文
配列の中で合計が最大になる連続したk個の要素をスライディングウィンドウで求め、O(n)の計算量で解いた。TCPではスライディングウィンドウによって受信確認を待たずに複数パケットを連続送信できる。
この用語をシェア
最終更新: