ホーム » スタッフ » 斉藤徹 » オーダ記法と処理時間の見積り&再帰関数

2008年4月
« 3月   5月 »
 12345
6789101112
13141516171819
20212223242526
27282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

オーダ記法と処理時間の見積り&再帰関数

先週の単純検索や最大選択法の処理時間の発展として、2分探索法の処理時間が、 IMG n /cgi-bin/mimetex.cgi?T(N)={T_a}+\log{N}\times{T_b} を示し、これらの処理速度の見積りでは、Nが大きくなったときの最大項しか 使わない点や、Nの式の部分が重要であることを確認し、オーダ記法を説明する。

オーダ記法では、Nが大きくなったときの最大項を抜粋し、係数は書かないことを示す。 簡単な時間式からオーダ記法を求めたり、時間予測の例題を示す。

時間があったので、次の再帰関数の時間見積りの例として、 再帰関数(fact,dango,fib)の実行予測を行い、再帰の処理の流れを復習。 fact,dango などが IMG n /cgi-bin/mimetex.cgi?T(N)={T_a}+{N}\times{T_b} であることを示す。