ホーム » 2009 » 4月 » 16

日別アーカイブ: 2009年4月16日

2009年4月
« 3月   5月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ループ処理とオーダ記法

ループ処理の時間

先週の、単純検索の処理時間が、 T(N)=Ta+Tb*N、 2分探索のループ回数が、 m=log(N)の説明に続き、 その処理時間は、 T(N)=Ta+Tb×log(N) であることを示す。

もう少し複雑になった事例ということで、2重ループを含む最大選択法による並べ替えは、 最内ループ回数が m=∑(i=1~N-1){ i }となることを示し、 最大選択法の処理時間は、 T(N)=Ta+Tb*N+Tc*N^2で示されることを説明する。


その他の公式

オーダ記法

前述の処理時間の式では、処理時間に関する定数が沢山でてくる。 また、Nが大きく変化した時の処理時間のおおよその予測の際には、 Nの次数の低い項は無視する場合が多い。

このためプログラムのアルゴリズムの効率(処理時間)を議論するときは、 Nが巨大になった時の最も値の大きい項の変化式の部分だけで、 大まかな処理時間の予測ができる。この式でアルゴリズムを表現したものを オーダ記法(ビッグオー記法)と呼ぶ。

よって、 単純検索は、、 2分探索は、、 最大選択は、で示されることを説明する。

処理時間の予測

2分探索法で、データ(N)が100件の時の処理時間が1msecであった場合、 データが1000件の場合どのくらいの処理時間となると予想されるか?

オーダ記法では、 は、 なので、 より、 (ただしlogの底は10とする)。 よって、

授業の最後に、複数の項のNの次数が微妙で増加速度の判断が困難な場合の オーダーを求める手法として、ロピタルの定理を用いた方法なども説明する。

Cでのオブジェクト指向もどき

先週の、機械系・電気系学生向けの構造体の説明の続き。 C言語でのオブジェクト指向もどきの解説。

変数と関数

プログラミングの基礎として、大域変数と局所変数を説明。 特に大域変数は、常に操作できる領域で、誤った操作による破壊の可能性が高く、 関数や局所変数を利用すべき点を力説する。 次に、関数と呼び出し側のデータの受け渡しとして、 値渡し・ポインタ渡し・参照渡しなどを説明する。

これにより、必要最小限の情報だけを関数に開示して、 値を修正してもらうことができる点を説明。

/* 値渡し */
void func( int x ) {
x++ ;
printf( "%d" , x ) ;
}
void main() {
int a = 123 ;
func( a ) ;  // 124 を表示
func( a ) ;  // 値渡しでaへの副作用がないので再び124を表示。
}
/* ポインタ渡し */
void func( int* p ) {
(*p)++ ;
printf( "%d" , (*p) ) ;
}
void main() {
int a = 123 ;
func( &a ) ;  // 124を表示。
func( &a ) ;  // ポインタの先のaが変化しているので125を表示
}
/* 参照渡し */
void func( int& x ) {
x++ ;
printf( "%d" , x ) ;
}
void main() {
int a = 123 ;
func( a ) ;  // 124の表示。a への副作用あり
func( a ) ;  // 125の表示。
}

Cでのオブジェクト指向もどき

C言語の構造体だけでオブジェクト指向の雰囲気を示すことができる点を、 下記のプログラムによって説明する。

これによって、main内部では、データの内容を知らなくても(データ隠ぺい), 関数の中身を知らなくても(手続き隠ぺい)プログラムが書けるようになった点を説明。 さらに、struct 宣言がオブジェクト、データ操作の関数をメソッドと呼び、 その2つを合わせてたものをクラス(class)と呼ぶことを説明する。

// Personオブジェクト
struct Person {
char name[ 10 ] ;
int  age ;
} ;
// Personの初期化メソッド
void set( struct Person* p , char s[] , int a ) {
strcpy( (*p).name , s ) ; // 最初の説明ではあえて
(*p).age = a ;            // アロー演算子は使わない
}
// Personの表示メソッド
void print( struct Person* p ) {
printf( "%sさんは%d才です。" ,
p->name , p->age ) ;  // ちょっと説明したあとでアロー演算子を使う。
}
void main() {
struct Person saitoh ;     // Personのインスタンス
struct Person family[ 4 ] ;
set( &saitoh , "とおる" , 44 ) ;
print( &saitoh ) ;
set( &family[0] , "あゆか" , 7 ) ;
set( &family[1] , "みつき" , 9 ) ;
print( &family[ 0 ] ) ; print( &family[ 1 ] ) ;
}