20230119計算量オーダーについて
パソコン素人です。
算数素人です。
基本情報技術者試験の問題・テキスト等を見て気になったメモです。
多分間違っているので詳しく見ないで下さい。すみません。
（記載内容や参考にしたネット情報など問題がありましたら、早急に削除いたします。）
「計算量オーダー」というのが気になって調べてみました。
ネット参考:
「計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜」
いろんなことが書いてあり、参考になりました。（感謝）
多分、ソートの計算量をエクセルにすると、こんな感じ（上記の表）です。
線形探索法は、前から１個ずつ探す。
二分探索法は、中央の値と大小比較して、さらに分割して・・・説明できないが（汗）・・・こんな感じ。
で、計算量に書いた「O」って何？で
「ランダウの O 記法」だそうです。
理解が違っているかもしれませんが、
O(n)のOって何？と思っていたのですが、ネットによれば、
ランダウって人のO（数字ではない）で、
極限までいくと、端数なんか無視する→そういう表記法だそうです。
「指数関数的に・・・」とかよく言うけど、べらぼうに数字が大きくなったら、半端は無視ということらしいです。
ルール：
最高次数の項以外は落とす: 3n^2+5n+100→3n^2
係数を無視する: 3n^2 → n^2
ということらしい。
上でサーチを記載したが、並べ替え（ソート）の計算量だと多分こうなる。
当たり前ですが、サーチより、並べ替え（ソート）の方がとても時間がかかります。
（バブルソートは１枚１枚並び替えます。）
（選択ソートも１枚１枚確定させていきます。）
（マージソートは要素を分割して（再帰処理）、最小になったら、並べ替えて、統合していきます。）
ソートは、数式にｎに指数がつくか、最短でもｎが前につく感じかな。とにかく回数がかかる。
なお、上記のネットには、
for (int i = 0; i < n; ++i) {
// なにかする (各 i に対する処理は軽いものとする)
}
上記のfor文は、「計算量O(n)」で、
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// なにかする (各 i, j に対する処理は軽いものとする)
}
}
上記のfor文は、「計算量O(n^2)」に該当するとありました。
・・・言われればなるほど。
さらに、上記ネットには、
計算に使用するマシンは普通の家庭用 PCとして、
1 秒間で処理できる for 文ループの回数は、10^8=100,000,000=100,000,000 回程度
と書いてありました。（どんどん進歩するようですが。）
そういうのを考えてくと仕事時間全体も計算できるのかなと思いました。
回数がかかると言っても、１秒に１億も処理できればあっという間か。
