ppt

３．多項式計算アルゴリズム
• べき乗の計算
• 多項式の計算
1
３－１：べき乗問題
入力： x , n
（ここで、入力サイズは、 n
す。）
n
出力：
としま
f (x ) = x
2
素朴なべき乗の求め方
• アィディア
–
x
を繰り返し、
n
回乗算する。
n
n
x =
gx42
gL444
gx3
Õ x = x144
i= 1
n
3
アルゴリズムnaïve_pow(x,n)
入力：x,n
出力：xのｎ乗
初期化が重要
1. f=1.0;
2. for(i=０;i＜Ｎ;i++){
3. f=f*x;
4. }
5. return f;
4
• アルゴリズムnaïve_powの正当性。
（ほとんど明らかだが、証明することもできる。）
練習
正当性を帰納法で証明するためには、どのよう
な命題を設定すればよいか？
5
アルゴリズムnaïve_powの時間計算量
• 高々 n 回の繰り返し。
• 各繰り返し中では、１回の乗算と、１回の
代入が行われているだけである。
 O ( n)
の時間計算量である。
6
数学の記号とプログラム
n- 1
Õx
i= 0
n- 1
å xi
i= 0
i
1. for(i = 0;i < n ;i++){
2. f=f* x [i ] ;
3. }
1. for(i = 0;i < n ;i++){
2. f=f+ x [i ] ;
3. }
7
高速なべき乗の求め方。
• 注意
– とりあえず、入力に制限を加える
–
が２のべき乗と仮定する。すなわち、
n
k
n= 2
• アィディア
– 倍、倍に計算した方が高速にもとまる。
k
k
x gx = x
– （一方、
i
x gx = x
2k
i+ 1
）
8
アルゴリズムfast_pow(x,n)
入力：x,n（ただし、 n = 2k ）
出力：xのｎ乗
1. f=x;
2. for(i=1;i＜k;i++){
3. f=f*f;
4. }
5. return f;
9
命題ＦＰ１（fast_powの正当性）
forループが k回繰り返されたとき、
fの値は、
である。
f = x
2k
証明繰り返し回数ｋによる帰納法による。
繰り返し回数ｋのときのｆの値を fk と表す。
基礎： k = 0
アルゴリズム中のステップ１より、
20
1
= x
一方、右辺＝ x
よって、命題は成り立つ。
f 0 = x である。
= x
10
帰納：
0< k
0 £ k ' < k なる全ての k ' に対して、
命題が成り立つと仮定する（帰納法の仮定）
k ' = k - 1 として、 k - 1 回の繰り返しで、
fk - 1 = x
2k - 1
である。よって、 k 回めの繰り返しでは、
fk = fk - 1 gfk - 1 = x
2k - 1
gx
2k - 1
= x
2k
QED
11
fast_powの時間計算量
アルゴリズムは、明らかに、ｋ回繰り返す。
繰り返し中は、1回の乗算しか行っていない。
したがって、
O (k )
の時間計算量である。
n = 2k
\ k = log2 n
なので、結局
O (log n )
の時間計算量である。
12
一般の自然数に対する高速な
べき乗アルゴリズム
n
が２のべき乗でないときを考える。
このとき、前の高速なべき乗アルゴリズムを
サブルーチンとして用いることができる。
の2進数表現を次のように表す。
n
(n )10 = (b b
m m - 1 L b1b0 )2
= 2 ´ bm + 2
m
m- 1
´ bm - 1 + L + 2 ´ b0
0
13
このとき、
xn
n
x = x
= (x
2m
m
=
は次のように表せる。
2m bm + 2m - 1 bm - 1 + L + 20 b0
bm
2m - 1
bm - 1
) g(x )
gL g(x
1 b0
)
bi
Õ (x )
2i
i= 0
これより、一般のｎに対する高速なアルゴリズムが
得られる。
14
アルゴリズムgeneral_fast_pow(x,n)
入力：x,n(ｎは一般の数）
出力：xのｎ乗
1.
2.
3.
4.
5.
6.
7.
8.
f=1.0;
1 0 )2 に変換する。
nを２進数 (bmbm - 1 L bb
for(i=0;i＜m;i++){
if( bi = = 1 ){
f=f*fast_pow(x, 2i );
}
}
return f;
15
３－２：多項式の計算
• 入力： x , n , a 0 , a1, L
• （ここで、入力サイズは、 n
す。）
• 出力：
, an
としま
f (x ) = a 0 + a1x + L + an x
n
n
=
å
ai x
i
i= 0
16
素朴な多項式の求め方
• アィディア
– 各項を素朴な乗算で計算し、
総和を求める。
f (x ) = a 0 + a1x + L + an x n
n
=
å
ai x i
i= 0
n
=
å
i= 0
æi ö
÷
ai çççÕ x ÷
÷
÷
çè j = 0 ø
17
アルゴリズムnaive_poly()
入力：x,次数n,係数a[n]
n
出力：
i
f (x ) =
1.
2.
3.
4.
5.
6.
7.
8.
9.
å
a[i ]x
i= 0
fx=0;
for(i=0;i＜=N;i++){
tmp=a[i];
for(j=0;j<i;j++){
tmp=tmp*x;
}
fx=fx+tmp;
}
return fx;
3-6は、
第i項の計算
18
素朴な多項式計算アルゴリズム
の正当性
命題ＮＰ１（naive_polyの正当性1）
2.のforループが i回繰り返されたとき、
tmpの値は、
ai x
i
である。
19
証明
アルゴリズム中のステップ３より、 tmp = ai に設定される。
また、４の繰り返しは明らかにi回である。
したがって、
よって、
x
はi回乗算される。
tmp = ai x
である。
i
より厳密な帰納法でも
証明できる。
QED
20
命題ＮＰ２（naive_polyの正当性２）
naïve_polyは
n
f (x ) =
å
ai x i
i= 0
を計算する。
証明
次数
n に関する帰納法による。
基礎 n = 0
tmp = a 0 = f (x )
帰納
であり正しい。
n> 0
0 £ n ' < n の時正しいと仮定する。
21
n ' = n - 1 とする。
n-1の繰り返しのときのｆｘの値を fn - 1 (x )
このとき、帰納法の仮定より、
と書く。
n- 1
fn - 1(x ) =
å
ai x i
i= 0
が成り立つ。 n 回目の繰り返しでは、 i = n なので、
n
（命題ＰＬ１より）
n
tmp = a x
また、ステップ７より、
f (x ) = fn - 1(x ) + tmp
æn - 1 i ö÷
n
= ççå ai x ÷
+
a
x
n
÷
çè i = 0
ø
n
=
å
i= 0
an x n
QED
22
素朴な多項式計算アルゴリズム
の計算時間
ステップ５の部分が最も時間を多く繰り返される。
ステップ４のforループは、i の値にしたがって、
i 回繰り返される。
よって、時間計算量を T (n ) とすると、
T (n ) は、次のように計算できる。
n
T (n ) =
å
i
i= 0
= 1+ 2+ 3+ L + n
n (n + 1)
=
2
= O (n 2 )
23
以上から、naive_polyの最悪時間計算量は、
2
O (n )
であることがわかる。
また、繰り返し回数は、入力サイズ（ｎ）だけに依存し、
問題例（係数配列の状態）に依存しない。
よって、
2
Q(n )
の時間計算量を持つこともわかる。
24
補足：べき乗に高速なアルゴリ
ズムを用いた場合
n
T (n ) =
2
å (log i )
i= 0
2
2
2
£ (log1) + (log 2) + L + (log n )
2
2
2
£ (log n ) + (log n ) + L + (log n )
((
= O n logn
2
))
((
と計算できるので、 O n logn
2
))
のアルゴリズムといえる。
（べき乗の計算に、mathライブラリのpowを用いた場合、
この計算量になると考えられる。）
25
ホーナーの方法
• アィディア
– xをできるだけくくりだしながら計算する。
f (x ) = a 0 + a1x + L + an x n
= (a 0 + (a1 + (L (an - 2 + (an ) * x ) * x ) L ) * x * x )
26
アルゴリズムを示すまえに、等式の正当性を証明する。
命題Ｈ１（hornerの正当性1）
f (x ) = a 0 + a1x + L + an x n
= (a 0 + (a1 + (L (an - 2 + (an ) * x ) * x ) L ) * x * x )
証明
a 0 , a 1, L , a n
に対して、
fk (x ) º an - k + an - k + 1x + an - k + 2x 2 + L + an x k
k
=
å
an - k + i x
i
i= 0
と定義する。
27
このとき、各関数は次のような系列になる。
f 0 (x ) = a n
f1(x ) = an - 1 + an x
f2 (x ) = an - 2 + an - 1x + an x 2
M
2
n
fn (x ) = a 0 + a1x + a2x + L + an x = f (x )
この fk (x ) に関して、
次式を k に関する帰納法で命題を証明する。
fk (x ) = (an - k + (an - k + 1 + (L (an - 1 + (an ) * x ) L ) * x ) * x )
28
基礎
k = 0
f0 (x ) = an = (an )
であり、満たされる。
帰納
k> 0
0 £ k ' < k なる全ての k ' で
k'
fk ' (x ) = an - k ' + an - k ' + 1x + L + an x
= (an - k ' + (an - k ' + 1 + (L (an - 1 + (an ) * x ) L ) * x ) * x )
と仮定する。（帰納法の仮定）
k ' = k - 1 として
fk - 1(x ) = an - k + 1 + an - k + 2x + L + an x
k- 1
= (an - k + 1 + (an - k + 2 + (L (an - 1 + (an ) * x ) L ) * x ) * x )
29
このとき、
an - k + an - k + 1x + L + an x
帰納法の仮定を
用いている。
k
= an - k + (an - k + 1 + L + an x
k- 1
)*x
= an - k + (an - k + 1 + (L (an - 1 + (an ) * x ) L ) * x ) * x
= (an - k + (an - k + 1 + (L (an - 1 + (an ) * x ) L ) * x ) * x )
よって、命題は成り立つ。
QED
30
ホーナーの方法の計算手順
(a0 + (a1 + (L (an - 1 + (an ) * x ) * x ) L ) * x ) * x )
31
アルゴリズムhorner_poly()
入力：x,次数n,係数a[n]
n
出力：
i
f (x ) =
å
a[i ]x
i= 0
1. horner(int k,double x){
2. if(k==0){
3.
return a[ｎ];
4. }else
5.
f_k=a[n-k]+horner(k1,x)*x;
6.
return f_k;
7.
}
8. }
32
ホーナーの方法の計算時間
計算時間を T
(n )
とすると次の漸化式を満たす。
ìï c0
(n = 0)
T (n ) = ïí
ïï c1 + T (n - 1) + c2 (n > 0)
ïî
c 1 を加算に必要な計算時間とし、
c 2 を乗算に必要な計算時間としている。
c = max{c1, c2 } とすると、次のようにかける。
ここで、
ìï c0
(n = 0)
T (n ) £ ïí
ïï T (n - 1) + 2c (n > 0)
ïî
33
T (n ) £ T (n - 1) + 2c
£ (T (n - 2) + 2c ) + 2c = T (n - 2) + 4c
M
£ T (0) + 2nc
これより、
£ (c 0 + 2c )n
T (n ) = O (n )
よって、ホーナーの方法による多項式の計算は、
線形時間アルゴリズムである。
34
ホーナーの方法の繰り返し版
ホーナーの方法は、次のように、繰り返しを用いても
実現できる。
1. horner(int k,double x){
2. double f_k=a[n];
3. for(k=1;k<=n;k++){
4.
f_k=a[N-k]+( f_k )*x;
5. }
6.
return f_k;
7. }
このアルゴリズムも明らかに線形時間で実行される。
35

Download Report