効率のよいメモリ使用と動的メモリ確保
次にメモリの利用効率の話について解説する。 配列宣言でサイズは定数 C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。 最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使っ […]
ポインタの加算と配列アドレス
ポインタの加算と配列アドレス ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。 // ポインタ加算の例 int a[ 5 ] = { 11 , 22 , 33 , 44 , […]
ソートアルゴリズム
前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。 ポインタについての説明は、前回の […]
ポインタを使った処理
この後の授業で、ポインタを使ったプログラムが増えるので、ポインタの理解の確認 ポインタと引数 値渡し // 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応す […]
再帰呼び出しと再帰方程式
再帰関数と再帰方程式 再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。 // 階乗 (末尾再帰) int f […]
授業アンケート結果(ぷちブルーな気分)
情報ネットワーク基礎(3EI/後期) 楽しんで受講してくれた人からの意見があり、ポイントでも85ポイントと高評価であった。内容理解やシラバスについてポイントが若干低いようであるが、誤差の範疇と思われる。理解把握のポイント […]
処理時間のオーダー(回答編)
2分探索法の処理時間の見積もり コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。 データ10000件なら何[sec]かかるか？ 解答 2分探索法なので、処理時間はO(logN) であり、T(N […]
ループ処理時間とオーダー記法と再帰
先週に、単純繰り返し処理の時間分析をやったので、次のステップに。 2分探索法の処理時間 データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。 // 2分探索法 O(log N) […]
2019年度情報構造論ガイダンス
情報構造論のガイダンス プログラムを評価する3つのポイント この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。 プログラムの速度 […]
情報構造論2018-講義録
情報構造論ガイダンス 繰り返し処理とオーダ記法 再帰処理の処理時間 マージソートのオーダー メモリを効率よく使うには mallocとfree 様々なメモリ確保 前期中間テストの答案返却 リスト構造について リスト構造での […]