【第5回】計算量とbit演算

計算量について

アルゴリズム

ある処理を行うプログラムを作るとき、どのように処理を行うのかという計算手順のことをアルゴリズムと呼びます。

例: 1 から n までの和を求めるプログラム
- 1 から n までの数を順番に足していく : n-1 回の計算を行う
- 等差数列の公式を用いて $\dfrac{n(n+1)}{2}$ を計算する : 3 回の計算を行う

このように、同じ処理を行うプログラムでも、複数のアルゴリズムを考えることができます。コンピュータも 1 回の計算には時間がかかるので、処理を早く終わらせるためには、より効率の良いアルゴリズムを考える必要があります。アルゴリズムの大まかな性能を表す指標として、計算量というものがあります。

計算量

プログラムは入力に対して必要な計算を行い結果を出力する。この時の計算時間や記憶領域の量がどのくらい変化するのかが計算量です。計算量には、時間計算量と空間計算量があります。

時間計算量: 計算の回数
空間計算量: 必要な記憶領域の量

たんに計算量という時は、時間計算量をさすことが多いです。

先ほどの 1 から n までの和を求めるプログラムの例で考えてみよう。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int sum=0;
    for(int i=1;i<=N;i++){
        sum+=i;
    }
    cout<<sum<<endl;
}

このプログラムでは、for 文を n 回繰り返しているので、計算回数はおおよそ n 回になります。このとき時間計算量はオーダー記法を用いて $O(n)$ と表します。このように、計算量を表すときには、計算回数ではなく、計算回数のオーダーを表します。

オーダー記法

厳密に時間計算量、空間計算量を求めることは大変です。そこでざっくりと計算量を表すために、オーダー記法 $O()$ を用います。

例: $3N^3+10N^2+2$ $3 N^{3} + 10 N^{2} + 2$ という式があったとき、 $O(N^3)$ $O (N^{3})$ と表す。
- 定数倍は無視する
- N が大きくなった時、最も影響が大きい項のみを考える

$N=1000$ の時、 $N^3=1000000000=10^9$ , $N^2=1000000=10^6$ であり、 $N^3$ は $N^2$ の量を無視できるほど大きいので $O(N^3)$ と表します。 $N$ を無限大に近づけた時の発散スピードを考えるとイメージしやすいかもしれません。

Plot

この図を見ると計算量の大まかなイメージがつかめると思います。

$O(1) < O(\log N) < O(N) < O(N\log N) < O(N^2) < O(2^N) < O(N!)$

例題

以下の式のオーダー記法を答えよ。

$N+100$
$3N^2+2N+1$
$10+2$
$2^N+N^3+N$
$N!+N^2+1$
$N \log N+N$
$N^2+N^2\log N$

答え

$O(N)$
$O(N^2)$
$O(1)$
$O(N^3)$
$O(N!)$
$O(N\log N)$
$O(N^2\log N)$

コードを見て、計算量を考えよう

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int sum=0;
    for(int i=1;i<=N;i++){
        sum+=i;
    }
    cout<<sum<<endl;
}

答え

さっき出てきたコードを同じです。これは for 文で処理を $N$ 回繰り返しているので、 $O(N)$ であらわされます。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int sum=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            sum+=i*j;
        }
    }
    cout<<sum<<endl;
}

答え

このコードは for 文が 2 重になっているので、 $O(N^2)$ であらわされます。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int count=0;
    while(N>0){
        N/=2;
        count++;
    }
    cout<<count<<endl;
}

答え

このコードは $N$ を $2$ で割り続けているので、 $N$ を割る回数を $x$ とすると $N \Bigl( \dfrac{1}{2} \Bigr) ^x = 1$ で表せます。この式の両辺を $\log$ をとると、 $x=\log_2 N$ となります。よって、 $O(\log N)$ であらわされます。計算量の $\log$ は底はなんでもいいです。底の変換公式より、 $\log_a N =\dfrac{\log_b N}{\log_b a}$ なので、定数とみなせます。今回は、 $\log_2 N$ になります。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    int count=0;
    vector<int> a(N);
    rep(i,N){
        cin>>a[i];
    }
    do{
        count++;
    }while(next_permutation(a.begin(),a.end()));
    cout<<count<<endl; //N!
}

答え

このコードは、 $N$ 個の数列の順列を全て列挙しています。順列の数は $N!$ なので、 $O(N!)$ であらわされます。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) cout << a.at(i) << " \n"[i == n - 1];
  return 0;
}

sort の計算量はいくらでしょう。下記のレファレンスを読んでみると... https://cpprefjp.github.io/reference/algorithm/sort.html

答え

$O(N\log N)$ と記載があります。二つの for 文は $O(N)$ なので、全体の計算量は $O(N\log N)$ になります。

