ぱうえる（けんた）
でも速いコードってどうやって評価する？？
「データの大きさ」や「実行する環境」に依存しない評価方法が必要 → 計算量の出番
→ (ランダウの記号)を用いる
オーダー記法の例）
このコードの計算量は？？
# 1~n までの数の和を求める n = int(input()) ans = 0 for i in range(1, n+1): ans += i print(ans)
→ （ までのループを 1 回している）
↓ の大きさと実際の値は次ページの表のようになります
参考：https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0#1-3-計算量の使い方
今回は代表的なものを 2 つ紹介します。
先ほどの までの数の和を求めるプログラムを高速化してみよう
このコードは、 の和を求めるために の計算をしています （ で 2.6 秒くらい必要）→ 間に合わない！
等差数列の和の公式を使えば…
# 1~n までの数の和を求める n = int(input()) ans = n * (n + 1) // 2 print(ans)
なんと、53.7ナノ秒で終了！！
→ 約5 億倍の高速化（ちょっと極端な例ではあるけど） → もちろん余裕で間に合う
あるたい焼き屋さんでは 毎日、売れた個数を記録しています。 営業開始から 日目までの売り上げは以下の通りでした。
日目日目日目日目日目日目日目
日目から 日目までの売り上げの合計はいくらでしょうか？
→ （個）
あるたい焼き屋さんでは、 日間毎日売り上げを記録しています。 営業開始から 日目の売り上げは 円でした。 このとき、以下の 個のクエリ（質問）に答えて下さい。 日目から 日目までの売り上げの合計はいくらでしょうか？
各項を毎回足していくと、毎回のクエリで という足し算をすることになる。→ 最大で 回 よって、 個のクエリを処理すると、計算量は ！！ → 間に合わない！
そこで、 を満たす を考える。（累積和） このとき、 が求める区間の和になる。
つまり？？
累積和配列の計算方法
累積和の計算量は？
→
よって 程度なら、余裕で間に合います。
$$ \small \begin{array}{|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline A_i & - & 20 & 50 & 30 & 10 & 30 & 0 & 40\\ \hline S_i & 0 & 20 & 70 & 100 & 110 & 140 & 140 & 180\\ \hline \end{array} $$