【誰でもわかる基本情報シリーズ】26.「計算量」

誰でもわかる基本情報シリーズ

みなさんこんにちは!おさかなです!

今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます!

第26弾は「計算量」について、書いていこうと思います!

それでは、レッツゴー!!!!!

想定読者
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人

前回の復習

前回は「データの探索」について見ていきました!

【誰でもわかる基本情報シリーズ】25.「データの探索」
【誰でもわかる基本情報シリーズ】第25弾!基本情報技術者試験の合格を目指す人に向けて、わかりやすく解説!今回は「データの探索」について学習してきます!まだまだ続くアルゴリズムを踏まえて、探索しましょう「おさかなび-osakanav-」では、「デジタル時代を楽しむためのミニ知識」をご紹介しています!ゆるいイラストが目印!

今回は「計算量」について学習していきましょう!

計算量(オーダ)

計算量(オーダ)」とは、もともとは桁数、累乗のことでざっくりどれくらいの量なのかを考えるときに使います。

計算量(オーダ)を利用することで、プログラムが未完成でも、アルゴリズムだけで「実行時間」のおよその見積もりができます。

おさかな
おさかな

処理するデータ量が相当多いときに「計算量(オーダ)」を使うといいよ!

通常は実行時間が「短い」方がいいのですが、「暗号」なんかの場合は実行時間が「長い」アルゴリズムを使うと解読するのに時間がかかり、より強固な暗号となります。

おさかな
おさかな

場合によって実行時間の「解釈」が変わってくるので気を付けよう!

オーダの計算方法

ざっくり言うと「一番指数が大きい項だけ考える」という方法です。
具体例を見ながら解説していきます!

例えば、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倍       遅い

 

整列アルゴリズムの計算量

基本交換法、基本選択法、基本挿入法の計算量 … O(n2)

探索アルゴリズムの計算量

線形探索法の計算量 … O(n)
2分探索法 … O(log2n)
ハッシュ探索法 …O(1)
おさかな
おさかな

しっかり復習しておこう!

おさかなが参考にした「書籍」一覧↓

(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度

令和02年 イメージ&クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験

キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)

令和02年【春期】【秋期】 基本情報技術者 合格教本

感想・まとめ

今回は「計算量」について、書いていきました…!

いかがだったでしょうか?

おさかな
おさかな

4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。

↓次回は「システムの処理形態」について解説していきます!

【誰でもわかる基本情報シリーズ】27.「システムの処理形態」
【誰でもわかる基本情報シリーズ】第27弾!基本情報技術者試験の合格を目指す人に向けて、わかりやすく解説!今回は「システムの処理形態」について学習していきます!「バッチ処理」など1つ1つ丁寧に解説!「おさかなび-osakanav-」では、「デジタル時代を楽しむためのミニ知識」をご紹介しています!ゆるいイラストが目印!

お楽しみに~!

おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています!
ぜひ他のページも覗いてみてください…!

それでは今回はこの辺で!

ここまで読んでくださり、ありがとうございました!

おさかなでした!

【おさかなび-osakanav-】では、この記事の感想!おさかなへの応援メッセージ!おさかなに聞きたい事、質問!記事にしてほしい内容!などを大募集中!

「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください!

タイトルとURLをコピーしました