同じアルゴリズムなのに計算量が違う理由を知りたい。

Question

実現したいこと

計算量が異なる理由を知りたい。

前提

AtCoderのABC376、C問題を解いていました。リンク内容
自分の作成したコードと、回答は実装しようとしていることは同じはずなのですが、
計算量に差があります。

発生している問題・エラーメッセージ

以下の二つのコードの計算量が異なる理由を知りたいです。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define ll long long

int main(){
    int N;

    cin >> N;


    vector<ll> A(N);
    vector<ll> B(N - 1);

    rep(i, N){
        cin >> A[i];

    }

    rep(i, N - 1){
        cin >> B[i];
    
    }

    sort(A.begin(), A.end());

    vector<ll> D = B;
    D.push_back(1 << 30);
    sort(D.begin(), D.end());
    rep(i, N){
        if(D[i] < A[i]){
            cout << -1 << endl;
            return 0;
        }
    }
    ll right = A[N-1];
    ll left = A[0];
    ll val = (right + left) / 2;
    ll ans = 0;
    bool ok = false;
    while(true){
    vector<ll> C = B;
    C.push_back(val);
    sort(C.begin(), C.end());
    ok = true;

    rep(i,N){
        if(C[i] < A[i]){
            ok = false;
        }
        
    }
    if(ok){
        ans = val;
        right = val;
        val = (right + left) / 2;
    }
    else{
        left = val;
        ll reVal = val;
        val = (right + left) / 2;
        if(val == reVal){
            if(ans > 0){
                cout << ans << endl;
                return 0;
            }
        } 
    }

    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define ll long long

int main() {
    int N;
    cin >> N;
    
    vector<ll> A(N);
    vector<ll> B(N - 1);
    rep(i, N) cin >> A[i];
    rep(i, N - 1) cin >> B[i];
    
    sort(A.begin(), A.end());  // Aのソート

    auto canSatisfy = [&](ll x) -> bool {
        vector<ll> C = B;
        C.push_back(x);       
        sort(C.begin(), C.end()); 
        
        rep(i, N) {
            if (C[i] < A[i]) return false; // 条件を満たさない場合
        }
        return true; // 条件を満たす場合
    };

    ll ok = 1 << 30;  // 十分大きい値
    ll ng = 0;        // 最小値

    // ok と ng の二分探索
    if (!canSatisfy(ok)) {
        cout << -1 << endl;  // 最大値でも条件を満たさない場合
        return 0;
    }

    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        if (canSatisfy(mid)) ok = mid;
        else ng = mid;
    }
    
    cout << ok << endl;
    return 0;
}

Comments

[toge_]

2つ質問させてください。

1. 「計算量」というのは「実行時間」のことだと考えればいいでしょうか？いわゆる「ランダウの記号」の意味だと同じ計算量になりそうに見えます。

2. 少なくとも上のコードと下のコードで以下の部分の実行時間が違うことは把握されているでしょうか？
[上のコードの47-52行目]
rep(i,N){
if(C[i] < A[i]){
ok = false;
}
}
[下のコードの22-24行目]
rep(i, N) {
if (C[i] < A[i]) return false; // 条件を満たさない場合
}

[mldo0]

ご質問ありがとうございます。
1.実行時間のことです。
2.上と下の実行時間の違いを理解していません。なぜ違いが生じるのでしょうか。
また、AtCoderで問題を解くにあたり、意識しなければならないほど大きな違いが生まれるのでしょうか。

[toge_]

上のコードだと、強制的にN回分のデータの比較が発生します。
下のコードだと、条件に合致しない場合には即座に処理を終了します。
このため、下のコードの方が確実に高速に動作するロジックになります。
while(true)ループの中で毎回実行される内容のため、支配的ではありませんが、ある程度処理時間に影響を与える可能性があります。

[mldo0]

break文が入っているのと同等ということですね。
言われるまで気づきませんでした。
ご回答ありがとうございました。

Answer 1

上のコードに以下の入力を与えると、okがfalseになることがないため、無限ループに陥ります。

2
1 2
2

二分探索は意外とバグりやすいので、「めぐる式二分探索」を使うことをお勧めします(下のコードでも使われています)。「二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜」の解説が分かりやすいと思います。

追記

上のコードには、問題点が2つあります。上記入力例だと、そのうちの1つしか分からないので、もう1つの問題が分かる入力例も挙げておきます。こちらも無限ループに陥ります。

2
1 2
1

一応、問題点についても説明しておきます。自力で解きたいなら読み飛ばしてください。

1. 条件を満たす場合に停止判定をしていない
   最初に挙げた入力例が無限ループとなる原因。
   条件を満たす場合の停止判定を追加するか、条件を満たさないことが確実な値(A[0]-1など)をleftの初期値に入れれば解決。
2. 条件を満たすのが、最大のおもちゃと同じ大きさの箱だけだった場合、ansが0のまま更新されない
   今回挙げた入力例が無限ループとなる原因。
   そもそも27～35行の判定を通っている時点で、最大のおもちゃと同じ大きさの箱が条件を満たすのは明らかなので、ansの初期値をA[N-1]にすれば解決。(そうすると、ansとrightが常に等しくなるので、ans自体不要となる)

Comments

[mldo0]

無限ループが起こってしまっているのは盲点でした。while(true)には注意が必要ですね...
ありがとうございました。めぐる式を勉強してみます