アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2009年6月11日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html
アルゴリズムとデータ構造基礎
オブジェクト指向の概念とJava言語
オブジェクト指向 = Object Oriented
Java言語のOO的なところの概説
計算量の概念とO記法
空間計算量と時間計算量
O記法
オブジェクト指向(OO)の概念
• オブジェクトを基本にとらえようとする考え
• オブジェクト間はメッセージパッシング
– オブジェクトの中身をいぢるのはオブジェクト自身
• メソッドが内蔵されている
• 従来の考えとちょっと違う
メソッドがオブジェクトに内蔵されてるとか
クラスが継承できるとか
 いろいろありますね…
オブジェクトとクラス
• オブジェクト＝もの
– 実体のあるものすべてオブジェクト
• クラスとは？
– 設計図のようなもの
– 型のようなものだけど型ではない
• メソッドを含むこともできる
• メソッドとは？
– オブジェクトへの操作を定義したもの
– オブジェクトへメッセージが送られたとき使われる
簡単な例
クラス: 人間
この講義の受講生だけでも９０人いたりするわけで…
Aさん
Bさん
Zzさん
学習方法
学習方法
学習方法
教科書
教科書
お金の使途
お金の使途
お金の使途
財布＋お金
財布＋お金
財布＋お金
・・・
教科書
OOの概念とJava言語
• オブジェクトはクラスのインスタンス
– 例えば、newすればインスタンスは生成できる
• メッセージを渡すこと＝関数を呼ぶこと
– 渡したいメッセージは引数
– 受け取りたいメッセージは戻り値
• 継承、インターフェース
継承(inheritance)
• 基底クラスの構成要素をそのままに、拡
張する仕組み。
– Javaではextendsにより継承
– extendsの右側のクラスが基底クラス
– 継承の結果できたクラス＝派生クラス
class baseClass {
void methodBase(){
// 何らかの処理１
}
}
class inheritedClass extends baseClass {
void methodInherited(){
// 何らかの処理２
}
}
静的束縛と動的束縛
• オーバーライド
– 基底クラスで定義されるメソッドを派生クラスで
再定義すること
• 隠蔽
– 基底クラスのstaticメソッドを派生クラスの
staticメソッドでオーバーライドすること
– 隠蔽は静的束縛が適用される
• 動的束縛
– クラス構成要素を呼び出す際に決定
– オブジェクト変数に代入されたオブジェクトによ
り呼ばれる構成要素が決まる
継承とオーバーライド
class baseClass {
// 基底クラス
void methodA(int i){
// 派生クラスによりオーバーライドされる
int x = i * 1000;
System.out.println(x);
}
void methodB(int i){
// 派生クラスに継承される
int x = i + 1000;
System.out.println(x);
}
}
class inheritedClass extends baseClass {
// 派生クラス
void methodA(int i){
// オーバーライドします
int x = i * 10;
System.out.println(x);
}
public static void main(String[ ] args) {
inheritedClass objectInherited = new inheritedClass( );
objectInherited.methodA(10);
// 100 を表示
objectInherited.methodB(10);
// 1010 を表示
}
}
静的束縛
class baseClass {
// 基底クラス
static void methodA(int i){
// クラスメソッド
int x = i * 1000;
// プログラムとともに存在
System.out.println(x);
}
static void methodB(int i){
// クラスメソッド
int x = i + 1000;
System.out.println(x);
}
}
class inheritedClass extends baseClass {
// 派生クラス
static void methodA(int i){
// クラスメソッド
int x = i * 10;
// プログラムとともに存在
System.out.println(x);
}
public static void main(String[ ] args) {
baseClass certainObject = new inheritedClass( );
certainObject.methodA(10);
// 10000を表示
certainObject.methodB(10);
// 1010を表示
}
}
動的束縛
class baseClass {
// 基底クラス
void methodA(int i){
// インスタンスメソッド
int x = i * 1000;
//
newしたときに生成
System.out.println(x);
}
void methodB(int i){
// インスタンスメソッド
int x = i + 1000;
System.out.println(x);
}
}
class inheritedClass extends baseClass {
// 派生クラス
void methodA(int i){
// インスタンスメソッド
int x = i * 10;
//
newしたときに生成
System.out.println(x);
}
public static void main(String[ ] args) {
baseClass certainObject = new inheritedClass( );
certainObject.methodA(10);
// 100を表示
certainObject.methodB(10);
// 1010を表示
}
}
計算量の概念（7ページ
1.2節）
• アルゴリズムの性能を示す指標
– 時間計算量
• (文字通り)計算に要する時間
– 空間計算量
• どれくらいの作業領域を必要とするかを表す
• 大きな問題が少ない計算量で解ければ優秀
– 漸近的に表現したものがO記法
• 計算量を定式化したとき、計算量に最も大きな影響
を及ぼす項をとりだしたもの。
O記法
• 漸近的な振る舞いを表す
– 定数項は無視
– 係数は１
– 一般には最も影響力の強い項のみで表す
• 項の形で大きく２つに分けられる（問題:n）
– 多項式
– 指数関数
ｋ
n
n
k
O(n)
2
O(n )
O(e )
n
O(n log n)

Download Report