ホーム » 2012 » 4月 » 19

日別アーカイブ: 2012年4月19日

2012年4月
1234567
891011121314
15161718192021
22232425262728
2930  

検索・リンク

オーダ記法と再帰関数

先週は、単純サーチ、最大選択法などの説明だったので、 2分探索方の説明を行い、

単純サーチ T(N) = Ta + Tb×N
最大選択法 T(N) = Ta + Tb×N + Tc×N^2
2分探索法 T(N) = Ta + Tb×log N

これらのTa,Tb,Tcは、計算機の性能に依存し、アルゴリズムの優劣判断には使えないので、 これらを記載しないオーダ記法を用い、 O(N) , O(N^2) , O(log N) のように記載する。

再帰関数

for 分による繰り返しの分析ができても、再帰処理を含む場合は、面倒になる。

以下のような再帰関数を示し、動作トレースのあと、一番簡単な fib について、 処理時間を示す。

int fact( int x ) {
if ( x == 0 )
return 1 ;
else
return x * fact( x - 1 ) ;
}
int fib( int x ) {
if ( x < 2 )
return 1 ;
else
return fib( x - 2 ) + fib( x - 1 ) ;
}

変数のスコープと寿命、数値の範囲

制御構文の説明の後として変数の説明、数値の範囲を説明。

int x=123; // 大域変数
void foo( int x ) { // 局所変数の仮引数。
x++ ;
printf( "%d" , x ) ;
}
void main() {
int a= 234;
foo( a ) ; // 235 値渡しでコピーされる。
foo( a ) ; // 235
}

関数の書き方の説明をしたけど、値渡し、ポインタ渡しの説明が不完全。 来週は、値渡し、ポインタ渡しを説明。

数値の範囲

char , short int , int , long int 、unsigned , signed といった型を説明。 数値の範囲は、他の授業で丁度やっていたので、すんなり説明が終わる。 ただし、2の補数表現の説明追加が必要かな。

職場の発注システムで、…(04/18)

  • 04/18 職場の発注システムで、プリンタトナーを発注したつもりだったけど、起票してなかった。おかげで、カスカス印刷の発注書のできあがり…. #fnct

この記事は、twitter の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。


システム

最新の投稿(電子情報)

アーカイブ

カテゴリー