アルゴリズムと データ構造 第 2 回 アルゴリズムの計算量 基本的なデータ構造（１）

前回の復習（１） アルゴリズムの数学的定義  チューリングマシンで記述可能な手続きをアルゴリズムと呼ぶ データ構造とは  データをコンピュータの記憶部分に組織化して格納する表現方 法 プログラムとは  プログラムはデータ構造を利用して，アルゴリズムをプログラ ミング言語で表現したものである

前回の復習（２） アルゴリズムの例１  身長順の名簿を作りたい 問題の解決 プログラムを作る アルゴリズムの例２  「ある正整数 m が３の倍数であるかどうかを求める」 アルゴリズムの例３  三つの整数値の最大値を求める  フローチャート  while 文、 for 文による繰り返し構造 データ型，データ構造の決定 アルゴリズムの決定 アルゴリズムと手続きの違い

演習問題の答え 第 1 問 整数 a 、 b を含め、その間の全整数の和を求めるフローチャートを記述せ よ。 なお、 a と b の大小関係にかかわらず和を求められるようにせよ。 また、 a と b が等しい場合は、和は a （または b ）そのものとなることと する。

演習問題の答え 第 ２ 問 第 1 問のフローチャートを実現する関数 int sumof(int a, int b) を作成せ よ。

アルゴリズムの計算量 計算量を測るための前提  どのようなコンピューターで処理することを前提としている か ランダムアクセス記憶 逐次実行型  アルゴリズムの良し悪しを議論するときは、個々のコンピュ ーターの性能に依存せず、一般性で表せるものに限る 並列コンピューター ノイマン型コンピュー ター ベクトルコンピューター 量子コンピューター

時間・領域計算量 時間計算量 アルゴリズムを実行したときの命令の数 領域計算量 アルゴリズムを実行したときに使用する変数や配列の数

時間計算量の種類 最悪（最大）計算量 あるアルゴリズム A に対して、入力データが与えられればその実行 に掛かる計算時間が決まるが、大きさが n であるすべての入力のう ちで計算時間が最大のもの 最良の計算時間を比較しても無意味．  入力サイズによって変化しない．  全体から見ると例外的な状況． たまたま a と b が一致する場合． たまたま a, b のいずれかが他方の倍数になっている場合．  アルゴリズムの性能を表しているとは言いがたい． 一般に最悪または平均の計算時間を比較する．  最悪 ( 最大 ) 時間計算量 : 解析的に求めやすい．  平均時間計算量 : より実態を表しているが，解析が困難． T A （ n ） = MAX (x に対する A の計算時間 ) size(x)=n である x

