オーダ記法と再帰関数
先週は、単純サーチ、最大選択法などの説明だったので、 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)
この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。