しゃくとり法の計算量はなぜO(n)となるのか

Question

知りたいこと

なぜしゃくとり法の計算量はなぜO(n)となるのですか？

前提

競技プログラミングをC++で学んでいます。

調べたこと

以下の2つのサイトの内容を読みましたが、私はしっかりと理解することができませんでした。
https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4
https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

自分で考えたこと(追記)

以下のコードは「N個の小さい順に並んだ整数A1, A2, A3,...,ANの中から2つの整数のペアを選ぶ方法の中から差がK以下となる選び方は何通りあるか」という問題を解くコードです。
<制約>
・1 <= N <= 100000
・1 <= K <= 10^9
・1 <= A1 < A2 < ... < AN <= 10^9

#include <iostream>
using namespace std;

int N, K;
int A[100009], R[100009];

int main() {
	// 入力
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];

	// しゃくとり法
	for (int i = 1; i <= N - 1; i++) {                                      //---(1)
		// スタート地点を決める
		if (i == 1) R[i] = 1;
		else R[i] = R[i - 1];

		// ギリギリまで増やしていく
		while (R[i] < N && A[R[i] + 1] - A[i] <= K) {           //---(2)
			R[i] += 1;
		}
	}

	// 出力
	long long Answer = 0;
	for (int i = 1; i <= N - 1; i++) Answer += (R[i] - i);
	cout << Answer << endl;
	return 0;
}

「競技プログラミングの鉄則　米田優峻[著]」3.3 しゃくとり法の問題A13から引用
問題:
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m
解答コード:
https://github.com/E869120/kyopro-tessoku/blob/main/codes/cpp/chap03/answer_A13.cpp

私の考えではこのしゃくとり法の計算量は(forループの計算量(1)) * (最も内側のwhileのループの計算量(2))が(n - 1)(n - ?)のような形になり、O(n^2)となるように思います。これは結局、(n - 1)(n - ?)< n^2ってことで、だから、O(n^2)にはならず、O(n)だという話なのでしょうか？

---

私の考えにどんな間違いがあるのか、なぜ計算量O(n)となるのかを教えてくださると幸いです。私自身混乱しているところも多くあると思いますので、そこも含めてご指摘お願いいたします。

Comments

[ozwk]

Qiitaのほうで
> トータルで見ると結局「2 つのポインタを左から右まで動かした」ということに過ぎないです。すなわち計算量は O(n) になります。
とありますがこの説明で納得できませんか?

[fana]

O(n) であることに疑問がある，ということですが，であれば
「あなたの考えによると　計算量はどうなるのでしょう？」
という話をすべきでしょう．
（そうしないと，あなたの疑問に見合った回答が得られ難いのではないでしょうか？）

[FIREMAX]

fanaさん、ご指摘ありがとうございます。編集してみました。

[actorbug]

追記のコードですが「差がKとなる選び方」ではなく「差がK「以下」となる選び方」を求めるコードではないでしょうか。
おそらく、書籍「競技プログラミングの鉄則」の「3.3 しゃくとり法」からの引用だと思われますが、引用元は明記しておくべきだと思います。
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m
https://github.com/E869120/kyopro-tessoku/blob/main/codes/cpp/chap03/answer_A13.cpp

[FIREMAX]

actorbugさん、ご指摘ありがとうございます。編集しました。

Answer 1

けんちょん氏のページの2つ目のコードを引用させていただいて説明します。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力受け取り */
    int n, Q;
    cin >> n >> Q;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    /* Q 回分のクエリを処理 */
    for (int j = 0; j < Q; ++j) {
        long long x; cin >> x; // 各クエリ x

        /* 合計値 */
        long long res = 0;

        /* 区間の左端 left で場合分け */
        int right = 0;     // 毎回 right を使い回すようにする
        long long sum = 0; // sum も使い回す
        for (int left = 0; left < n; ++left) {
            /* sum に a[right] を加えても大丈夫なら right を動かす */
            while (right < n && sum + a[right] <= x) {
                sum += a[right];
                ++right;
            }

            /* break した状態で right は条件を満たす最大 */
            res += (right - left);

            /* left をインクリメントする準備 */
            if (right == left) ++right; // right が left に重なったら right も動かす
            else sum -= a[left]; // left のみがインクリメントされるので sum から a[left] を引く
        }

        cout << res << endl;
    }
}

