雑読「問題解決力を鍛える！アルゴリズムとデータ構造」：2章 計算量とオーダー記法
2.1 計算量とは
アルゴリズムの良さを決める基準
実行時間を大雑把に見積もれる
2.2 計算量のオーダー記法
1重のforループと2重のforループの比較の実験
1重はNが10, 100倍になると計算時間が10, 100倍になり、N重は100, 10000倍になっている
前者をO(N)、後者をO(N^2)という
アルゴリズムAの計算時間T(N)がおおむねP(N)に比例することを
T(N)=O(P(N))と表記し
Aの計算量はO(P(N))という
forループのコードの計算量を実際に考えていく
一番支配的な項だけみておけばNが大きい時無視できるからいいよねという内容
2.3 計算量を求める例(1)：偶数の列挙
N個の整数を受け取ってN以下の偶数を全て出力するアルゴリズム
反復回数はN/2で、計算時間はおおむねNに比例するのでO(N)
Nが大きくなった時にあまり効いてこないので定数倍は無視する
2.4 計算量を求める例(2)：最近点対問題
2次元平面上のN個の点のうち、最も距離が近い2点の距離を求める問題に対する全探索
T(N)=\frac{1}{2}N(N-1)なのでO(N^2)
この問題は分割統治法を使うとO(N \log N)のアルゴリズムもあるらしい
2.5 計算量の使い方
実行環境に強く依存するが、大まかな感覚を掴むのは重要
アルゴリズム設計ではこれを知っておく必要がある
計算実行時間の制限
ときたい問題のサイズ
現代の家庭用PCでは10^9回/sぐらい計算できる
CPUのクロックが例えば3GHzなら1秒に3×10^9クロックの計算できる
なるほど
O(N!)やO(2^N)
Nが大きいと現実的な時間で計算が終わらない
N=100の時2^{100}\simeq10^{30}ステップ必要で10^9回/sの計算機を使うと30兆年ぐらいかかる
でもNが十分に小さければ使える
定数d>0が存在して計算量がN^dの定数倍によって上から抑えられる
N\log Nは多項式ではないけどN\log N\leq N^2だからO(N\log N)は多項式時間
O(1)
Pythonのリストでinを使うとO(N)になるのでsetやdictを使ってハッシュテーブルを使う
2.6 計算量に関する注釈
時間計算量と領域計算量（実行時のメモリ使用量）がある
本書での計算量は時間計算量のこと
入力データによっては計算が早く終わったり遅く終わったりする
最悪ケースを最悪時間計算量
本書での計算量はこっち
クイックソートは平均的には高速だけど最悪時には遅い
入力データに特定の分布を仮定したときの時間計算量の期待値を平均時間計算量という
2.7 ランダウのO記法の詳細
前の説明をもうちょっと数学的に緻密にする
O記法は上界
だからO(N^2)のアルゴリズムはO(N^3)でもある。ただ普通最も小さいもので表記する
Ω記法は下界
θ記法は上界と下界両方から挟み撃ちで評価
慣習としてθ記法が使えてもO記法を使うから本書も基本O記法を使う
2.8 まとめ
計算量は実際的には定数倍や低次の項を無視する
実際のアルゴリズム評価はforの反復回数評価のような方法で求めたものが計算時間評価の良い尺度になる
演習問題
2.1 ランダウのO記法にする問題
1000N
Nの定数倍なのでO(N)
5N^2+10N+7
一番支配的な項はN^2なのでO(N^2)
4N^2+3N\sqrt{N}
N\sqrt{N}\leq N^2なので、支配的な項はN^2だからO(N^2)
N\sqrt{N}+5N\log N
\lim_{N \to \infty}\frac{5N\log N}{N\sqrt{N}} = \lim_{N \to \infty}\frac{N^5}{2^{\sqrt{N}}}\to 0なのでO(N \sqrt{N})
2^N+N^{2019}
支配的な項は2^NなのでO(2^N)
2.2
cfor(int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
for (int k = j + 1; k < N; ++k) {
}
}計算量を求め、ランダウのO記法を示せ
Nこのものから3個を選ぶ方法を全て列挙するのでN(N-1)(N-2)
支配的な項はN^3なのでO(N^3)
2.3
以下の手続きの計算量をもとめ、ランダウのO記法を示せ
cbool is_prime(int N) {
if (N<=1) return false;
for(int p=2; p*p <= N; ++p)){
if(n % p == 0) return false;
}
return true;
}整数N>0が素数かを判定するプログラム
方針：for分の反復回数T(N)を数える
n=1 0
n=9 2
n=16 3
だいたい\sqrt{N}回計算されるのでO(\sqrt{N})
もっと弱いアルゴリズムも紹介されていた
2.4
年齢が0以上2^k未満のとき2分探索でk回で当てられることを示せ
2分探索では1回で選択肢が1/2になる。k回で(1/2)^kになるので0以上2^k未満の2^k個の選択肢から1つに絞れる
これで示したことになる？
2.5
年齢が0以上N未満のとき2分探索でO(logN)で当てられることを示せ
2.4と同様に選択肢はk回の探索で(1/2)^kになる
N個の選択肢がk回の探索で1個に絞れれば解いたことになる。ことのきのkの反復回数k=T(N)を得たい
(1/2)^kN=1をkについてとくとk=\log NなのでO(\log N)で当てられる
2.6
1+1/2+...+1/N=O(logN)を示せ
\lim_{N \to \infty}\frac{\sum_{k=1}^N\frac{1}{k}}{\log N}が定数で抑えられることを示せば良い
このままだと計算がわからなかった（できる？）
\sum_{k=1}^N\frac{1}{k}<1+\log NなのでO(\log N)
（関係ない）\lim_{N \to \infty} \frac{1}{N}\sum_{k=1}^N\frac{1}{\frac{k}{N}}=\int_0^1\frac{1}{x}dx（発散）
区分求積懐かしい
cf. オイラーの定数(オイラー・マスケローニ定数)
\gamma \coloneqq \lim_{n\to \infty}\left(\sum_{k=1}^{n}\frac{1}{k} - \log n \right) = 0.57721\dots