[アルゴリズムとデータ構造]第2回 計算量

作成日：2023年1月12日 更新日：2023年1月12日

計算量を学ぼう！

ぱうえる（けんた）:link:

速いコードが書きたい！

でも速いコードってどうやって評価する？？

  • 「 個のデータに対して 秒で終了しました！」
    • データの個数が変わったらどうなる？？
    • そもそもPythonで実行するかC言語で実行するかでも変わりそう

「データの大きさ」や「実行する環境」に依存しない評価方法が必要
→計算量の出番

オーダー記法 (1/2)

x_x2_x3.png (55.1 kB)
  • では が大きくなったとき
    値が大きく変化する
  • 定数倍を考えないで、 の項だけに
    注目すればいいのでは？？

→ (ランダウの記号)を用いる

オーダー記法 (2/2)

  • 計算量は基本的にオーダー記法で書く
    1. 一番大きい項のみ残して表記する
      （ は定数）
    2. 定数倍は無視する

オーダー記法の例）

コードの計算量の調べ方

  • 回のループをする →
  • 回のループの中で 回のループをする（二重ループ）
    →
  • bit全探索（ 個の要素についてある/ないの 通りを考える）
    →
  • 個の順列を全て調べる →

ここまでの復習

このコードの計算量は？？

## 1~n までの数の和を求める
n = int(input())

ans = 0
for i in range(1, n+1):
    ans += i

print(ans)

→ （ までのループを1回している）

計算量の使い方

  • 一般的なコンピュータが1秒間に計算できる回数は約 回
  • 競プロの実行時間制限は大体 秒
  • 各計算量ごとの、制限時間に間に合う

↓ の大きさと実際の値は次ページの表のようになります

参考：https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0#1-3-計算量の使い方

計算量を落とすテクニック

今回は代表的なものを2つ紹介します。

  • 式変形
    比較的単純だけど、強力な手法
  • 累積和
    数列の区間の和を高速に求めるアルゴリズム

式変形

先ほどの までの数の和を求めるプログラムを高速化してみよう

## 1~n までの数の和を求める
n = int(input())

ans = 0
for i in range(1, n+1):
    ans += i

print(ans)

式変形

このコードは、 の和を求めるために の計算をしています
（ で2.6秒くらい必要）→間に合わない！

time_n.png (47.6 kB)

等差数列の和の公式を使えば…

## 1~n までの数の和を求める
n = int(input())
ans = n * (n + 1) // 2

print(ans)
time_1.png (41.3 kB)

なんと、53.7ナノ秒で終了！！

→ 約5億倍の高速化（ちょっと極端な例ではあるけど）
→ もちろん余裕で間に合う

演習問題（式変形）

累積和

あるたい焼き屋さんでは 毎日、売れた個数を記録しています。
営業開始から 日目までの売り上げは以下の通りでした。

日目日目日目日目日目日目日目

日目から 日目までの売り上げの合計はいくらでしょうか？

→ （個）

累積和

あるたい焼き屋さんでは、 日間毎日売り上げを記録しています。
営業開始から 日目の売り上げは 円でした。
このとき、以下の 個のクエリ（質問）に答えて下さい。
日目から 日目までの売り上げの合計はいくらでしょうか？

累積和

各項を毎回足していくと、毎回のクエリで という足し算をすることになる。→最大で 回
よって、 個のクエリを処理すると、計算量は ！！
→間に合わない！

累積和

そこで、 を満たす を考える。（累積和）
このとき、 が求める区間の和になる。

証明）

累積和

つまり？？

累積和

累積和配列の計算方法

calc_acc.png (1.9 MB)

累積和

累積和の計算量は？

  • を求めるのに : から まで 回計算する
  • クエリの計算に
    から までの和は という引き算1回で求まる
  • このクエリを 回繰り返す

→

よって 程度なら、余裕で間に合います。

演習問題（累積和）

参考