念のため説明しますが、このコード全体がO(n)というわけではありません。O(n)なのは、22～35行目のループです。コード全体だとクエリがQ個なのでO(Qn)です。

さて、22行目から35行目のループを考えたときに、最も多くの回数実行されるコードは、一番内側のループ内(25～26行目)となります。一番内側のループで注目すべきは、26行目の++rightになります。22～35行目のループ内を見ると分かりますが、rightはループ内で増える一方で、減ることは一切ありません。また、24行目のループ継続条件にright < nが含まれるので、rightがnまで増えると、一番内側のループは実行されません。その条件下で、26行目の++rightが最大何回実行されうるか考えると、n回までしか実行できないことが分かります。最も多くの回数実行される一番内側のループ内のコードが最大n回までしか実行されないことと、22～35行目のループ自体も最大n回までしか実行されないことから、O(n)であるということができます。

Comments

[FIREMAX]

回答ありがとうございます。「最も多くの回数実行される一番内側のループ内のコードが最大n回までしか実行されないことと、22～35行目のループ自体も最大n回までしか実行されないことから、O(n)であるということができます。」の部分がうまく理解できません。n * n=n^2となり、O(n^2)となってしまう気がするのですが・・・。

[actorbug]

外側のループがn回回る間に、内側のループが「合計」n回しか回らない、ということです。
外側のループ1回ごとに、内側のループも何回か回ることになるでしょう。1回も回らないこともあれば、数回回ることもあるでしょう。しかし、その回数をすべて合計した結果は、最大でn回にしかならない、という主張です。

[FIREMAX]

自分が完璧に理解できているか分からないので、以下の2つの考えが正しいか確認したいです。

①actorbugさんの提供してくださったコードでは同じforループ内で、rightがポインタを進み、後ろはleftを使ってsumから引いてあげることで、自動的にしゃくとりの始点が変化し(たのと同じような意味になる)、またrightが進み続けるので、しゃくとり法の動作をしている部分の操作はn回で計算量O(n)となる。②私の質問に追記で添付した問題を解くコードは「差がKとなる2つの整数のペアの選び方」を問う問題であることから、ポインタが前に進むときにしかR[i]は増やされないので、そもそもペアを考えることができない末尾の分を抜いて、操作がn-1回なので、こちらも計算量O(n)となる。

間違っている点や気になる点がありましたら、教えてください。間違えた理解をしたくないので。

[actorbug]

言ってることは正しいですが、何かもやもやを感じます。

計算量というのは、ざっくり言うと、コードの計算ステップ数を表すものです。
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0#1-1-%E8%A8%88%E7%AE%97%E9%87%8F%E3%82%AA%E3%83%BC%E3%83%80%E3%83%BC

コード内の各行が、最大でもn回しか実行されなければO(n)みたいな話です。
そちらでデバッガを使えるか分かりませんが、特定行にブレークポイントを設置して実行したときに、終了までにブレークポイントでn回しか止まらない、という感覚です。
(正確に言うと、内側のループの条件判定部分は2n回止まりますが、nの定数倍ということでO(n)なのは変わりません)

コードをベースに説明していないことが、もやもやする原因だと思います。
まあ、個人的な感情にすぎないので、無視していただいて構いません。

[FIREMAX]

返信ありがとうございました。完全には理解できていないかもしれませんが、actorbugさんの回答でしゃくとり法の計算量について自分のもやもやが晴れたので、ベストアンサーに選ばさせてください。

Answer 2

（おことわり：この「しゃくとり法」という語を初めて聞いたレベルのど素人なので，盛大に間違っているかもしれません）

---

長さ n のデータ列があって，その全ての部分データ列を愚直に調べねばならないことを考えると……
部分列の左端の位置 left の取り得る位置が n パターンあって，
右端の位置 right の法はざっくりと n/2 パターンかな？ （left よりも左側には行かないから）
…というわけで，ざっくりと n * n/2 パターンくらい頑張らなきゃならなくて，オーダとしては O(n*n) である，と．

---

対して，解くべき問題次第では，何らかの問題固有の性質を利用することで（上記のような全探索をせずに済んで）ざっくりと以下のような探索で済む場合というのがあって，これを「しゃくとり法」と呼ぶらしい．

