全文

(1)

算法の設計と解析

第五回

2004.11.22

P

i6=jaibj =Pn

i=0aibn−i

A=F(a1, ..., an) B=F(b1, ..., bn) を満たすFを作れという問題に対して、

ωn= 1, ω6= 1, yi =

n−1X

j=0

ωijxj

Fとする。

y= (y0, y1, ..., yn−1)T x= (x0, x1, ..., xn−1)T とおくと、

y= Φ(n)x

Φ(n)=

1 · · · 1 1 ωji 1

と表すことができる。

n= 2kと考える

Φ(n)=

"

Φ(n2) (n2)Φ(n2) Φ(n2) −∆(n

2)Φ(n2)

#

n=

1 0

ω ω2

. ..

0 ωn−1

x01= (xT0xT1)T 2k×2k次の行列とベクトルの積を4つの2k2 ×2k2 の行列とベクトルの積に分ける

1

(2)

積の回数

ak nlogn

−→ Ak

bk nlogn

←− Bk

(1) 積の回数はαnlogn+β回つまり積の回数を減らしている。

Φ(2) = 1 i 1 −i

!

Φ(4)Φ(8)

Φ(n)= Φ(n2) ∆Φ(n2) Φ(n2) −∆n2Φ(n2)

!

H2= 1 1

1 −1

!

H4H8

H2k = H2k2 H2k2 H2k2 −H2k2

!

(2)

H = 1 1

1 0

!

x∈ {0,1}y∈ {−1,1}

ex,

αn2+βn2O(n3) Def1f(x) =O(g(x)0)limn→∞f(x)

g(x) = 0 O(x) = sinx

Def2, f(x) =O(g(x))x→ |f(x)< C|g(x)|

となる定数Cが存在する

Def3f(x) =H(g(x))∀x >∃x ...

Def4f(x)g(x)

limx→∞g(x)f(x) = 1

(3) ex,

x2+xx2 Def5f(x) = Ω(g(x))

2

(3)

行列を

2

分割する問題の計算量

(積の回数)

αnlogn+β=O(nlogn) φ(2)= 1 i

1 −i

!

, i2=−1 (4)

Euler

点と点を結ぶ辺と考える

1: Eulerの頭のいいところ

点の集合:V,i、辺の集合:E, C, V ×V 辺の重み:ω(i, j), V ×V の関数 E(i, j)ijのつながりを決める|v|<∞,|v|=

グラフ上の最小化問題 X

i,j∈v

ω(i, j)min, v2v となるvを見つける

ex

v,ある点からある点への最短距離 (i,i)なる辺自己ループ

(i,i)を含まないグラフを単純グラフという。

閉路のないグラフを木という。

グラフのデータ構造V ={1,2, ..., n}, E={(α, β)}

1: 自己ループなしのグラフ

1 2 . . . n

1 × ω(1,2) ω(1, n)

2 ×

... . ..

n ×

3

Updating...

参照

Updating...

関連した話題 :