知りたいこと
なぜしゃくとり法の計算量はなぜ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
C++
1#include <iostream> 2using namespace std; 3 4int N, K; 5int A[100009], R[100009]; 6 7int main() { 8 // 入力 9 cin >> N >> K; 10 for (int i = 1; i <= N; i++) cin >> A[i]; 11 12 // しゃくとり法 13 for (int i = 1; i <= N - 1; i++) { //---(1) 14 // スタート地点を決める 15 if (i == 1) R[i] = 1; 16 else R[i] = R[i - 1]; 17 18 // ギリギリまで増やしていく 19 while (R[i] < N && A[R[i] + 1] - A[i] <= K) { //---(2) 20 R[i] += 1; 21 } 22 } 23 24 // 出力 25 long long Answer = 0; 26 for (int i = 1; i <= N - 1; i++) Answer += (R[i] - i); 27 cout << Answer << endl; 28 return 0; 29}
「競技プログラミングの鉄則 米田優峻[著]」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)となるのかを教えてくださると幸いです。私自身混乱しているところも多くあると思いますので、そこも含めてご指摘お願いいたします。
![guest](/img/icon/icnUserSample.jpg)
回答2件
あなたの回答
tips
プレビュー