left = right = 0;  //最初は両者左端
while( left<n )  //※終了条件が正しいかはちょっと自信ないけど
{
  //ループ内では状況次第で以下の３パターンのうちのいずれかの操作を行う．
  //要は｛範囲の右側を伸ばす，範囲の左側を縮める，範囲をオフセットする｝のどれかをやる，っていう．
  (1) ++right
  (2) ++left
  (3) (1)と(2)の両方
}

もちろん（言うまでも無く），ループ内では

• right が激しく範囲外まで進んだりしない
• left が right を超えることはない

みたいな条件を満たす形で操作を選択する．
で，これの計算量のオーダが O(n) というのが信じられない，と．

……そしたらまずは以下を考えてみてはどうか

left = 0;  //leftしかない
while( left<n )  //※終了条件が正しいかはちょっと自信ないけど
{
  //ループ内でやれることは以下の１パターンのみ
  //（※話がわかりやすいように，↑の疑似コードと同様に「(2)」とかしてあるけど）
  (2) ++left
}

これなら頑張らなきゃならないパターン数は n パターンだ．→だから O(n) だよね．

じゃあこれ↓は？

left = right = 0;  //最初は両者左端
while( left<n )  //※終了条件が正しいかはちょっと自信ないけど
{
  //ループ内では状況次第で以下の2パターンのうちのいずれかの操作を行う
  //※ただし left が right を追い越さないようにする
  (1) ++right
  (2) ++left
}

さっきは left しかいなかったけど，今回は left と right の二人がいるから，
頑張らなきゃならないパターン数は 2*n くらいだよね．そしたらこれも O(n) だ．

最初の疑似コードはこれに「(3)」という「より早く処理が終わる方向のオプション」が加わっているだけの話と見ることができそうだよね．
言わば，計算回数的に最悪の場合(?)を考えれば一度もこの「(3)」を選択しないかもしれないということだよね．
そしたら結局，オーダは「(1)と(2)しかない場合」と同じってことだよね．

……っていう感じでどうかな？

Comments

[FIREMAX]

ご回答ありがとうございます。fanaさんのおっしゃりたいことは分かる気がします。しかし、私が実例のコードを載せなかったばっかりに具体的な層で話すことを阻んでいるように感じました。なので、質問者と回答者の双方の理解を助けるために質問の方に実例のコードを添付しようと思います。

[fana]

> 具体的な層

というのがどういう意味かわからないけれども，「なんとか法の計算量」の話をするにおいては，具体的に解く問題の内容みたいなのは不要だよね．
「とにかく　しゃくとり法なるアルゴリズム　で何らかの問題を解く場面の計算量」ってのはこうだよね，っていう話をしてるんだよね？

で，この回答内における「しゃくとり法　ってこういう方法なんだよね？」っていう理解が間違っていないのであれば，これ以上何を話す必要があるのだろうか？　……というのがわからない感じ．

「具体例に即したほうが話がわかりやすい」的なことはあり得るだろうけども……
何らかの具定的な問題に即した話をすると，今度はその話がその問題のみに当てはまる話なのかそれとも…　みたいな点が逆にぼんやりしてしまうんじゃないかな．

[fana]

質問文内に追加されたコード例は，なんというか，「あえて/わざわざ/etc...」２重ループの形で書いてあるかのように見えてしまうなぁ．
この回答内の擬似コードのような愚直な形（１つのループ内で操作を選ぶ形）に書き換えられないか？　を考えてみると良いんじゃないかな．

[FIREMAX]

返信ありがとうございます。fanaさんの言う通り、具体的なコード例を示したことで、話を冗長させ、論点を抑えにくくしてしまう恐れはありました。fanaさんはコードの動作を単純化して擬似コードとし、コードがとりえる操作の数や計算量を分かりやすく教えてくださろうとしたのだと思います。しかし、私は具体的な例を通して細かい動きまで確認してから、抽象的な見方へと移っていく方が分かりやすいかなと思いました。ただ、自分の質問の仕方の悪さと学習不足がfanaさんに混乱を招いてしまったところもあるので、そこは本当に申し訳ないです。fanaさんの考えは完璧に理解することはできていないかもしれませんが、他の記事や回答の内容を理解するのに大変助かりました。改めてありがとうございました。