1. アルゴリズムと計算量
授業の説明
「データ構造」の講義で学ぶ内容
データ構造の話
コンピュータ内で
データをどのように
保持するのか
データ
密接な関係
アルゴリズムの話
データを使って
どのように
処理させるのか
処理結果
データ構造の重要性
処理効率の向上＝洗練されたアルゴリズム＋データ構造の正しい選択
データ構造の選択
• アルゴリズムを考慮
• コンピュータ資源を考
慮
データ
アルゴリズムの設計
• データ構造を考慮
• コンピュータ資源を考慮
処理結果
他の科目との関連
プログラミング
アルゴリズム
データ構造
アルゴリズムの話
手続きとは？
問題を解く手順が書かれている
Jfkdsoaiejfl;ldsfdsajklaf
kljklfjdajfkldldsfdsajklaf
fkdjkfdsafjkdssfdsajklaf
Jfkdstioewpkmvm,ajklaf
基本的な演算・操作
Jfkdsamekocigjkf;ajkdsf
Jewojfdkvm,ladkfgiuako
ldsfiewjfnmdaljcidoagjkf
記述は有限の長さ
アルゴリズムとは？
どんな入力でも
必ず停止する
定義域
手続
き
値域
アルゴリズムの例（ユークリッドの互助法）
m、nは自然数
(1) r ← （n を m で割った余り）, (2)に移る。
(2) r = 0 ならば
m が最大公約数と答え，計算を停止する。
r ≠ 0 ならば
n ← m, m ← r, (1)に移る。
３４
１４
n
m
６
２
０
r
ユークリッドの互助法（イメージの構築）
n＝［長い方］
m で割った余り
＝［短い方］
nをm
何故、「n
何故、「 nを←mm,で割った余り」を考えるのか？
m ← r 」の代入を行うのか？
今まで短かった方が今度は長い方に
今まで余りだった方が今度は短い方に
ユークリッドの互助法（具体例）
６
３４
２
１４
３４
１４
n
m
０
６
２
r
停止しない手続きの例（問題設定）
• 最大公約数問題を市松模様問題として解釈
• 市松模様問題
→ 入力：長方形（縦と横の長さ）
→ 出力：出来るだけ大きい正方形で市松模様を
つけたときの、その正方形のサイズ
• ［長い方］を「短い方］で割った［余り］
＝［長］－ ｛［短］×切捨て（［長］/［短］）｝
停止しない手続きの例（手続き）
• 市松模様問題を解く手続き
(1) r ← （［長い方］を［短い方］で割った［余り］）, (2)に移る。
(2) r = 0 ならば
［短い方］ が正方形のサイズと答え，計算を停止する。
r <> 0 ならば
［長い方］ ← ［短い方］, ［短い方］ ← ［余り］, (1)に移る。
• 計算誤差は無いものとする（現実的な仮定ではない）
停止しない手続きの例（定義域）
横
縦：横
市松模様を
解く手続き
縦
縦横比が
実数
縦横比が
有理数
値域
自分で考えてみよう
• 縦横比が有理数だと必ず停止することを証明
してみよう
• 停止しないような縦横比を見つけてみよう
ロシア乗算法（ハードに適した方法）
÷２
×２
４５
×
１９
２２
×
３８
１１
×
端数を保存
＋
２で割る
４５ → １０１１０１
２２ → １０１１０１
１９
７６
５
× １５２
＋
７６
２
×
３０４
＋
１５２
１
×
６０８
＝
６０８
合計 ８５５
２を掛ける
１９ → １００１１
３８ → １００１１０
１０進数で１０倍
→右に０を追加
２進数で２倍
→右に０を追加
効率の良し悪しの尺度
•
運転技術の評価
– 最速F1ドライバーとは？
1. 最新型マシーンと旧型マ
シーン
2. 短距離と長距離
3. 優勝回数と平均順位
• プログラムの評価
– 高速プログラムとは？
1. 最新型コンピュータと旧型コ
ンピュータ
2. 大規模データと小規模データ
3. 最悪計算量と平均計算量
計算量（物差と量り方）
• テストコースで車を５０回 • 何を量るか（物差）
走らせた
– 計算時間を量る
• 何を量るか（物差）
– 速度を量る
– 燃費を量る
• どう評価するか（量り方）
– 最悪のタイムで評価
– 平均で評価
→ 時間計算量
– 使用メモリを量る
→ 空間計算量
• どう評価するか（量り方）
– 最悪の場合で評価
→ 最悪計算量
– 平均で評価
→ 平均計算量
漸近的計算量
良いアルゴリズムはどっち？
時間計算量の例
a11
a
n1
a1n b11
A
ann bn1
b1n c11 c1n
B
bnn cn1 c nn
10
100
1000
10 A “何倍か？“はアルゴリズムに依存する
B
A
B
100
10倍
A
B
1000
10倍
10×10の
計算時間
何倍？
100×100
の計算時間
何倍？
1000×1000
の計算時間
時間計算量の例
a11 a1n b11 b1n c11 c1n
a a b b c c
nn n1
nn
nn
n1
n1
n
cij aik bkj
k 1
• c ：Pの１回の（最悪）処理時間
• Pはn３回行われる
⇒
for i : 1 to n do
for j : 1 to n do
{ cij : 0; ←無視
for
k
:
1
to
n
do
計算時間は（最悪） c n３
3
cij : cijP aik bkj ; }
３
（計算時間はn に比例） O ( n )
何を気にしているのか？
例：（行列の積の計算時間）と（正方形の体積）
• （体積の増え方）と（辺の長さの増え方）の関係は？
⇒ 体積は辺の長さの３乗に比例
（辺が２倍になれば体積は２３＝８倍になる）
• （データサイズ）と（計算時間）の関係は？
⇒ 計算時間はデータサイズの３乗に比例
O(n3)と表記する
計算量のオーダ
* c R n0 N n n0
O( f (n)) t : N R
t (n) cf (n)
c f ( n)
t(n)はO(f(n))
t (n)
cy
y
n0
f (n)
計算量のオーダ
* c R n0 N n n0
( f (n)) t : N R
t (n) cf (n)
f (n)
t(n)はΩ(f(n))
t (n)
y
cy
n0
c f ( n)
計算量のオーダ
* c R n0 N n n0
O( f (n)) t : N R
t (n) cf (n)
n0 N n n0
c
R
*
( f (n)) t : N R
t (n) cf (n)
( f (n)) O( f (n)) ( f (n))
© Copyright 2024 ExpyDoc
