アルゴリズムとデータ構造 1章の復習 第2章 リスト構造 ５月10日 情報知能学科 白井英俊 計算量：時間と空間 • 時間計算量、もしくは時間複雑度(time complexity) そのアルゴリズムを実行するのに、最悪の場合、どのくらい時 間がかかるかを、入力の大きさの関数として表す • 空間計算量、もしくは空間複雑度(space complecity) そのアルゴリズムを実行するのに、最悪の場合、どのくらい 記憶領域が必要かを、入力の大きさの関数として表す 計算量（複雑度）＝時間計算量＋空間計算量 時間計算量の常識的な評価 • 教科書p.8 O(1) --- 理想的に速い O(log n) --- 非常に速い O(n) --- 速い O(n log（n)) --- 速いほう O(n2) --- かなり遅いが、許されないほどではない O(n3) --- かなり遅い。許される限界。 O(cn ) --- (cは1より大きい定数）。指数オーダ (exponential order)。とっても遅い。 計算量の演習1 • 教科書p.11 1.1 次の5種類の計算時間を、nを横軸にとって、一つ のグラフに重ねて表せ。そして、そのグラフから オーダの大小関係が読み取れることを観察せよ。 f1(n) = 10000 n f2(n) = 10000 n log(n) 実際にグラフを書く前に、 これらのオーダがどうなるか f3(n) = １00 n**2 考えておいてください f4(n) = 10 n**3 f5(n) = 2**n 計算量の演習1の解答 • GnuPlotを用いる。ただし、ｘをnと「読み替える」 (1≦x≦30 のグラフ。x=30 では f5 > f2 > f1 > f4 > f3のように見えるが…） 1 1 1 e e e + + + 0 0 0 1 0 0 0 f 1 ( x ) f 2 ( x ) f 3 ( x ) f 4 ( x ) f 5 ( x ) 9 8 1 e + 0 0 7 1 e + 0 0 6 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 5 1 0 1 5 2 0 2 5 3 0 計算量の演習1の解答(続) f5を除いて3000まで表示させると、 f4 > f3 > f2 > f1 となる ことが分かる 1 1 e e + + 0 0 1 1 2 f 1 ( x ) f 2 ( x ) f 3 ( x ) f 4 ( x ) 0 1 e + 0 0 8 1 e + 0 0 6 1 0 0 0 0 1 0 0 1 0 5 0 0 1 0 0 0 1 5 0 0 2 0 0 0 2 5 0 0 3 0 0 0 計算量の演習1 の解答(まとめ) つまり、nが十分大きければ、 n < n*log(n) < n2 < n3 < 2n であることが分かる f1(n) = 10000 n オーダ：O(n) f2(n) = 10000 n log(n) O(n log(n)) f3(n) = １00 n**2 O(n2 ) f4(n) = 10 n**3 O(n3 ) f5(n) = 2**n O(2n ) 計算量の演習２ • 教科書p.11 1.2 ステップ数が f(n)=100000n, g(n)=10n**3, h(n)=2**nの3つのアルゴリズムにn=100の大きさの データを与えたとする。1ステップが10**(-9)秒で 実行できるコンピュータで走らせたときの計算時間 は次のどれに近いか？ 1ミリ秒、1秒、1分、1時間、1日、1ヶ月、1年、1世紀 計算量の演習２の解答 問題：ステップ数がf(n)=100000n, g(n)=10n**3, h(n)=2**nの3 つのアルゴリズムにn=100の大きさのデータを与えたとする。 1ステップが10**(-9)秒で実行できるコンピュータで走らせたとき の計算時間は？ 210 =1024 ≒103 答え： f(100)=100000*100 = 107 だから2100=(210)10= (103)10 g(100)=10*100**3 =107 1ステップが10-9秒なので、f もgも107*10-9 =1*10-2秒 (10ミリ秒) h(100)=2**(100) ≒ 1030 1ステップが10-9秒なので、h(100)*10-9 ≒ 1030*10-9 =1*1021秒 1年＝60*60*24*365≒ 3.2*107 秒, 1世紀=100年=3.2*109秒 計算量の演習３ • 教科書p.11 1.4 次の式のオーダを、最も忠実で簡単な式を用いて 表せ。 (1) 6.5n3 + 8n2 + 5 (2) 5 n log(n) + 3 n2 (3) 2.5 n √n + 3.6 n log(n) (4) 5 n + 8 log(n) (5) 2n + 5 n 5 (6) 800 n log(n) + n 計算量の演習３の解答 • 問題： 次の式のオーダを、最も忠実で簡単な式を 用いて表せ。 (1) 6.5n3 + 8n2 + 5 (2) 5 n log(n) + 3 n2 (3) 2.5 n √n + 3.6 n log(n) (4) 5 n + 8 log(n) (5) 2n + 5 n 5 (6) 800 n log(n) + n 注意：2nのような「２」は定数倍 ではない。nの関数に『掛け算』 されている『数』が無視の対象 解法： (1)定数倍を無視 (２)最も大きくなるnの項だけを残す 計算量とオーダ • ここまでで何か質問は？ • アルゴリズムが与えられた時に、『計算量』を 求めることは、5章に入ったら… ４月の講義のまとめ • 「アルゴリズム」 • 「アルゴリズム」の計算量 時間複雑度、空間複雑度 オーダ ： log(n), n, n*log(n),n**2, n**3, 2**n, n! • 「アルゴリズム」をプログラムとして実現することにより、アル ゴリズムの検証を行う ー プログラムを書くだけではなく、い ろいろな例で実験する • そのために、Rubyの復習が必要（代入、条件分岐、繰り返し 、変数／定数、配列、クラス） アルゴリズムをプログラムとして実現する • 再帰関数：プログラムを書く、プログラムを読む（動きを追う） アルゴリズムの例 入力 • 問題（教科書p.1)： n個の実数x1, x2, …, xnが 与えられて、その中の最大値を求める 出力 • 素朴版(p.1) x1, x2, …, xnを順にみていく。その途中でいつ も、「それまでに見た数の最大値」を覚えてお く。最後まで見終わったとき、「それまでに見 た数の最大値」が求めるべき最大値 14 アルゴリズムの例（続) 最低限、このように書けるようになろう！ • より明確な記述(p.2) 入力： 正の整数nとn個の実数値x1, x2, …, xn 出力： x1, x2, …, xnの中の最大値 手続き： 「変数y に x1の値を代入する」 1. y ← x1 (yは「それまでの最大値」を記録） 2. i = 2,3,…,nに対して順に次を行う： xi > y ならば y ← xi 3. yを出力する 15 アルゴリズムの例（続) MAXはアルゴリズムの名前。カッコのな かは入力「引数」を書く。 • 「プログラム」風(p.3) Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中の最大値 手続き（Procedure): ここでの記法についてはウェブページの 「教科書のアルゴリズムの記述とRUBY言 1. y ← x1 ; 語の対応」参照 2. for i ← 2 until n do if xi > y then y ← xi ; 3. return y; このような記法のアルゴリズムから プログラムを実現できるように！ 16 新しい概念：ポインタ(pointer) • ポインタの元々の意味は「指さし」。 • 「変数」の役割は、 「オブジェクトを指す」 （オブジェクトを「値」として持っているわけではない） 例えば、変数xに配列[1,2,3] を代入したとする。 その結果、「変数」の値として配列[1,2,3]が入るのではなく、 配列そのものは別の場所に作られ、その場所への『手がか り』が「変数の値」になる。 このような手がかり(記憶番地、アドレス)をポインタという。 Rubyの変数の『値』は、みなポインタ • 参考: プログラミング言語Cでは、int *x のように書いて、変数xは、整数オブジェクトへのポイ ンタ(アドレス)を値とする、というように宣言する ポインタの詳細 • アドレス（記憶番地）：コンピュータの記憶場所 ここでは少し拡張して「データの格納場所の手が かり」（場所の情報）と考える 例： 配列を変数に代入 変数名 x 記憶場所b 記憶場所a アドレス 配列：かなりの場 所を必要とする複 雑なデータ ポインタによる説明 コンピュータの内部： x = [1, 2, 3] y=x x xの記憶場所 x[1] = 5 5 y yの記憶場所 p y => [1,5,3] x.shift p y => [5, 3] 配列： [ 1, 2, 3 ] 注意：本当は「配列」は、かなり 複雑な形をしているのだけど、 簡略化しています クラスとインスタンス Rubyのオブジェクトには 数、文字列、配列、…などがあった これは、プログラミング言語としてはかなり豊か これらを使いこなせば、いろいろなことができる。でも… 問題に適したデータ構造を考えないといけないことが ある。 そのために、クラス定義とインスタンス生成の方法は 知っておかないといけない （本講義では これから多用します） Rubyにおけるクラス定義 • オブジェクト指向 プログラムが扱うデータ（オブジェクト）と、それをど のように扱うかという手続き（関数）とを「組」として表 す • クラスーオブジェクトの「種類」 • クラス定義 1) どのようなパーツ（部品）があるかを宣言：インス タンス変数 2) 手続き（関数)の宣言：インスタンスメソッド クラス定義の例 • 名簿の一つの項目を「クラス」として定義する • 名簿の項目(Item)には、(少なくとも)次のパーツ（部 品)をもつと考えられる 1)名前 2)住所 3)生年月日 4)性別 5)年齢 name address birth_date sex age これを図示すると… クラス名 Item name address 部品名 birth_date sex age 具体的な値がはい る（ポインタ) クラス定義の例(続) • 右に図示した名簿の項目 (Item)に対応した「クラス」: Item name 大文字から始める class Item address def initialize(n,a,b,s) birth_date @name = n sex @address = a age @birth_date = b @sex = s Initialize は重要なインスタンスメソッド。 @age = Time.now.year - b 「インスタンス」作成の時に説明 end end @つきの変数が「インスタンス変数」 これが「パーツ（部品）名」になる クラス定義の例(続) ただ、このままだと、部品にアクセス(取り出し、参照)しにくいので … Item class Item def initialize(n,a,b,s) name @name = n address @address = a birth_date @birth_date = b sex @sex = s age @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age end (1) attr_accessor につづけて (2) インスタンス変数名の前にコロン( : ) インスタンス生成 • 鯛焼きに例えて言えば、 クラス定義は、鯛焼きを焼く金型(鉄板) これだけでは、鯛焼きは食べられない… 鯛焼きを食べるには、「材料を用意して、鯛焼き を作る」必要がある。 それをするのが、「インスタンス生成」 「Taro Yamada」の名簿項目を作る: 注：ここでは、生年月日ではな く「生まれた年（西暦）」としよう Item.new(“Taro Yamada”, “Toyota”, 1990, “male”) インスタンス生成(続) Item.new (“Taro Yamada”, “Toyota”,1990, “male”) これにより、initializeメ ソッドが呼び出される その引数の n, a, b, sがそれ ぞれ Item.new の実引数と 結び付けられ、 次に の文が実行 されて、次に示すようなItem クラスのインスタンスができ あがる: class Item def initialize(n, a, b, s) @name = n @address = a @birth_date = b @sex = s @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age end インスタンス生成（完成) Item.new(“Taro Yamada”, “Toyota”,1990, “male”) Itemクラスのインスタンス name address “Taro Yamada” “Toyota” birth_date 1990 sex “male” age ２０ 注：Time.now.year が 2010を返すとすれば 演習1：クラスとインスタンス 注：補助資料を参照してください： 演習1.１．Itemクラス定義を用いて、以下の例を参考に、自分に 当てはめて名簿項目(Itemインスタンス)を生成せよ（注意：女 性の場合、性別は”female”） mydata = Item.new(“Taro Yamada”, “Toyota”, 1990, “male”) 演習1.２．上を実行後 mydata.age の値を表示させよ。 演習1.3. さらに mydata.age = ３0 を実行させた後の mydata.birth_date と mydata.age の値を表示させよ。 クラス定義（追加）：インスタンスメソッド そのインスタンスだけに適用される関数(メソッド)の定義： class Item def initialize(n,a,b,s) @name = n ; @address = a @birth_date = b ; @sex = s @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age def show(sep = “, ”) return “Name: “+@name+sep+” Sex: “+@sex+sep+”Age: “+@age end end 注：(sep=“,”) は、メソッド(関数)の引数が省略できること、また省 略された場合に”,”が値となることを表すRubyの記法 演習2：クラスとインスタンス 注：補助資料を参照してください： 演習２(発展)： (1) 複素数を表すクラスを定義せよ。そのクラスの名 前を Complex とし、パーツは二つ、 real (reと略す、 実部) と imaginary (im と略す、虚部)。 (2) 補助資料の例にならって、複素数同士の引き算 と割り算をするメソッドを付け加えよ。 (3) インスタンスを2つ以上つくり、計算がちゃんと行 われることを確かめよ。 複素数について • 2つの複素数を (a+bi), (c+di)とすると(a,b,c,dは 実数, iは虚数) 足し算： (a+bi) + (c+di) = (a+c) + (b+d)i 引き算： (a+bi) - (c+di) = (a-c) + (b-d)i 掛け算： (a+bi) * (c+di) = (a*c - b*d)+(b*c + a*d)i 割り算： (a+bi) / (c+di) = (a*c + b*d)+(b*c - a*d)i c2 + d2 c2 + d2 参考： (c –di)は(c+di)の共役複素数 (a+bi) (c+di) (a+bi) (c - di) (c+di) * (c - di) (a*c + b*d) (b*c -a*d)i c2 + d2 + c2 + d2 （予習)リストの必要性とポインタ • 名簿のような｢表｣を記憶することを考える 普通の方法： 1行分記憶するのに必要な記憶の大 きさをkバイトとして、コンピュータ上に固定した記憶 場所を確保して使う 0 1行k バイト k 2k … リストの必要性とポインタ（続） • 表方式の特徴：検索が容易 n件目のデータは、n*k～(n+1)*k-1の範囲 に入っている • 表方式の欠点：データの削除や挿入の手間 が大きい 例：1番目のデータを削除したら、その 後のデータをすべて一行ずつ前に移動し なければならない リストの必要性とポインタ（続） • リスト（線形リスト）：表方式の欠点を解消 – データの挿入、削除の手間が軽減 – ただし、記憶場所が多く必要、データの検 索(アクセス）の手間がかかる、という欠点あ り • リスト(線形リスト）の基本単位：セル(Cell) data next データ部 ポインタ データ部： データの記憶用 ポインタ部：別なセルのアドレス セル(Cell) • 線形リスト構造を表現する基本単位セル 例えて言えば、連結器つきの車両 つながったセルの図
© Copyright 2024 ExpyDoc