#include <bits/stdc++.h>
using namespace std;

int f(int x) {
  int sum = 0;
  for (int i = 0; i < x; i++) sum += i;
  return sum;
}

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  for (int i = 0; i < n; i++) sum += f(i);
  cout << sum << endl;
  return 0;
}

答え

このコードは、 $f(x)$ を $n$ 回呼び出しています。 $f(x)$ の計算量は $O(x)$ なので、 $O(N^2)$ であらわされます。

競プロでの計算量

「実行時間制限」、「メモリ制限」があるので計算量をよく考えます。基本的には、1 秒あたり $10^8$ ~ $10^9$ あたりまでは許されます。

$O(10^8)$ : まあ行ける
$O(10^9)$ : 単純な処理、加算、減算くらいならいける
$O(10^{10})$ : まあムリ

目安

制約	間に合うオーダー	使うアルゴリズム例
$N\le 10$	$O(N!)$	順列全探索
$N\le 25$	$O(2^N)$	bit 全探索
$N\le 200$	$O(N^3)$	ワーシャルフロイド
$N\le 10^4$	$O(N^2)$	二重ループ
$N\le 10^5$	$O(N\log N)$	ソート
$N\le 10^8$	$O(N)$	線形探索
$N\le 10^{14}$	$O(\sqrt{N})$	素数判定
それ以上	$O(\log N)$	二分探索
	$O(1)$	定数時間

練習問題

解説

 int f0(int N) {
  return 1;
}

これは $O(1)$ です。 $N$ に関係なく、常に 1 回の計算で終わります。

int f1(int N, int M) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    s++;
  }
  for (int i = 0; i < M; i++) {
    s++;
  }
  return s;
}

これは $O(N+M)$ です。 $N$ と $M$ の値によって計算回数が変わります。

int f2(int N) {
  int s = 0;
  for (int i = 0; i < N; i++) {
      int t = N;
      int cnt = 0;
      while (t > 0) {
        cnt++;
        t /= 2;
      }
      s += cnt;
  }
  return s;
}

これは $O(N\log N)$ です。 $\log N$ を $N$ 回繰り返しているので、 $N\log N$ になります。

int f3(int N) {
  int s = 0;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      s++;
    }
  }
  return s;
}

これは $O(1)$ です。 $N$ に関係なく、9 回の計算で終わります。

int f4(int N) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      s += i + j;
    }
  }
  return s;
}

これは $O(N^2)$ です。 $N$ を 2 重に繰り返しているので、 $N^2$ になります。

int f5(int N, int M) {
  int s = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      s += i + j;
    }
  }
  return s;
}

これは $O(NM)$ です。 $N$ と $M$ を 2 重に繰り返しているので、 $NM$ になります。

bit 演算

bit

コンピュータは、0 と 1 の 2 進数で情報を表します。0 か 1 の 2 通りで表せる情報の最小単位をbitと呼びます。bit は、binary digitの略です。

bit 演算子

bit 演算で主に使うものは以下の 6 つ

AND: &
OR: |
XOR: ^
NOT: ~
左シフト: <<
右シフト: >>

bool の AND&&,OR||との区別を理解しておこう。特に、bit ごとの演算は「bitwise 〇〇」という言い方をする。

AND

2 つの bit がともに 1 のときのみ 1 を返す演算子です。

`x`	`y`	`x & y`
0	0	0
0	1	0
1	0	0
1	1	1

$10$ & $12=1010_{(2)}$ & $1100_{(2)} = 1000_{(2)}$
$10$ & $5=1010_{(2)}$ & $0101_{(2)} = 0000_{(2)}$

OR

2 つの bit のどちらかが 1 のとき 1 を返す演算子です。

`x`	`y`	`x \| y`
0	0	0
0	1	1
1	0	1
1	1	1

$10$ | $12=1010_{(2)}$ | $1100_{(2)} = 1110_{(2)}$
$10$ | $5=1010_{(2)}$ | $0101_{(2)} = 1111_{(2)}$

XOR

2 つの bit が異なるとき 1 を返す演算子です。

`x`	`y`	`x ^ y`
0	0	0
0	1	1
1	0	1
1	1	0

$10$ ^ $12=1010_{(2)}$ ^ $1100_{(2)} = 0110_{(2)}$
$10$ ^ $5=1010_{(2)}$ ^ $0101_{(2)} = 1111_{(2)}$

NOT

bit を反転させる演算子です。

`x`	`~x`
0	1
1	0

~ $10$ = ~ $1010_{(2)}$ = $0101_{(2)}$

左シフト

bit を左にシフトさせる演算子です。右側に 0 が追加されます。 x<<nと書いたとき、 $x$ に $2^n$ を掛けることと同じです。

$10$ << $2$ = $1010_{(2)}$ << $2$ = $101000_{(2)}$ = $40$

