みなさんこんにちは！おさかなです！
今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます！
第26弾は「計算量」について、書いていこうと思います！
それでは、レッツゴー！！！！！
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人
前回の復習
前回は「データの探索」について見ていきました！
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="16" height="16"><rect fill-opacity="0"/></svg>){kind=icon}
今回は「計算量」について学習していきましょう！
計算量(オーダ)
「計算量(オーダ)」とは、もともとは桁数、累乗のことでざっくりどれくらいの量なのかを考えるときに使います。
計算量(オーダ)を利用することで、プログラムが未完成でも、アルゴリズムだけで「実行時間」のおよその見積もりができます。
![おさかな](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="400" height="400"><rect fill-opacity="0"/></svg>){kind=icon}
処理するデータ量が相当多いときに「計算量(オーダ)」を使うといいよ！
通常は実行時間が「短い」方がいいのですが、「暗号」なんかの場合は実行時間が「長い」アルゴリズムを使うと解読するのに時間がかかり、より強固な暗号となります。
場合によって実行時間の「解釈」が変わってくるので気を付けよう！
オーダの計算方法
ざっくり言うと「一番指数が大きい項だけ考える」という方法です。
具体例を見ながら解説していきます！
例えば、n個のデータを処理する最大実行時間がAn2で抑えられるとき、実行時間のオーダがn2であるといえます。
※Aは定数
計算式の中で一番指数が大きい項だけを考え、それ以外の数は無視して考えます。
実行時間とオーダの関係
実行時間 オーダ
A 1
100n n
3n2 + 5n + 1000 n2
どうして一番指数が大きい項だけを考えるんだろう？？
では、一番指数が大きい項だけを考えそれ以外の数は無視するのか、解説していきます！
例えばデータ数「n = 10,000」で、実行時間が「3n2 + 5n + 1000」だとします。
この式にnを代入すると、「3n2」の部分は「3000,000,000」になりますが、「残り」は「51,000」にしかならず「3000,000,000」と比べるとかなり小さい値になります。
オーダではざっくりと計算したいため、小さい値は無視するというわけです。
オーダ記法
「オーダ記法」とは、関数が「無限大」または「特定の変数値」に向かうとき、大雑把かつ簡潔に表現するための記法のことです。
プログラムの計算量を「O(オーダ)」という形で表します。
例えば、「O(n2)」とは、データ数がnのときに、n2に比例して、計算量が増えていくという意味になります。
計算量 計算量の変化 実行時間のイメージ
O(1) nと無関係に一定 変わらず 相当速い
O(log2n) nの対数に比例 2倍 速い
O(n) nに比例 100倍
O(n2) nの2乗に比例 10,000倍 遅い
整列アルゴリズムの計算量
探索アルゴリズムの計算量
2分探索法 … O(log2n)
ハッシュ探索法 …O(1)
しっかり復習しておこう！
おさかなが参考にした「書籍」一覧↓
・(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度
・令和02年 イメージ＆クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験
・キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)
感想・まとめ
今回は「計算量」について、書いていきました…！
いかがだったでしょうか？
4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。
↓次回は「システムの処理形態」について解説していきます！
お楽しみに～！
おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています！
ぜひ他のページも覗いてみてください…！
それでは今回はこの辺で！
ここまで読んでくださり、ありがとうございました！
おさかなでした！
【おさかなび-osakanav-】では、この記事の感想！おさかなへの応援メッセージ！おさかなに聞きたい事、質問！記事にしてほしい内容！などを大募集中！
「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください！
