binary_search の計算量について

グラフの探索のコードを書いていたところ、どうしても実行時間を減らせない場合に遭遇しました。
試行錯誤した結果、binary_search を使っていたことが問題だということが分かりました。
binary_search を使用すると、5000msかかっていたコードが、count を採用すると、150msで終わりました。
計算量について自分で調べた限りだと、binary_serch の計算量は log2(last - first) であり、
一方の count は last - first であると認識しています。
それを踏まえると、binary_serchを使った方が高速であると考えていたのですが、予想に反する結果になりました。
それ以上の情報は探せず、理由が分からずにいます。
もしご存じの方がいたら、ご教授いただけたらと思います。

c++
1//コード1 binary_search
2
3#include "bits/stdc++.h"
4using namespace std;
5#define rep(i, a, n) for(int i = (int)(a); i < (int)(n); i++)
6//------------------------------------------------------------------------------------------------------------------------------------------//
7
8int main() {
9
10    clock_t start = clock();
11
12    int node = 0;
13    int edge = 0;
14    cin >> node >> edge;
15
16    vector<vector<int>> list(node + 1);
17    rep(i, 0, edge) {
18        int inputA = 0;
19        int inputB = 0;
20        cin >> inputA >> inputB;
21        list[inputA].push_back(inputB);
22
23    }
24    int ans = 0;
25    for (int i = 1; i < node + 1; i++) {
26        queue<int> que;
27        que.push(i);
28        set<int> visited;
29        visited.insert(i);
30        while (que.size() != 0) {
31            int num = que.front();
32            que.pop();
33            for (int j : list[num]) {
34
35                //該当箇所//
36                if (binary_search(visited.begin(),visited.end(), j) == 0) {
37                    que.push(j);
38                    visited.insert(j);
39                }
40
41            }
42        }
43        ans += visited.size();
44    }
45
46    cout << ans << endl;
47
48    clock_t end = clock();
49    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
50    printf("time %lf[ms]\n", time);
51}
52

691603
time 5315.307000[ms]

c++
1//コード2 count
2
3#include "bits/stdc++.h"
4using namespace std;
5#define rep(i, a, n) for(int i = (int)(a); i < (int)(n); i++)
6//------------------------------------------------------------------------------------------------------------------------------------------//
7
8int main() {
9
10    int node = 0;
11    int edge = 0;
12    cin >> node >> edge;
13
14    vector<vector<int>> list(node + 1);
15    rep(i, 0, edge) {
16        int inputA = 0;
17        int inputB = 0;
18        cin >> inputA >> inputB;
19        list[inputA].push_back(inputB);
20
21    }
22    int ans = 0;
23    for (int i = 1; i < node + 1; i++) {
24        queue<int> que;
25        que.push(i);
26        set<int> visited;
27        visited.insert(i);
28        while (que.size() != 0) {
29            int num = que.front();
30            que.pop();
31            for (int j : list[num]) {
32
33                //該当箇所//
34                if (visited.count(j) == 0) {
35                    que.push(j);
36                    visited.insert(j);
37                }
38
39            }
40        }
41        ans += visited.size();
42    }
43
44    cout << ans << endl;
45}
46

691603
time 150.059000[ms]

行動規範の内容に同意します

回答1件

ベストアンサー

binary_searchの計算量は、ランダムアクセスイテレータならO(log N)ですが、そうでなければO(N)となります。

Complexity
On average, logarithmic in the distance between first and last: Performs approximately log2(N)+2 element comparisons (where N is this distance).
On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

binary_search - C++ Reference

setのイテレータは双方向イテレータであり、ランダムアクセスイテレータではないのでbinary_searchはO(N)となります。