右シフト

bit を右にシフトさせる演算子です。左側に 0 が追加されます。 x>>nと書いたとき、 $2^n$ で割ることと同じです。ただし、小数点以下は切り捨てになります。

$10$ >> $2$ = $1010_{(2)}$ >> $2$ = $10_{(2)}$ = $2$

複合代入演算子

演算	演算子
AND	`&=`
OR	`\|=`
XOR	`^=`
左シフト	`<<=`
右シフト	`>>=`

NOT の複合代入演算子はありません。

bit 演算の注意

符号あり整数型の場合(int,long long)、最上位 bit は符号を表すので、想定外の処理が起こることがあります。 bit 演算を行うときは、気を付けて演算をするか、符号なし整数型(unsigned int,unsigned long long)を使うか後で説明する bitset を使いましょう。

bit 全探索

AtCoder でよく出ます。bit 全探索とは、bit を使って全探索を行う方法です。bit 全探索は、 $2^N$ 通りの組み合わせを全て試すことができます。シフト演算と AND 演算が理解できていれば分かります。

例題

$1,2,4$ の中から自由に数字を選び、選び出した数字の和でいくつの数字を作ることができるか。一つも選ばない場合は 0 になる。

考え方

3 つのこの数字を選ぶ、選ばないの 2 パターンを bit で表す。 $0$ から $2^n-1$ まで(今回は $2^3-1$ まで)調べる。

数字	4	2	1	作られる数字
$0(000_{(2)})$	x	x	x	0
$1(001_{(2)})$	x	x	o	1
$2(010_{(2)})$	x	o	x	2
$3(011_{(2)})$	x	o	o	3
$4(100_{(2)})$	o	x	x	4
$5(101_{(2)})$	o	x	o	5
$6(110_{(2)})$	o	o	x	6
$7(111_{(2)})$	o	o	o	7

コード

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> a={1,2,4};
    int n=3;
    for(int bit=0;bit<(1<<n);bit++){ // 1<<nは2^n
        int sum=0;
        for(int i=0;i<n;i++){
            if(bit&(1<<i)){ // bitのi番目のbitが立っているかどうか
                sum+=a[i];
            }
        }
        cout<<sum<<endl;
    }
}

練習問題

ヒント

問題の言っていることは、選び出した集合の中に $1$ から $N$ までの数字が全て含まれていますかということ。
集合は set で扱います。

解答例


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<set<int>> a(m);
    for (int i = 0; i < m; i++)
    {
        int size = 0;
        cin >> size;
        for (int j = 0; j < size; j++)
        {
            int x;
            cin >> x;
            a[i].insert(x);
        }
    }

    int ans = 0;
    for (int bit = 0; bit < (1 << m); bit++) // 0 ~ 2^m - 1くりかえす
    {
        set<int> s;
        for (int i = 0; i < m; i++)
        {
            if (bit & (1 << i))  // bitのi番目のフラグが立っているかどうか
            {
                for (auto x : a[i])
                {
                    s.insert(x);
                }
            }
        }
        if ((int)s.size() == n)  // setは重複を許さない集合なので,setのsizeが
                                 // nであるとき1からnまでの全ての数字が含まれている
        {
            ans++;
        }
    }
    cout << ans << endl;
}

bitset

int 型は $32$ bit, long long 型は $64$ bit までしか扱えない。
bitset は,任意の長さの bit 列を扱うことができる。

宣言

bitset<長さ> 変数名;  // 長さは定数である必要がある
bitset<n> bs; // このような書き方はできません
bitset<4> bs; // 4bitのbit列
bitset<4> bs("1010"); // 4bitのbit列で初期化

代入

bs=5; // 5=101
bs=bitset<4>("1010");
bs=0b1010; // 0bで2進数を表すことができる

演算

bitset は bit 演算の演算子はすべて使える。

メソッド

メソッド	説明
.count()	1 の数を数える
.set()	全ての bit を 1 にする
.set(i,j)	i 番目の bit を j にする
.reset()	全ての bit を 0 にする
.reset(i)	i 番目の bit を 0 にする
.flip()	全ての bit を反転する
.flip(i)	i 番目の bit を反転する
.to_string()	bitset を文字列に変換する

【第5回】計算量とbit演算

計算量について

アルゴリズム

計算量

オーダー記法

例題

コードを見て、計算量を考えよう

競プロでの計算量

目安

練習問題

bit 演算

bit

bit 演算子

AND

OR

XOR

NOT

左シフト

右シフト

複合代入演算子

bit 演算の注意

bit 全探索

例題

考え方

コード

練習問題

bitset

宣言

代入

演算

メソッド

【第4回】便利なデータ構造

【第6回】累積和で高速処理をしてみよう