# 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 他のソートが出てきたら分からなかった