基本情報技術の学習をしています。画像の問題について分からないことがあります。赤線で引いてある意味が理解できないので、分か…

Question

基本情報技術の学習をしています。画像の問題について分からないことがあります。赤線で引いてある意味が理解できないので、分かる方いらっしゃいましたら教えていただけると嬉しいです。

Answer 1

厳密な話はありますが、概念としては、そう難しいものではありません。

要は、計算する量が大体どのぐらいか？というだけです。

計算量というは、通常はデータの量に依存しますね。その量をnとして、
そのnに比例的な計算量ならnのオーダー
そのnの二乗に比例的な計算量ならnの二乗のオーダー
そのnによらず，一定の計算量なら1のオーダーとなることを言っているだけです。

例えば、要素数がnの配列から最大値を抜き出す計算だとすると、n回、配列の要素を比較する計算をするのでnのオーダーになります。つまり、forループを一周回せば計算できますね。

これが並べ替えでは、アルゴリズムに寄りますが、単純なものでは、「最大値を見つけて」、その最大値としてどこかに並べておき、残った配列から更に、「最大値を見つけて」、次の最大値のとして保存しという操作を「配列要素数のn回、続け」ます。「最大値を見つけて」の操作にnオーダーが掛かり、それを「配列要素数のn回、続け」るのにnオーダー掛かります。つまり、nの二乗のオーダーになります。forループの中で、更にforループを行うようなアルゴリズムです。

これは数字遊びではなく、結構重要です。
例えば、データの配列数が数百あるはもしかしたら数千ぐらいまでであれば、どのような計算方法を行っても、どうせ極短い計算時間なので、そのアルゴリズムの計算量はあまり考えなくても構いません。

仮に1つの要素を処理するのに0.0000001秒(0.1μ秒)かかる時、1000の要素があるとすると、nオーダーなら合計、0.0001秒(0.1ミリ秒)程度掛かり、nの二乗オーダーなら0.1秒程度となりますね。0.1秒も、0.1ミリ秒も人間にとってはほぼ一瞬ですから、この際の計算方法には無頓着でも良いわけです。

しかし、その配列が、数万、数十万というような大きなデータを扱うような場合は、状況が変わります。
仮にn=10万だとして、上と同じ条件で計算すると、
nオーダーなら合計、0.01秒程度掛かり、nの二乗オーダーなら1000秒(約17分)となりますね。
この計算が終わるまで、17分という時間は、もしかしたら使い勝手に大きく影響する可能性があります。例えば、検索用語を入れて、結果が出るまで17分待てますか？

情報処理技術者は、データ量や実装のしやすさ、記憶量と、その答えを出すべき時間に対して、適切な手法を設計する必要があり、この際、「オーダー」の概念は必要不可欠なものとなるのです。

Answer 2

>基本情報技術の学習
基礎の教科書を購入した方がいいです。

こういう小難しい話が延々と続くからです。

プログラムの計算量、オーダー表記 O( ) の求め方のまとめ | 工業大学生ももやまのうさぎ塾
https://www.momoyama-usagi.com/entry/calc-order

計算量オーダーについて #アルゴリズム - Qiita
https://qiita.com/asksaito/items/59e0d48408f1eab081b5

一週間で身につくアルゴリズムとデータ構造|応用編第1日目：アルゴリズムと計算量
https://sevendays-study.com/algorithm/ex-day1.html

Answer 3

オーダーの定義を例を挙げて説明してくれてます。
より一般化した言い方でいうと、cを定数とすると、実行時間が y=cf(n) となるとき、すなわちf(n)に比例して大きくなるとき、f(n)のオーダーという言い方をするよ、ということです。
それをf(n)の一例としてn^2で説明しているのです。