補講：アルゴリズムと漸近的評価

アルゴリズム

アルゴリズムと問題 「アルゴリズム」とは「問題」を解くために、 「基本操作」（命令）を有限個組み合わせ てできる手順。 色々な問題 命令 データのソート アルゴリズム 四則演算 2進数への変換 代入演算 連立方程式を解く 比較演算 組み合わせ方 最大公約数

アルゴリズム例１ 25の2進数は？ 25/2 =12 ・・・1 12/2 = 6 ・・・0 6/2 = 3 ・・・0 １０進数を２進数に変換する方法 25の2進数は？ ２で割り算 商 余 25/2 =12 ・・・1 12/2 = 6 ・・・0 6/2 = 3 ・・・0 3/2 = 1 ・・・1 1/2 = 0 ・・・1

最大公約数を求める方法（ユークリッドの互除法） アルゴリズム例２ 最大公約数を求める方法（ユークリッドの互除法） 2つの自然数m,nの最大公約数を求めるアルゴリズム [step1]：mをnで割って余りをrとする。 [step2]:r=0ならアルゴリズム終了する。このときのnが 最大公約数 [step3]:r0なら、mにnを代入し、nにrを代入してstep1にもどる。 実行例 m=12 n=8 の最大公約数 1回前の余り で割り算 余り 次回の値 12/8=1・・・4 m=8 n=4 8/4=2 ・・・0 最大公約数は４

アルゴリズムとプログラム アルゴリズム プログラミング プログラム ＋ プログラム言語 データ構造 int gcd(int m, int n){ int r; do { r= m % n; m=n; n=r; }while(r != 0); return m; } ユークリッドの互除法 ＋ 整数型データ

アルゴリズムの評価

問題の大きさ 同じ問題でも、 その大きさ毎に必要な演算数（総ステップ数、計算時間）は異なる。 大きさも考えた問題 n桁の足し算 n桁の10進数をmビットの２進数へ変換 n変数の連立方程式 n個のデータに対する、ソート n桁の数とm桁の数の最大公約数 通常入力サイズは、n,m等の文字で表します。

アルゴリズムの評価 アルゴリズムは通常「問題」を解くためのものであり、 どんな大きさでも解けないといけない。 総ステップ数を、入力サイズnの関数T(n)で評価します。 （使用メモリ量を、入力サイズnの関数S(n)で 評価することもあります。）

1000MIPS(1秒間に10億回の演算可能）の コンピュータで考えてみましょう。 関数 n 10秒 1秒 0．01秒 約 秒 20秒 計算時間と関数 1000MIPS(1秒間に10億回の演算可能）の コンピュータで考えてみましょう。 関数 n サイズ 10秒 1秒 0．01秒 約 秒 20秒 10秒 1秒 約3京世紀 30秒 1分40秒 1分40秒 甚大 40秒 16分40秒 約2時間47分 甚大 50秒 約2時間47分 約11.5日 甚大 1分 約１日 約3.2年 甚大

関数の分類（オーダー記法） 関数の増加傾向により、 関数を大まかに分類したい。 指数(時間） 対数（時間） 多項式（時間）

O記法

Ｏ記法 定義 ２つの正の値しかもたない数列を とする。 ２つの定数 , が存在し、 なる全てのｎに対し, ならば、 と書き、 はオーダー ２つの正の値しかもたない数列を　　　　　　　　　とする。 ２つの定数　　　　,　　　　が存在し、 　　　　　　なる全てのｎに対し, ならば、 と書き、 　　　　　　　はオーダー と読む。 注意１：Ｏ記法では、「＝」の左辺と右辺の交換は不可。

Ｏ記法のイメージ

Ｏ記法の例 とすれば、 に対して、 よって、 とすれば、 に対して、 よって、 注意2：通常Ｏ記法では、最も簡単な関数で表す。

Ｏ記法の例 とすれば、 に対して、 よって、 とする。 なので、 に対して、 よって、

Ｏ記法の練習 次の数列の一般項（関数）をＯ記法で表せ。

プログラムと漸近的評価 仮定１ プログラム内の加減算は、ある定数 時間以下で実行できる。 仮定２ プログラム内の加減算は、ある定数　　時間以下で実行できる。 仮定２ プログラム内の乗除算は、ある定数　　時間以下で実行できる。 仮定３ プログラム内の比較は、ある定数　　時間以下で実行できる。 仮定４ プログラム内の代入は、ある定数　　時間以下で実行できる。 . プログラムでは、このように仮定できることが多い。

プロうグラムの漸近的評価

仮定１－４より、　　　　　　　　　　　　　　　なる　 をとると、 プログラム内の4則演算、比較等はある定数時間以下で実行できる。 つよめて プログラム内では、 繰り返し構造、 （再帰関数を含む）関数呼び出し、 以外は定数時間で実行できると仮定できることが多い。

プログラムにおける計算時間の漸近評価例 function1() { for(k=0;k<n;k++) ・・・・ } この部分がｎ回 実行されることに 注意する。 function1の計算時間は、 である。

プログラムにおける計算時間の漸近評価例2 function2() { for(k=0;k<n;k++) for(j=0;j<n;j++) ・・・・ } この部分は　　回 実行されることに 注意する。 この部分は　　回 実行されることに 注意する。 この部分は　　回 実行されることに 注意する。 function2の計算時間は、 で ある。

プログラムにおける計算時間の漸近評価例3 function3の計算時間 を評価してみましょう。 function3() { for(k=0;k<n;k++) for(j=0;j<k;j++) ・・・・・・ } function3の計算時間 を評価してみましょう。

プログラムにおける計算時間の漸近評価例4 int function4(int n) { if(n＜1) return(0); } else function4(n-1); function4の計算時間 を評価してみましょう。 この漸化式より、 である。

プログラムにおける計算時間の漸近評価例5 int function5(int n) { if(n＜1) return(0); } else function5(n/2); function5の計算時間 を評価してみましょう。 この漸化式より、 である。

プログラムにおける計算時間の漸近評価例6 function6の計算時間 を評価してみましょう。 この漸化式より、 である。 int function6(int n) { if(n＜1) return; } else function6(n-1); function6の計算時間 を評価してみましょう。 この漸化式より、 である。

プログラムにおける計算時間の漸近評価練習1 次のプログラムの計算時間をＯ記法で求めよ。 ただし、入力サイズは仮引数ｎに入っている数とする。

（１） exercise1(int n) { for(j=0;j<n;j++) for(k=0;k<n;k++) ・・・・・・ } for(l=0;l<n;l++) ××××

（2） exercise2(int n) { if(n＜2) return; } else exercise2(n-1)；