最大時間計算量を求める 例１： アルゴリズム A ： int s=25; T A (n) = 1 例２： アルゴリズム B ： T B (n) = 1+(n+1)+n=2n+2 例３ アルゴリズム C ： 大きさ n の配列 D[1:n] の中にある数のうちで最大のものを 求める sum = 0; for (i = 1; i <= n; i++) sum += i; big ← D[1] for (i = 2; i <= n; i++) { if( D[i] > big){ big ← D[i]; } Print (big); ① ② ③ ① ② ③ ④ ⑤ ⑥ ⑦ T C (n) = 1+n+(n-1) +(n-1)+1 = 3n

計算量の漸近的評価 例４ ある問題を解く３つのアルゴリズム A,B,C がある、これらの時間計算量 T A (n), T B (n),T C (n) を求めたところ、それぞれ T A (n)= 10000n 3 T B (n)=1000n nlogn T C (n)=n 4 であった。３つのうちでどのアルゴリズムの効率が一番良いといえるであろうか。 オーダ記法 計算量 T(n) が、ある関数 f(n) に対して O(f(n)) ( オーダ f(n)) であるとは、適当な２つの正の 定数 n 0 と c が存在して、 n ≧ n 0 となるすべての n に対して、 T(n) ≦ cf(n) が成り立つことをいう 計算量 T(n) が、ある関数 f(n) に対して O(f(n)) であるとき、 f(n) を T(n) の漸近的上界という T(n) のオーダは f(n) である

計算量の漸近的評価 例５ 計算量 T(n) が、 T(n)=4n 3 +2n であるとする. n ≧ 1 なるすべての n に対し て、 T(n)=4n 3 +2n ≦ 4n 3 +2n 3 = 6n 3 が成り立つので、 T(n) は O(n 3 ) である 例６ 計算量 T(n) が、 T(n)=2n+ nlog 2 n であるとする. n ≧ 4 なるすべての n に 対して、 T(n)= 2n+ nlog 2 n = n(2+log 2 n) ≦ n(log 2 n+log 2 n) = 2nlog 2 n が成り立つので、 T(n) は O(nlog 2 n) である 評価のルール１ 評価のルール ２ T(n) がいくつかの項の和になっているときには、主要項のみを残す、それ以外の項は無視してよい 主要項： n の値が大きくなるに連れて一番大きくなる項 T(n) の主要項の係数も無視して良い

オーダ記法の基本的な性質 和の規則 T 1 (n) と T 2 (n) をそれぞれ O(f 1 (n)), O(f 2 (n)) である計算量とし、このとき、 T 1 (n) ＋ T 2 (n) は O(max(f 1 (n), f 2 (n))) である 積の規則 T 1 (n) と T 2 (n) をそれぞれ O(f 1 (n)), O(f 2 (n)) である計算量とする、このとき、 T 1 (n) ・ T 2 (n) は O(f 1 (n) ・ f 2 (n))) である 例４ ある問題を解く３つのアルゴリズム A,B,C がある、これらの時間計算量 T A (n), T B (n),T C (n) を求めたところ、それぞれ T A (n)= 10000n 3 T B (n)=1000n nlogn T C (n)=n 4 であった。３つのうちでどのアルゴリズムの効率が一番良いといえるであろうか。 O(n 3 ) O(n 2 ) O(n 4 ) 例３ アルゴリズム C ： 大きさ n の配列 D[1:4] の中にある数のうちで最大のものを求める big ← D[1] for (i = 2; i <= n; i++) { if( D[i] > big){ big ← D[i]; } Print (big); ① ② ③ ④ ⑤ ⑥ ⑦ O(n)

注意点 1. T(n) の増加の様子を一番良く表す単純な関数を用いる 2. オーダによる評価は漸近的な評価で、計算量の第１次近似でしかない 3. 指数時間アルゴリズムは、現実的ではない 図：オーダ評 価に用いられ る関数の増加 の様子 多項式時間アルゴリズム（ polynomial time algorithm ） 時間計算量が、 n,nlogn, n 2, n 3 等のような n の多項式のオーダであるようなアルゴリズム 指数時間アルゴリズム（ exponential time algorithm ） 時間計算量が、 2 n, n!, n n 等のような n の多項式のオーダであるようなアルゴリズム T(n) ≦ cn 2 ≦ cn 3 ≦ cn 4 ≦ … スーパーコンピューター京

配列 配列の必要性 配列の定義 配列（ Array ） は、同一型の変数である要素（ element ）が集まって直線 状に並んだデータ構造である 配列の基本  同じ型の要素の集合体  要素の型は任意：算術型、ポインタ、構造体、共用体、配列など

宣言 初期化と利用 int a[5]; /* int 型で要素数 5 の配列を宣言 */ /* a[0] から a[4] まで利用可能 */ a[1] = 5; /* a[1] に 5 を代入 */ x = a[3]; /* a[3] から値を取り出し x に代 入 */ s = sizeof(a) / sizeof(a[0]);/* 配列の要素数を s に代入 */ int a[5] = {1, 2, 3, 4, 5} ; /* 配列宣言時に初期化可能 */ 配列の宣言と利用 int a[5]; /* a は要素型が int 型で要素数 5 の配列 */ double height[20]; /* height は要素型が double 型で要素数 20 の配列 C の場合は添字が 必ず０から始ま る！ a[i]

配列の特徴 各要素はメモリ上に同じサイズで連続して格納される 添え字 ( インデクス ) を指定することで，要素にランダム にアクセス（ random access ）可能 data[0] data[1] data[2] data[3] 個々のセルに整数型の要素 が格納されている． 100 ： 104 ： 108 ： アドレス メモリ 使いたいデータにすぐアクセスできること CD プレーヤは聴きたい曲にランダムアクセス可能 カセットテープは聴きたい曲を前から順に探す必要がある ⇒シーケンシャルアクセス (sequential access) y = data[2]; 例） data[4]

配列の短所 データの数をあらかじめ宣言する必要がある データを格納するための領域を自由に追加した り、不要になったら領域を開放したい … どう する？ ⇒ ポインタを利用 int a[3];

（復習）ポインタ（ pointer ）とは 変数を指し示すためのデータ型 他のデータへの参照を示す（他のデータがある 場所の番地が格納される） ポインタ型がある言語： C, PASCAL ポインタ型がない言語： BASIC, FORTRAN

ポインタ ポインタ型変数 ptr アドレス n １０４番地 : メモリ空 間 ptr ８０番地 : 「 ptr は n を指している 」 とは？ int 型変数 n

ポインタとアドレス アドレス ５０ １０４番地 : メモリ空 間 １０４番地 ８０番地 : 変数 n のデータが入っ ているメモリ上のア ドレスが格納される ポインタ型変数 ptr int 型変数 n

ポインタ型変数宣言の例 int n; int *ptr; n = 50; ptr = ＆ n; アドレス演算子 （単項 & 演算子， &operator ） データが格納されているアドレスを 取り出す演算子 ← n は int 型の変数 ← ptr は int 型の変数を指すポインタ変数 ポインタであることを表わす記号 （ “ アスタリスク ” という）

ポインタ型変数宣言の例 int n; int *ptr; n = 50; ptr = ＆ n; ptr n 1004 番地 :80 番地 : 番地 :80 番地 : 1004 番地 番地 :80 番地 :

まとめ アルゴリズムの計算量 最悪（最大）計算量 計算量の漸近的評価 （オーダ） 配列 ポインタの復習

演習問題 第 1 問 次のような計算量 T(n) について、そのオーダを求めなさい (a) T(n) = 1.5n n n (b) T(n) = 4logn +8n (c) T(n) = 3n 2 + 7nlog3 n (d) T(n) = 2 n + 3n 5 第 2 問 計算量 T(n)= 2 n+1 のとき、そのオーダは 2 n といえるか。また、 T(n)=2 2n のときはど うか示しなさい。