---
# System prepended metadata

title: Chapter16-10 「オーダ記法」
tags: [基本情報技術]

---

# Chapter16-10 「オーダ記法」

## 8/13(金)

###### tags:`基本情報技術`

さつき：
> アルゴリズムの計算量をO（式）の形であらわすものです。
> おおまかな処理効率をはかるための指標。
> あくまでも「アルゴリズムにおけるデータ量と計算量との関係」を見るものなので、例えばバブルソートと選択ソートのように、オーダが同じだからといって、処理時間が同じ、とはなりません。

* 各アルゴリズムのオーダ
    * オーダ記法では、係数は無視できる。log2n→lognという感じ。
* 過去問
    * 問1 OK
    * 問2 OK。
* おまけ（世間の色々なアルゴリズムについて）
    * たとえばカーナビや乗り換え案内
        * 中心となるのは、A地点からB地点まで行く方法が何パターンかあった場合、どの経路を通るのがいちばん早いか？を計算してくれるアルゴリズム
    * Googleの検索アルゴリズム
        * Googleで検索された単語に対して、どのページを上位に表示させるかという計算方法（アルゴリズム）
    * アルゴリズム体操
        * 「前の手順を受けて、次の手順が進む」動きがアルゴリズム的なので「アルゴリズム体操」という名前になっているのでしょう。
    >面白かった！


にわ：
- 読み込み
    * オーダ：アルゴリズムにおけるデータ量と計算量の関係をあらわすもの（大まかな処理効率がどのくらいかをはかる指標）
    * オーダ記法：オーダをO（式）で表す。例えばO(n)とか。
    * 各アルゴリズムのオーダ（探索アルゴリズムの例）
        * 線形探索法：O(n) 一つずつ見ていくのでnが増えた分処理回数も増える
        * 2分探索法：O(log2n) 2分の1ずつ絞り込むのでデータ量が２倍になった時に処理回数が増える
        * ハッシュ法：O(1) 直接アクセスできるので件数nに左右されない
- 過去問
    * 問１：OK。オーダ記法では定数の係数は無視できるのか。。。
    * 問２：ほぉ・・・解説読んでやっと理解した。



ちさと：
* オーダ記法
    * アルゴリズムの計算量（実行時間）を表す
    * 線形探索法：　例）処理するデータ量nが2倍、3倍と増えると、処理時間も比例して2倍、3倍と増えるアルゴリズム＝O(n)と表す
* 過去問
    * 問１：おk
    * 問２：nが増えるたびに２重ループが１つ増える

まい：
* オーダ記法 Big-O Notation: アルゴリズムの計算量(実行時間)をO式の形で表すもの
   * 正確な実行時間ではなく、大まかな処理効率を図る

* Linear O(n)
* Quadratic O(n2)

* 過去問
  * 問1 ok
  * 問2 ok 他のソートが出てきたら分からなかった